【图解算法】归并排序
✊不积跬步，无以至千里；不积小流，无以成江海。
木偶人 mouu
读完需要
速读仅需 3 分钟
思路
1.将n个元素分成两个含n/2元素的子序列（左边可能比右边多1个数），直到拆分的每个数组只包含一个元素。
2.从最底层开始逐步合并两个排好序的数列。
图解
归并排序
算法分析
复杂度分析
归并排序算法每次将序列折半分组，共需要logn轮，因此归并排序算法的时间复杂度是O(nlogn)。不管是有序还是无序都需要拆分数组，进行前后比较，所以最好和最坏时间复杂度是一样的都是O(nlogn)。
合并数组需要放在新的数组中，借助额外的空间，所以空间复杂度是O(n)。
稳定性分析
因为拆分数组是按照对半拆分，元素前后顺序没有改变，排序也是从前到后，对比前后顺序也是没变，所以稳定。
代码
public static void mergeSort(int[] arr, int first, int last){
if(null == arr || arr.length < 0 || first == last){
return;
}
mergeSort(arr, first, (last + first)/2);
mergeSort(arr, (last + first)/2 + 1, last);
sort(arr, first, (last + first)/2, last);
}
//这个方法是合并两个有序数组，就好像直接插入排序算法一样
public static void sort(int[] arr, int first, int mid, int last ){
int[] temp = new int[last - first + 1];
int i = 0;
int j = 0;
int index = 0;
while(i < mid - first + 1 && j < last - mid){
if(arr[first + i] >= arr[mid + 1 + j]){
temp[index] = arr[mid + 1 + j];
j++;
index++;
} else {
temp[index] = arr[first + i];
i++;
index++;
}
}
while(i < mid - first + 1){
temp[index] = arr[first + i];
index++;
i++;
}
while(j < last - mid){
temp[index] = arr[mid + 1 + j];
index++;
j++;
}
for(int k = first, n = 0; k <= last; k++, n++){
arr[k] = temp[n];
}
}
public static void main(String[] args) {
int[] arr=new int[]{123,45,6,22,99,1,38,41,-6,0};
//归并排序
mergeSort(arr,0,9);
System.out.println("归并排序后的结果是:");
System.out.println(Arrays.toString(arr));
}总结
时间复杂度
最小时间复杂度是O(nlogn)
最大时间复杂度是O(nlogn)
平均时间复杂度是O(nlogn)
空间复杂度
O(n)
稳定性分析度
稳定