【数据结构】排序算法---归并排序（动图演示）
文章目录
1. 定义
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：
- 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
- 自下而上的迭代；
2. 算法步骤
- 把长度为n的输入序列分成两个长度为n/2的子序列；
- 对这两个子序列分别采用归并排序；
- 将两个排序好的子序列合并成一个最终的排序序列。
3. 动图演示
4. 性质
稳定性：
归并排序是高效的基于比较的稳定排序算法。
空间复杂度：
归并排序可以只使用 O ( 1 ) O(1) O(1)大小的辅助空间，但为便捷通常使用与原数组等长的辅助数组。所以通常情况下空间复杂度为 O ( n ) O(n) O(n)
时间复杂度：
归并排序基于分治思想将数组分段排序后合并，时间复杂度在最优、最坏与平均情况下均为 O ( n l o g n ) O(nlogn) O(nlogn)。
5. 算法分析
和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O ( n l o g n ) O(nlogn) O(nlogn)的时间复杂度。代价是需要额外的内存空间。
6. 代码实现
C语言——迭代版
intmin(int x,int y){return x < y ? x : y;}voidmerge_sort(int arr[],int len){int*a = arr;int*b =(int*)malloc(len *sizeof(int));int seg, start;for(seg =1; seg < len; seg += seg){for(start =0; start < len; start += seg *2){int low = start, mid =min(start + seg, len), high =min(start + seg *2, len);int k = low;int start1 = low, end1 = mid;int start2 = mid, end2 = high;while(start1 < end1 && start2 < end2) b[k++]= a[start1]< a[start2]? a[start1++]: a[start2++];while(start1 < end1) b[k++]= a[start1++];while(start2 < end2) b[k++]= a[start2++];}int*temp = a; a = b; b = temp;}if(a != arr){int i;for(i =0; i < len; i++) b[i]= a[i]; b = a;}free(b);}C语言——递归版
voidmerge_sort_recursive(int arr[],int reg[],int start,int end){if(start >= end)return;int len = end - start, mid =(len >>1)+ start;int start1 = start, end1 = mid;int start2 = mid +1, end2 = end;merge_sort_recursive(arr, reg, start1, end1);merge_sort_recursive(arr, reg, start2, end2);int k = start;while(start1 <= end1 && start2 <= end2) reg[k++]= arr[start1]< arr[start2]? arr[start1++]: arr[start2++];while(start1 <= end1) reg[k++]= arr[start1++];while(start2 <= end2) reg[k++]= arr[start2++];for(k = start; k <= end; k++) arr[k]= reg[k];}voidmerge_sort(int arr[],constint len){int reg[len];merge_sort_recursive(arr, reg,0, len -1);}Python
defmergeSort(arr):import math if(len(arr)<2):return arr middle = math.floor(len(arr)/2) left, right = arr[0:middle], arr[middle:]return merge(mergeSort(left), mergeSort(right))defmerge(left,right): result =[]while left and right:if left[0]<= right[0]: result.append(left.pop(0))else: result.append(right.pop(0));while left: result.append(left.pop(0))while right: result.append(right.pop(0));return result Java
publicclassMergeSortimplementsIArraySort{@Overridepublicint[]sort(int[] sourceArray)throwsException{// 对 arr 进行拷贝，不改变参数内容int[] arr =Arrays.copyOf(sourceArray, sourceArray.length);if(arr.length <2){return arr;}int middle =(int)Math.floor(arr.length /2);int[] left =Arrays.copyOfRange(arr,0, middle);int[] right =Arrays.copyOfRange(arr, middle, arr.length);returnmerge(sort(left),sort(right));}protectedint[]merge(int[] left,int[] right){int[] result =newint[left.length + right.length];int i =0;while(left.length >0&& right.length >0){if(left[0]<= right[0]){ result[i++]= left[0]; left =Arrays.copyOfRange(left,1, left.length);}else{ result[i++]= right[0]; right =Arrays.copyOfRange(right,1, right.length);}}while(left.length >0){ result[i++]= left[0]; left =Arrays.copyOfRange(left,1, left.length);}while(right.length >0){ result[i++]= right[0]; right =Arrays.copyOfRange(right,1, right.length);}return result;}}C++——迭代版
template<typename T>// 整数或浮点数皆可使用,若要使用物件(class)时必须设定"小与"(<)的运算子功能voidmerge_sort(T arr[],int len){ T *a = arr; T *b = new T[len];for(int seg =1; seg < len; seg += seg){for(int start =0; start < len; start += seg + seg){int low = start, mid =min(start + seg, len), high =min(start + seg + seg, len);int k = low;int start1 = low, end1 = mid;int start2 = mid, end2 = high;while(start1 < end1 && start2 < end2) b[k++]= a[start1]< a[start2]? a[start1++]: a[start2++];while(start1 < end1) b[k++]= a[start1++];while(start2 < end2) b[k++]= a[start2++];} T *temp = a; a = b; b = temp;}if(a != arr){for(int i =0; i < len; i++) b[i]= a[i]; b = a;} delete[] b;}C++——递归版
voidMerge(vector<int>&Array,int front,int mid,int end){// preconditions:// Array[front...mid] is sorted// Array[mid+1 ... end] is sorted// Copy Array[front ... mid] to LeftSubArray// Copy Array[mid+1 ... end] to RightSubArray vector<int>LeftSubArray(Array.begin()+ front, Array.begin()+ mid +1); vector<int>RightSubArray(Array.begin()+ mid +1, Array.begin()+ end +1);int idxLeft =0, idxRight =0; LeftSubArray.insert(LeftSubArray.end(), numeric_limits<int>::max()); RightSubArray.insert(RightSubArray.end(), numeric_limits<int>::max());// Pick min of LeftSubArray[idxLeft] and RightSubArray[idxRight], and put into Array[i]for(int i = front; i <= end; i++){if(LeftSubArray[idxLeft]< RightSubArray[idxRight]){ Array[i]= LeftSubArray[idxLeft]; idxLeft++;}else{ Array[i]= RightSubArray[idxRight]; idxRight++;}}}voidMergeSort(vector<int>&Array,int front,int end){if(front >= end)return;int mid =(front + end)/2;MergeSort(Array, front, mid);MergeSort(Array, mid +1, end);Merge(Array, front, mid, end);}Go
funcmergeSort(arr []int)[]int{ length :=len(arr)if length <2{return arr } middle := length /2 left := arr[0:middle] right := arr[middle:]returnmerge(mergeSort(left),mergeSort(right))}funcmerge(left []int, right []int)[]int{var result []intforlen(left)!=0&&len(right)!=0{if left[0]<= right[0]{ result =append(result, left[0]) left = left[1:]}else{ result =append(result, right[0]) right = right[1:]}}forlen(left)!=0{ result =append(result, left[0]) left = left[1:]}forlen(right)!=0{ result =append(result, right[0]) right = right[1:]}return result }结语
今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下。
也可以点点关注，避免以后找不到我哦！
Crossoads主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是作者前进的动力！
带你初步了解排序算法：https://blog.ZEEKLOG.net/2301_80191662/article/details/142211265
直接插入排序：https://blog.ZEEKLOG.net/2301_80191662/article/details/142300973
希尔排序：https://blog.ZEEKLOG.net/2301_80191662/article/details/142302553
直接选择排序：https://blog.ZEEKLOG.net/2301_80191662/article/details/142312028
堆排序：https://blog.ZEEKLOG.net/2301_80191662/article/details/142312338
冒泡排序：https://blog.ZEEKLOG.net/2301_80191662/article/details/142324131
快速排序：https://blog.ZEEKLOG.net/2301_80191662/article/details/142324307
归并排序：https://blog.ZEEKLOG.net/2301_80191662/article/details/142350640
计数排序：https://blog.ZEEKLOG.net/2301_80191662/article/details/142350741
桶排序：https://blog.ZEEKLOG.net/2301_80191662/article/details/142375338
基数排序：https://blog.ZEEKLOG.net/2301_80191662/article/details/142375592
十大经典排序算法总结与分析：https://blog.ZEEKLOG.net/2301_80191662/article/details/142211564
