其他排序

基数排序

堆排序

插入排序和希尔排序

快速排序

冒泡排序和选择排序

归并排序

前备知识：如果数组中只有一个数，那么这个数组一定是有序的！

核心思想：将两个有序的数组合并为一个有序的数组(运用了分组的思想：递归)

实现过程：对于如下数组进行归并排序，过程如下：

如上所示，由于归并排序是将两个有序的数组合并为一个有序的数组，因此我们首先是对上述数组进行拆分，数组长度为nLen = 9，因此将数组均分为nLen/2 = 4，拆分后如下图所示：

如上图所示，经过一次折半将数组拆分为了两个数组，由于归并排序的思想是将两个有序的数组进行合并，因此我们需要继续对数组进行拆分，拆分后如下图所示：

如上图所示，数组基于上次两个数组拆分为了4个数组，下面四个数组中有的有两个元素，有的有三个元素，而且有些数组我们看起来他们已经是有序的，但是计算机并不知道他们是否有序，只有遍历一遍才会知道，但是遍历数组显然不是我们排序的目的，因此我们需要进一步拆分，最终将数组拆分后的图如下：

我们知道，当数组只有一个元素时，一定是有序的，而归并排序就是将两个有序的数组合并成一个有序的数组。因此，我们将拆分后的数组进行合并，如下图所示：

如上所示，我们将最后一层的数进行了合并，之后再对上一层合并，依次进行，如下图所示：

继续回溯上一层合并

继续回溯上一层合并…

如上图所示，当返回第一层的时候，数组已经排好序。我们从归并的过程可以看出，归并的过程就是一个递归的过程，先递归将数组拆分，拆分到最小后将数组合并，合并后回溯。

代码实现

#include <stdio.h>#include <stdlib.h>void Print(int arr[],int nLen){if(arr == NULL || nLen <= 0) return;for(int i = 0;i < nLen;i++){printf("%d\t",arr[i]);}printf("\n");}void Merge(int arr[],int nBegin1,int nEnd1,int nBegin2,int nEnd2){if(arr == NULL || nBegin1 > nEnd1 || nBegin2 > nEnd2)return;int nLen = nEnd2 - nBegin1 + 1;int *parr = (int *)malloc(sizeof(int)*nLen);int nIndex = nBegin1;int i = 0;//合并while(nBegin1 <= nEnd1 && nBegin2 <= nEnd2){if(arr[nBegin1] <= arr[nBegin2]){parr[i++] = arr[nBegin1++];}else{parr[i++] = arr[nBegin2++];}}while(nBegin1 <= nEnd1){parr[i++] = arr[nBegin1++];}while(nBegin2 <= nEnd2){parr[i++] = arr[nBegin2++];}for(i = 0;i < nLen;i++){arr[nIndex++] = parr[i];}free(parr);parr = NULL;}void MergeSort(int arr[],int nBegin,int nEnd){if(arr == NULL || nBegin >= nEnd)return ;int nMid = nBegin + (nEnd - nBegin)/2;//折半//左MergeSort(arr,nBegin,nMid);//右MergeSort(arr,nMid+1,nEnd);//合并Merge(arr,nBegin,nMid,nMid+1,nEnd);}int main(){int arr[] = {3,67,287,9,3,9,23,56,7};MergeSort(arr,0,sizeof(arr)/sizeof(arr[0])-1);Print(arr,sizeof(arr)/sizeof(*arr));return 0 ;}

最好时间复杂度：O(nlogn)

最坏时间复杂度：O(nlogn)

平均时间复杂度：O( nlogn）

空间复杂度：O(n)

稳定性：稳定

适用场合：数组量大且较无序