将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段之间有序。将两个有序表合并成一个有序表，称为二路归并。
将待排序序列R[0...n-1]看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复，最后得到一个长度为n的有序序列。
归并排序需要做两件事：
1）分解：将序列每次折半划分
2）合并：将划分后的序列段两两合并后排序
如何合并？
在每次合并过程中，都是对两个有序的序列段进行合并，然后再排序。这两个有序的序列段分别为R[low, mid]和R[mid+1, high]，先将它们合并到一个局部的暂存数组R2中，待合并完成后再将R2复制回R中。
每次从两个段中取出一个记录进行关键字的比较，将较小者放入R2中，最后将各段中余下的部分直接复制到R2中。经过这样的过程，R2已经是一个有序的序列，再将其复制回R中，一次合并排序就完成了。
在某趟归并中，设各子表的长度为gap，则归并前R[0...n-1]中共有n/gap个有序的子表：R[0...gap-1], R[gap...2*gap-1], ... , R[(n/gap)*gap ... n-1]。
在将相邻的子表归并时，需要对表的特殊情况进行处理：
1）若子表个数为奇数，最后一个子表无须和其他子表归并（即本趟处理轮空）；
2）若子表个数为偶数，到最后一对子表中后一个子表区间的上限为n-1；
时间复杂度： 归并排序的形式就是一棵二叉树，需要遍历的次数就是二叉树的深度，时间复杂度是O(nlogn)。
空间复杂度： 算法处理过程中，需要一个大小为n的临时存储空间用来保存合并序列。
算法稳定性： 在归并排序中，相等元素的顺序不会改变，所以它是稳定的算法。
总结：
1）时间复杂度：O(nlogn)
2）空间复杂度：O(n)
3）稳定性：稳定
4）复杂性：较复杂
1）空间复杂度考虑：选择优先级为[堆排序>快速排序>归并排序]。
2）稳定性考虑：应选归并排序，堆排序和快速排序都是不稳定的。
3）平均排序速度考虑：应选快速排序。
import java.util.Arrays
/**
* 归并排序
* 效率O（nlogn），归并的最佳、平均和最糟用例效率之间没有差异，适用于排序大列表，基于分治法。
*/
public class MergeSort {
public static void main(String[] args) {
int[] array = {9, 1, 5, 3, 4, 2, 6, 8, 7}
MergeSort merge = new MergeSort()
System.out.println("排序前:"+Arrays.toString(array))
merge.sort(array)
System.out.println("排序后:"+Arrays.toString(array))
}
private static int[] sort(int[] list){
for(int gap = 1gap <list.lengthgap = 2*gap){
MergePass(list,gap,list.length)
System.out.println("gap="+gap+":"+Arrays.toString(list))
}
return list
}
private static void MergePass(int[] arr,int gap,int length){
int i=0
// 归并gap长度的两个相邻子表
for(i=0i+2*gap-1 <lengthi = i+2*gap){
Merge(arr, i, i + gap - 1, i + 2 * gap - 1)
}
// 余下两个子表，后者长度小于gap
if (i + gap - 1 <length) {
Merge(arr, i, i + gap - 1, length - 1)
}
}
private static void Merge(int[] arr,int low,int mid,int high){
int i=low// i是第一段序列的下标
int j = mid +1// j是第二段序列的下标
int k = 0// k是临时存放合并序列的下标
int[] array2 = new int[high - low + 1]// array2是临时合并序列
// 扫描第一段和第二段序列，直到有一个扫描结束
while (i <= mid &&j <= high) {
// 判断第一段和第二段取出的数哪个更小，将其存入合并序列，并继续向下扫描
if (arr[i] <= arr[j]) {
array2[k] = arr[i]
i++
k++
} else {
array2[k] = arr[j]
j++
k++
}
}
// 若第一段序列还没扫描完，将其全部复制到合并序列
while(i <= mid){
array2[k] = arr[i]
i++
k++
}
// 若第二段序列还没扫描完，将其全部复制到合并序列
while(j <= high){
array2[k] = arr[j]
j++
k++
}
// 将合并序列复制到原始序列中
for (k = 0, i = lowi <= highi++, k++) {
arr[i] = array2[k]
}
}
}
运行结果:
排序前: 9 1 5 3 4 2 6 8 7
gap = 1: 1 9 3 5 2 4 6 8 7
gap = 2: 1 3 5 9 2 4 6 8 7
gap = 4: 1 2 3 4 5 6 8 9 7
gap = 8: 1 2 3 4 5 6 7 8 9
排序后: 1 2 3 4 5 6 7 8 9
以var a = [4,2,6,3,1,9,5,7,8,0]为例子。1.希尔排序。 希尔排序是在插入排序上面做的升级。是先跟距离较远的进行比较的一些方法。
function shellsort(arr){ var i,k,j,len=arr.length,gap = Math.ceil(len/2),tempwhile(gap>0){ for (var k = 0k <gapk++) { var tagArr = []tagArr.push(arr[k]) for (i = k+gapi <leni=i+gap) { temp = arr[i] tagArr.push(temp) for (j=i-gapj >-1j=j-gap) { if(arr[j]>temp){ arr[j+gap] = arr[j]}else{ break} } arr[j+gap] = temp} console.log(tagArr,"gap:"+gap)//输出当前进行插入排序的数组。 console.log(arr)//输出此轮排序后的数组。 } gap = parseInt(gap/2)} return arr }
过程输出：
[4, 9] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [2, 5] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [6, 7] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [3, 8] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [1, 0] "gap:5" [4, 2, 6, 3, 0, 9, 5, 7, 8, 1] [4, 6, 0, 5, 8] "gap:2" [0, 2, 4, 3, 5, 9, 6, 7, 8, 1] [2, 3, 9, 7, 1] "gap:2" [0, 1, 4, 2, 5, 3, 6, 7, 8, 9] [0, 1, 4, 2, 5, 3, 6, 7, 8, 9] "gap:1" [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
由输出可以看到。第一轮间隔为5。依次对这些间隔的数组插入排序。
间隔为5：
[4, 9] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [2, 5] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [6, 7] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [3, 8] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [1, 0] "gap:5" [4, 2, 6, 3, 0, 9, 5, 7, 8, 1] [4, 6, 0, 5, 8] "gap:2" [0, 2, 4, 3, 5, 9, 6, 7, 8, 1] [2, 3, 9, 7, 1] "gap:2" [0, 1, 4, 2, 5, 3, 6, 7, 8, 9] [0, 1, 4, 2, 5, 3, 6, 7, 8, 9] "gap:1" [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
间隔为2：
[4, 2, 6, 3, 0, 9, 5, 7, 8, 1]4 6 0 5 8 2 3 9 7 1
排序后：
[0, 1, 4, 2, 5, 3, 6, 7, 8, 9]
间隔为1：
排序后：
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]。
2.快速排序。把一个数组以数组中的某个值为标记。比这个值小的放到数组的左边，比这个值得大的放到数组的右边。然后再递归 对左边和右边的数组进行同样的操作。直到排序完成。通常以数组的第一个值为标记。
代码:
function quickSort(arr){ var len = arr.length,leftArr=[],rightArr=[],tagif(len<2){ return arr} tag = arr[0]for(i=1i<leni++){ if(arr[i]<=tag){ leftArr.push(arr[i]) }else{ rightArr.push(arr[i]) } } return quickSort(leftArr).concat(tag,quickSort(rightArr)) }
3.归并排序。把一系列排好序的子序列合并成一个大的完整有序序列。从最小的单位开始合并。然后再逐步合并合并好的有序数组。最终实现归并排序。
合并两个有序数组的方法：
function subSort(arr1,arr2){var len1 = arr1.length,len2 = arr2.length,i=0,j=0,arr3=[],bArr1 = arr1.slice(),bArr2 = arr2.slice() while(bArr1.length!=0 || bArr2.length!=0){ if(bArr1.length == 0){ arr3 = arr3.concat(bArr2)bArr2.length = 0 }else if(bArr2.length == 0){ arr3 = arr3.concat(bArr1)bArr1.length = 0 }else{ if(bArr1[0]<=bArr2[0]){ arr3.push(bArr1[0]) bArr1.shift()}else{ arr3.push(bArr2[0]) bArr2.shift()} } } return arr3 }
归并排序：
function mergeSort(arr){ var len= arr.length,arrleft=[],arrright =[],gap=1,maxgap=len-1,gapArr=[],glen,nwhile(gap<maxgap){ gap = Math.pow(2,n) if(gap<=maxgap){ gapArr.push(gap) } n++} glen = gapArr.lengthfor (var i = 0i <gleni++) { gap = gapArr[i] for (var j = 0j <lenj=j+gap*2) { arrleft = arr.slice(j, j+gap)arrright = arr.slice(j+gap,j+gap*2)console.log("left:"+arrleft,"right:"+arrright)arr = arr.slice(0,j).concat(subSort(arrleft,arrright),arr.slice(j+gap*2)) } } return arr }
排序[4,2,6,3,1,9,5,7,8,0]输出：
left:4 right:2 left:6 right:3 left:1 right:9 left:5 right:7 left:8 right:0 left:2,4 right:3,6 left:1,9 right:5,7 left:0,8 right: left:2,3,4,6 right:1,5,7,9 left:0,8 right: left:1,2,3,4,5,6,7,9 right:0,8
看出来从最小的单位入手。
第一轮先依次合并相邻元素：4,2 6,31,95,78,0
合并完成之后变成： [2,4,3,6,1,9,5,7,0,8]
第二轮以2个元素为一个单位进行合并：[2,4],[3,6] [1,9],[5,7] [0,8],[]
合并完成之后变成：[2,3,4,6,1,5,7,9,0,8]
第三轮以4个元素为一个单位进行合并：[2,3,4,6],[1,5,7,9] [0,8],[]
合并完成之后变成： [1,2,3,4,5,6,7,9,0,8]
第四轮以8个元素为一个单位进行合并： [1,2,3,4,5,6,7,9],[0,8]
合并完成。 [0,1,2,3,4,5,6,7,8,9]
可以实现比较器Comparator来定制排序方案，同时使用Colletions.sort的方式进行排序，代码如下：
public void sortDesc(List<Long>s){
Collections.sort(s, new Comparator<Long>() {
public int compare(Long o1, Long o2) {
Long result = o2 - o1
return result.intValue()
}
})
s.forEach(item->{
System.out.print(item +" ")
})
}
同时常用的比较排序算法主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。
java的冒泡排序实现如下：
public static void bubbleSort(int []arr) { for(int i =0i<arr.length-1i++) { for(int j=0j<arr.length-i-1j++) {//-1为了防止溢出 if(arr[j]>arr[j+1]) { int temp = arr[j] arr[j]=arr[j+1] arr[j+1]=temp } } } }还有非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等。
