1、冒泡排序
1.1从右往左两两比较，把每轮的最小值放在了arr[i].
双重for循环
外层循环：定位。 内层：比较交换。
最好时间复杂度：O（n）
最差时间复杂度：O（n^2）
平均时间复杂度：O（n^2）
空间复杂度：O(1).
稳定

//从右往左两两比较，把每轮最小的放在了arr[i]
function bub(arr){let len = arr.length;for(let i=0;i<len;i++){let flag = false;for(let j=len-1;j>i;j-- ){if(arr[j]<arr[j-1]){swap(arr,j-1,j);flag = true}}//没有交换 说明已经排好序了if(!flag) return arr;}return arr
}
function swap(arr,i,j){temp = arr[i];arr[i]=arr[j];arr[j]=temp;
}
let arr = [2,1,4,6,5];
console.log(bub(arr));

1.2从左往右两两比较，把每轮的最大值放在了最右 arr[len-i]。

//从左往右两两比较，把每轮最大放在了最右 arr[len-i]
function bub(arr){let len = arr.length;for(let i=0;i<len;i++){let flag = false;for(let j=0;j<len-i-1;j++){if(arr[j]>arr[j+1]){swap(arr,j,j+1);flag = true;}}//没有交换 说明已经排好序了if(!flag) return arr}return arr;
}
function swap(arr,i,j){temp = arr[i];arr[i]=arr[j];arr[j]=temp;
}
let arr = [2,1,4,6,5];
console.log(bub(arr));

2、选择排序
每轮获取得到最小值的下标，如果这个下标不是当前i，就将这两个值交换。
双重for循环
外层循环：定位。 内层：找最值。
最好时间复杂度：O（n^2）
最差时间复杂度：O（n^2）
平均时间复杂度：O（n^2）
空间复杂度：O(1)。
不稳定。

function selectsort(arr){let len = arr.length;let min;for(let i=0;i<len;i++){min = i;for(j=i+1;j<len;j++){if(arr[j]<arr[min]){min = j;}}if(min!=i){swap(arr,i,min);}}return arr;
}
function swap(arr,i,j){var temp =arr[i];arr[i] = arr[j];arr[j] = temp;
}
let arr = [2,1,4,6,5];
console.log(selectsort(arr));

3、直接插入排序
当前 i 往它的左边看，不合适的往后移，腾出一个位置可插入，不断去找这个值应该插在什么位置。
双重for循环
外层循环：定位。 内层：与前元素比较腾空位。

最差时间复杂度：O（n^2）
平均时间复杂度：O（n^2）
空间复杂度：O(1)

function insertsort(arr){let len = arr.length;var i,j;for( i = 1;i<len;i++){let val = arr[i];for( j=i-1;j>=0;j--){if(arr[j]<val){break;//val已经大于它左边的第一个a[j]，退出第二个for}//arr[j]>val  不用判断直接腾位置吧arr[j+1]=arr[j];//a[j]比val大,a[j]往后腾位置}
//一直往左看，找到合适的位置时a[j]一定要比val小，val就应该在腾出的a[j+1]w位置arr[j+1]=val;//val找到它该放的位置}return arr
}
let arr = [2,1,4,6,5];
console.log(insertsort(arr));

另一种写法更容易理解：

function insertsort(arr){let len = arr.length;var i,j;for( i = 1;i<len;i++){//只有当前i的值比前面左边的小，才需要腾位置if(arr[i]<arr[i-1]){val = arr[i];for(j=i-1;j>=0&&val<arr[j];j--){arr[j+1]=arr[j];//腾位置}arr[j+1]=val;}}return arr
}
let arr = [2,1,4,6,5,3];
console.log(insertsort(arr));

4、希尔排序
是对直接插入排序的改进。

function shellsort(arr){let len = arr.length;let d=parseInt(len/2);let i,j;for(d;d>=1;d=parseInt(d/2)){for( i = d;i<len;i++){if(arr[i]<arr[i-d]){val = arr[i];for(j=i-d;j>=0&&val<arr[j];j-=d){arr[j+d]=arr[j];}arr[j+d]=val}}}return arr;
}
let arr = [8,4,5,7,1,3,6,2,4];
console.log(shellsort(arr));

5、折半插入排序
当low = high时最后一次进入while ,mid=low=high 最后只有两种情况：
1、arr[mid]>val ，val 应该在前面。也就是在mid的位置。此时经过if判断high = mid-1，left还是mid，left>high退出循环。,取mid=low=high+1。
2、arr[mid]<val， val应该在后面。也就是在mid+1的值位置。此时经过if判断，low=mid+1>,high还是mid，low>high退出循环。取mid+1 = low = high+1。
所以不管哪种情况，val的位置就是low，或者说是high+1。

function insertsort(arr){var len = arr.length;var low,high;var i,j;for( i = 1;i<len;i++){low = 0,high = i-1;let val = arr[i];while(low<=high){mid = Math.floor((low+high)/2);if(arr[mid]>val) high = mid-1;else low = mid+1;}//low的位置就是它该放的for( j=i-1;j>=low;j--){//腾出low值的位置arr[j+1]=arr[j];}arr[low]=val;}return arr
}
let arr = [2,1,4,6,5,3,1,2,6,8,4,9,7,3];
console.log(insertsort(arr));

6、归并排序
分而治之策略。
双重for循环
最差时间复杂度：O（nlogn）
平均时间复杂度：O（nlogn）
空间复杂度：O(n).

function mergesort(arr){let len = arr.length;//不断拆分至只有一个数if(len<=1) return arr;let mid=Math.floor(len/2);let left = arr.slice(0,mid);let right = arr.slice(mid);return merge(mergesort(left),mergesort(right))
}
//合并左右数组
function merge(leftarr,rightarr){let res = [];let i=0,j=0;while(i<leftarr.length&&j<rightarr.length){if(leftarr[i]<rightarr[j]){res.push(leftarr[i++]);}else{res.push(rightarr[j++]);}}//不知道哪个剩余，将剩余拼接return res.concat(leftarr.slice(i)).concat(rightarr.slice(j));}
let arr = [8,4,5,7,1,3,6,2];
console.log(mergesort(arr));

7、快速排序

最差时间复杂度：O（n^2）
平均时间复杂度：O（nlogn）
空间复杂度：O(nlogn).
不稳定

        function partition(arr,low,high){let pivot= arr[low];//基准while(low<high){//从右往左，右边是要大于pivot的while(low<high &&arr[high]>=pivot){high--;//满足大于pivot，继续往左}//当出现小于pivot的值，退出该while，并且要把该值放在左边。这时的high位置的值是要留给大于pivot的值arr[low]=arr[high];//暂存这个小于pivot的数， 原来的arr[low]值已经用pivot保存//开始从左往右，左边是要小于pivot的while(low<high&&arr[low]<=pivot){low++;//满足小于pivot，继续往右}//当出现大于pivot的值，退出该while，并且要把该值放在右边。这时的lowarr[high]=arr[low];//把该大于pivot的值放在第一个while留的位置。  }arr[low]=pivot;return low;}function quickSort(arr,left,right){if(left<right){var mid = partition(arr,left,right);  //确定划分中间位置quickSort(arr,left,mid-1);   //对左边部分进行递归quickSort(arr,mid+1,right);   //对右边部分进行递归}}var arr=[1,12,6,3,5,8,2,7,9];quickSort(arr,0,arr.length-1);console.log(arr);