function shellSort(arr){ var gap=Math.floor(arr.length/2); while(gap>0){ for(var i=gap;i<arr.length;i++){ temp=arr[i]; for(var j=i;j>=gap&&arr[j-gap]>temp;j-=gap){ arr[j]=arr[j-gap]; } arr[j]=temp; } gap=Math.floor(gap/2); } return arr; } var arr = [2,3,6,4,2,1,90,100,20,5]; console.log(shellSort(arr)); //[1, 2, 2, 3, 4, 5, 6, 20, 90, 100]
归并排序
原理：
归并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
有以下几个步骤：
1、把长度为n的输入序列分成两个长度为n/2的子序列;
2、对这两个子序列继续分为m/2的子序列，一直分下去
3、将两个排序好的子序列合并成一个最终的排序序列。
再来一张静态图，比较好理解
这里需要补充是，归并中对数组的分割是从上往下的，归并中数组的比较是从下往上的。
特点：
速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列.
属于分治思想，递归归并
代码实现：
/* 排序并合并*/ function merge(left, right) { var re = []; while(left.length > 0 && right.length > 0) { if(left[0] < right[0]) { // 如果左边的数据小于右边的数据，将左边的数据取出，放到新数组那里 re.push(left.shift()); } else { re.push(right.shift()); } } /* 当左右数组长度不等.将比较完后剩下的数组项链接起来即可 */ return re.concat(left).concat(right); } function mergeSort(arr) { if(arr.length == 1){ return arr; } /* 首先将无序数组划分为两个数组 */ var mid = Math.floor(arr.length / 2); var left = arr.slice(0, mid); var right = arr.slice(mid); /* 递归分别对左右两部分数组进行排序合并 */ return merge(mergeSort(left), mergeSort(right)); } var arr=[2,3,6,4,2,1,90,100,20,5]; console.log(mergeSort(arr)); // [1, 2, 2, 3, 4, 5, 6, 20, 90, 100]
快速排序
原理：
1、在数据集之中，选择一个元素作为"基准"（pivot）。比如选择下面数字45
2、所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
3、对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
特点：速度最快。和归并排序不同的是，归并排序是先分为两组再继续排，而快速排序是边分边排
代码实现：
// 大致分三步： // 1、找基准（一般是以中间项为基准） // 2、遍历数组，小于基准的放在left，大于基准的放在right // 3、递归 function quickSort(arr){ //如果数组<=1,则直接返回 if(arr.length<=1){ return arr; } var pivotIndex=Math.floor(arr.length/2); //找基准，并把基准从原数组删除 var pivot=arr.splice(pivotIndex,1)[0]; //定义左右数组 var left=[]; var right=[]; //比基准小的放在left，比基准大的放在right for(var i=0;i<arr.length;i++){ if(arr[i]<=pivot){ left.push(arr[i]); }else{ right.push(arr[i]); } } //递归 return quickSort(left).concat([pivot],quickSort(right)); } var arr=[2,3,6,4,2,1,90,100,20,5]; console.log(quickSort(arr)); // [1, 2, 2, 3, 4, 5, 6, 20, 90, 100]
选择排序