排序的概念
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次 序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
一、常见的排序算法
我们根据排序的思想可分为4大类排序：
插入排序：插入排序又有直接插入排序和希尔排序
选择排序：选择排序和堆排序
交换排序：冒泡排序和快速排序
归并排序：归并排序
二、代码实现
在这里给一个力扣链接用来帮助大家测试自己的排序的性能好坏
力扣链接：力扣
接下来我们就开始实现这些排序，首先是直接插入排序：
如上图所示就是直接插入的单趟排序，而完整的排序只需要让end从要排序的数组的第一个数开始依次实现上面的操作即可。
void InsertSort(int* a, int n) { for (int i = 0; i < n - 1; i++) { int end = i; int tmp = a[end + 1]; while (end >= 0) { if (a[end] > tmp) { a[end + 1] = a[end]; end--; } else { break; } } a[end + 1] = tmp; } }
在这里可能会有人疑惑，为什么循环条件中i<n-1，原因是我们每次要保存end的后一个数，如果i<n那么i的后一个数并不存在tmp在保存的时候就会越界。可能光看代码会有人看不懂，下面我们画图演示一遍：
下面我们来分析一下直接插入排序的时间复杂度和空间复杂度以及稳定性。我们可以发现最坏的情况是一共N个数，end在交换的时候每个数都要挪动，所以时间复杂度为O（N^2）,空间复杂度很明显为O（1）因为我们是在原数组移动并没有开辟空间。那么直接插入排序是否稳定呢？答案是稳定，我们已经说过了，稳定性是指相同的数在排序完后他们的相对顺序不变也就是说一个数组有两个5，排序完后这两个5的相对顺序要和没排序之前的顺序一样。而插入排序每次是将大的数往后插入并不会改变相同数的相对顺序所以是稳定的。
希尔排序：
希尔排序与插入排序的区别在于希尔排序会先进行预排序，我们从上面的直接排序可以看出当一个序列大部分是有序的时候用直接排序会非常快，因为在不需要移动的时候我们直接break跳出循环了，那么这个时候预排序的优势就体现出来了，通过预排序将一个序列中大部分数变成有序的然后再直接排序就会省下更多的时间。
代码如下：
void ShellSort(int* a, int n) { int gap = n; while (gap > 1) { gap = gap / 3 + 1; for (int i = 0; i < n - gap; i++) { int end = i; int tmp = a[end + gap]; while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } } }
如图所示是将整个数组4个为一组进行预排序的图，后面2个一组的与之相同就不画了，从图中我们可以发现为什么for循环里的条件是i<n-gap，因为整个数组并不是都能按照gap进行平均分配，一定会有有些数没有分组的情况，这个时候等待gap变成新的个数为一组的时候就可以分配到上次没预排序的数，如果没有这个条件那么i走到后面就会发生很多的越界。然后我们再来看gap的设定，从代码中我们可以看到我将gap定为n，当gap大于1就进行预排序，进来后让gap/3+1，这里为什么要+1呢？因为我们除到最后一定要让gap最后一次是1，我们可以发现当gap为1 的时候就是直接排序，所以这个gap设定的时候只要能保证最后一次为1即可。我们也可以让gap/2，这样的话最后一次一定是1，希尔排序中与直接插入排序不同的地方就在于希尔排序的预排序，只要理解了预排序那么就很简单的写出希尔排序了。当然我们在预排序的时候一定要把end放到end+gap的位置并且放完后让end-gap这样才能保证最后一次将tmp里的数放到end+gap的位置，这些地方其实拿直接排序来看就是将end+1变成了end+gap而已。下面我们来分析一下希尔排序的时间复杂度和空间复杂度以及稳定性。希尔排序的时间复杂度很难就计算所以我们就直接引用《数据结构-用面相对象方法与C++描述》--- 殷人昆书中的话：
然后我们给出希尔排序时间复杂度为O(n^1.3)，希尔排序也是在原数组中进行排序所以空间复杂度为O(1)，那么希尔排序稳定吗？答案是不稳定，因为在预排序阶段就把相同数的相对顺序打乱了所以不稳定。
选择排序：
选择排序就是每次在数组中选一个大的数或者一个小的数然后放在数组第一个位置或者最后一个位置，然后缩小区间再继续刚才的动作。由于选择排序相对简单并且容易理解所以我们直接上代码，我们写出的是每次遍历的时候直接找出最大的和最小的这样效率上能有些提升。
代码如下：
void swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } void SelectSort(int* a, int n) { int begin = 0; int end = n - 1; while (begin < end) { int min = begin; int max = begin; for (int i = begin; i <= end; i++) { if (a[i] < a[min]) { min = i; } if (a[i] > a[max]) { max = i; } } swap(&a[begin], &a[min]); if (max == begin) { max = min; } swap(&a[end], &a[max]); begin++; end--; } }
我们需要注意的是在遍历数组找最大最小数的时候一定保存的是下标而不是这个数，如果保存数字的话会有很多的麻烦，比如说会缺失数据，因为我们交换是数组里的数交换，当你直接保存的是数字本身而不是下标的时候交换的就是max或min变量本身和数组中的数而不是数组中的两个数交换。我们遍历一遍数组后找到最大的数的下标和最小的数的下标然后把最小的数和begin位置交换，在这里要注意一个细节，很有可能第一个数就是最大的数这个时候max指向的是begin位置，而我们先将begin和min交换了这个时候最大的数就到了min位置，所以我们需要用if判断语句来将max的位置修正，然后再将最大的数和end位置交换，然后缩小区间即可。当begin==end的时候循环结束所有数都排序完成。这个时候我们来看一下选择排序的时间复杂度，一共n个数每次进入都需要遍历一遍数组找到最大或最小的数，虽然到最后区间会越来越小但是时间复杂度是最坏的情况所以时间复杂度为O（n^2）,由于是在数组上进行排序所以空间复杂度为O（1）并没有额外开辟空间。那么选择排序稳定吗？答案是不稳定，原因如下图：
堆排序：
堆排序我们在前面的文章中详细的讲解了，这里就大致说一下即可。堆排序升序要建大堆，因为大堆堆顶元素是最大的，每次将堆顶元素和最后一个元素交换，这样最大的数就到了最后一个，然后从堆顶元素开始向下调整，调整后的堆顶元素就变成了堆中第二大的元素，然后让总数--这样下一次交换就是倒数第二个位置堆顶元素交换，就排好了最大和第二大的数然后依次类推即可。
void swap(HPDataType* p1, HPDataType* p2) { HPDataType tmp = *p1; *p1 = *p2; *p2 = tmp; } AdjustDown(HPDataType* a, int n, int parent) { int child = 2 * parent + 1; while (child < n) { if ((child+1) < n && a[child + 1] < a[child]) { child++; } if (a[parent] > a[child]) { swap(&a[parent], &a[child]); parent = child; child = 2 * parent + 1; } else { break; } } } //向下调整建堆 void HeapCreat(Heap* ps, HPDataType* a, int n) { assert(ps); ps->a = (HPDataType*)malloc(sizeof(HPDataType) * n); if (ps->a == NULL) { perror("malloc:"); exit(-1); } memcpy(ps->a, a, sizeof(HPDataType) * n); ps->capcity = ps->size = n; int end = n - 1; for (int i = (end - 1) / 2; i >= 0; i--) { AdjustDown(ps->a, n, i); } } void HeapSortUp(Heap* ps,HPDataType* a, int n) { //升序建大堆 降序建小堆 HeapCreat(ps, a, n); int end = n - 1; while (end > 0) { swap(&ps->a[0], &ps->a[end]); AdjustDown(ps->a, end, 0); end--; } }
由于在之前的文章中有很详细的介绍堆，所以有不懂的可以去看看前面的文章，这里我们讲解了一下思路就跳过了。那么堆排序的时间复杂度为多少呢？由于堆本质上是完全二叉树，二叉树的高度为2^0~2^h-1，通过计算可得时间复杂度为O（N*logN）,并没有额外开辟空间所以空间复杂度为O（1），那么稳定吗？答案是不稳定，因为堆排序每次都要向下调整在调整的过程中就会打乱相同数的相对顺序，所以不稳定。
冒泡排序：
冒泡排序相信对每个人来说都不陌生，这里我们就直接上代码了。
void swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } void BubbleSort(int* a, int n) { for (int i = 0; i < n - 1; i++) { int flag = 0; for (int j = 0; j < n - 1 - i; j++) { if (a[j] > a[j + 1]) { swap(&a[j], &a[j + 1]); flag = 1; } } if (flag == 0) { break; } } }
在这里我们稍加进行了改进，每进行一趟冒泡排序的时候我们都用flag去判断是否已经有序，如果整个数组都没有交换过那么就说明这个数组是有序的那么直接退出循环即可。我们可以看到最外面那层循环为n-1，这是为什么？因为如果有10个数排序，我们进行9趟冒泡排序就排好了9个数剩下一个数因为那9个数的移动自己就会排好，所以只需要n-1趟即可，在内层循环中，我们每排好一个数就要减少一次循环的次数所以是n-1-i。下面我们来看一下冒泡排序的时间复杂度，按最坏的情况，要进行n-1趟排序，每个数都要去比较一共n个数，所以冒泡排序的时间复杂度为O(n^2),空间复杂度为O（1）。那么冒泡排序稳定吗？答案是稳定，因为冒泡排序只有前面的小于后面的才交换是不影响相同数的相对顺序的。
快速排序：
快速排序的核心内容有三个版本，我们就都讲解一遍，这三个版本分别是霍尔，挖坑，双指针法。
注意：这里的三个版本只是单趟排序的思想不同，其他都一样。
我们先来讲解霍尔版本的。首先让left指向数组的最左边，让right指向数组的最右边，然后选左边的作为Key，这个Key也可以是右边，如果是左边那么等会就让右边先走，如果是右边那就要让左边先走，这样可以保证最后Key的左边为比K小的，Key的右边为比K大的。
上图就是一趟快速排序的过程，我们发现一趟结束后key左边的都比key小，key右边的都比key大，那么下一趟我们只需要在重复刚刚的步骤去排key左边的区间和key右边的区间，很多人问为什么不排key了，打个比方 312 6 987 我们可以发现只需要排6左边的和6右边的这个序列就有序了。那么既然每次都要排序这个数组的左右区间那我们很自然的就想到了递归，在什么情况下左右就排好序了不需要再递归了呢？当只有一个数的时候不需要再递归了因为一个数就是有序的。下面我们就附上完整的代码：
void QuickSort(int* a, int begin, int end) { if (begin >= end) { return; } int left = begin; int right = end; int key = left; while (left < right) { //左边为K让右边先走，右边找到小于K的停下 while (left < right && a[right] >= a[key]) { right--; } //右边找到小后停下让左边走去找比K大的然后交换 while (left < right && a[left] <= a[key]) { left++; } swap(&a[left], &a[right]); } //当left==right时两个下标相遇然后让相遇点和key交换，然后相遇点变成新的K swap(&a[left], &a[key]); key = left; QuickSort(a, begin, key - 1); QuickSort(a, key + 1, end); }
下面我们画一下此代码的递归展开图：
看不清的可以对照上图看下面的图：
通过递归展开图我们应该可以清楚的理解快速排序是如何将一段乱序数字排成有序的，需要注意的点是每次右边走的时候或者左边走的时候循环条件内必须加上left<right，因为在走的时候left和right的下标发生了变化，如果右边找小然后左边没有小的数的时候没有left<right的限制就会发生越界，并且我们找小或者找大一定是真小，不可以是等于，如果在循环条件内，没有加上等于就会造成碰到与Key相等的数的时候就停下了。
挖坑法：
挖坑法的思想是让一个变量去保存key值，然后我们假设左边第一个位置为坑，当然也可以右边第一个位置为坑，但是一定要相反的方向先走。刚刚我们假设第一个位置为坑，然后我们让右边先走去找比key小的，找到后把这个位置的数据填入坑中，然后这个位置变成新的坑，再让左边走去找比K大的，找到后把这个位置的数放入新的坑中然后这个位置再变成坑，当left==right的时候这个位置一定是坑，只需要将key放入这个位置即可。
如上图所示就是挖坑法的思想，这个思想适合不太理解霍尔的那个方法的人。下面是挖坑法的代码：
void QuickSort2(int* a, int begin, int end) { if (begin >= end) { return; } int left = begin; int right = end; int key = a[left]; int hole = left; while (left < right) { //左边为坑让右边先走，右边找到小于K的放到坑里然后让自己变成新的坑 while (left < right && a[right] >= key) { right--; } a[hole] = a[right]; hole = right; //左边走去找比K大的然后填入坑自己变成新的坑 while (left < right && a[left] <= key) { left++; } a[hole] = a[left]; hole = left; } //当left==right时两个下标相遇相遇点就是坑，把key放到坑里 a[hole] = key; QuickSort2(a, begin, hole - 1); QuickSort2(a, hole + 1, end); }
我们可以看到与霍尔的版本差距并不是很大，主要在于单趟排序的不同，最后递归的时候都是去递归相遇点前面的区间和相遇点后面的区间。
双指针法：
双指针法其实并不是指针只是两个下标，但是此方法是单趟排序中最为简单的，其本质就是将大于key的数往后推。我们定义两个下标一个是prev 一个是cur，prev每次从数组最左边开始，cur为prev+1的位置，然后让cur去找比Key小的数，当找到后让prev先++然后与cur位置的数据进行交换，然后cur再开始找比key小的，当cur超过数组大小的时候循环结束。然后把prev位置和key进行交换即可。以下为示意图：
我们可以看到排完后key的左边都是小于key的，key的右边都是大于key的。
void QuickSort3(int* a, int begin, int end) { if (begin >= end) { return; } int prev = begin; int cur = begin + 1; int key = begin; while (cur <= end) { //当cur小于key并且cur和prev指向的不是同一个位置的时候就交换（因为同一个位置交换没意义） if (a[cur] < a[key] && ++prev != cur) { swap(&a[cur], &a[prev]); } cur++; } //当cur越界就把prev和key位置数据交换 swap(&a[key], &a[prev]); QuickSort3(a, begin, prev - 1); QuickSort3(a, prev + 1, end); }
我们从代码就可以看出此方法的简洁，刚刚从示意图中我们可以看到如果一开始cur就是比key小的那么prev++后与cur在同一个位置是不需要交换的。if (a[cur] < a[key] && ++prev != cur)这串代码的意思是一旦cur小于key为真就会继续判断++prev!=cur这个语句，因为是前置++只要cur小于key那么prev就会++往后走一步，即使++prev != cur这条语句为假不进行交换prev也会++。
快排的三个单趟循环讲完了下面我们再来讲解一下如何改进快速排序让快速排序的效率更高。一共两个方法，一个是小区间优化的方法，另一个是三数取中的方法，这两个方法可以同时放到快速排序中进行优化。
小区间优化：
相信大家都知道，算法只有在数据量很大很大的时候才能明显看出差距，当我们要排序的数据量很小的时候我们不需要"杀鸡用牛刀"直接用适应性很强的插入排序去排这些小区间即可，为什么说插入排序的适应性很强呢？因为插入排序在大多数数据是有序的情况下排的会非常快，希尔排序就是根据这个来改进的让效率变得很高。那么我们直接上代码：
void InsertSort(int* a, int n) { for (int i = 0; i < n - 1; i++) { int end = i; int tmp = a[end + 1]; while (end >= 0) { if (a[end] > tmp) { a[end + 1] = a[end]; end--; } else { break; } } a[end + 1] = tmp; } } void QuickSort3(int* a, int begin, int end) { if (begin >= end) { return; } if ((begin + end + 1) < 15) { InsertSort(a, begin + end + 1); } else { int prev = begin; int cur = begin + 1; int key = begin; while (cur <= end) { //当cur小于key并且cur和prev指向的不是同一个位置的时候就交换（因为同一个位置交换没意义） if (a[cur] < a[key] && ++prev != cur) { swap(&a[cur], &a[prev]); } cur++; } //当cur越界就把prev和key位置数据交换 swap(&a[key], &a[prev]); QuickSort3(a, begin, prev - 1); QuickSort3(a, prev + 1, end); } }
为什么是begin+end+1呢？因为begin到end是闭区间比如10个数那么闭区间为0-9，所以还要加上1才是真实的数据个数，当数组里的数据小于15的时候我们直接用插入排序即可。
三数取中：
三数取中的方法是优化选key阶段的，从数组的begin mid end三个数中选一个作为key，为什么这样做会优化呢？因为我们依靠从数组最左边或者最右边或者随机选key都有可能选到最大的或者最小的，我们的快速排序只有在每次选的key都是中间值的时候时间复杂度才为O(n*logn),如果每次选出的key都是最小的或者最大的那么就意味着每次排序只排了左边或者右边一个数，每次只排一个的话时间复杂度其实为O(n^2)才对是，所以才有了三数取中这个方法，每次都能保证选的key是区间中的中值，这就符合快排的理想状态了。为什么快排的理想状态下的时间复杂度为n*logn看下图：
我们不能发现理想状态下不就是二叉树吗？二叉树中我们当时专门计算了向下调整的空间复杂度为,如下图所示：
明白了快速排序的理想时间复杂度为O（NlogN）后我们就直接放代码了：
int midi(int* a, int begin, int end) { int mid = (begin + end) / 2; if (a[begin] < a[mid]) { if (a[end] > a[mid]) { return mid; } else if (a[begin] > a[end]) { return begin; } else { return end; } } else { //begin>mid if (a[mid] > a[end]) { return mid; } else if (a[begin] > a[end]) { return end; } else { return begin; } } } void QuickSort3(int* a, int begin, int end) { if (begin >= end) { return; } if ((begin + end + 1) < 15) { InsertSort(a, begin + end + 1); } else { int mid = midi(a, begin, end); swap(&a[mid], &a[begin]); int prev = begin; int cur = begin + 1; int key = begin; while (cur <= end) { //当cur小于key并且cur和prev指向的不是同一个位置的时候就交换（因为同一个位置交换没意义） if (a[cur] < a[key] && ++prev != cur) { swap(&a[cur], &a[prev]); } cur++; } //当cur越界就把prev和key位置数据交换 swap(&a[key], &a[prev]); QuickSort3(a, begin, prev - 1); QuickSort3(a, prev + 1, end); } }
我们可以看到三个数取中间值还是比较麻烦的，首先假设begin<mid,当end>mid的时候中间值就是mid了，如果end<mid的话再去比较end和begin谁大然后返回其中间值即可。有了三数取中这个方法快速排序就相当于每次都是理想状态下的排序了。
非递归版快速排序：
我们刚刚已经讲解过，快速排序的本质在于每次找出一个key然后key的左区间都是比key小的，key的右区间都是比key大的，那么这个时候再去排左区间，既然是区间我们不妨可以想想其他的办法来实现非递归过程，有聪明的小伙伴应该也想到了吧，其实我们只需要把要排序的区间放入栈或者队列中，然后去将每个区间排序完成即可。下面直接放代码进行讲解。
#include <stdbool.h> #include <stdlib.h> #include <assert.h> typedef int StackDate; typedef struct Stack { StackDate* a; int top; int capcity; }Stack; void StackInit(Stack* ps) { assert(ps); StackDate* tmp = (StackDate*)malloc(4 * sizeof(StackDate)); if (tmp == NULL) { perror("malloc\n"); exit(-1); } ps->a = tmp; ps->top = 0; ps->capcity = 4; } void StackDestroy(Stack* ps) { assert(ps->a); free(ps->a); ps->a = NULL; ps->top = 0; ps->capcity = 0; } void StackPush(Stack* ps, StackDate x) { assert(ps); if (ps->capcity == ps->top) { StackDate* tmp = (StackDate*)realloc(ps->a, ps->capcity * 2 * sizeof(StackDate)); if (tmp == NULL) { perror("realloc\n"); exit(-1); } ps->a = tmp; ps->capcity *= 2; } ps->a[ps->top] = x; ps->top++; } bool StackEmpty(Stack* ps) { assert(ps); return ps->top == 0; } void StackPop(Stack* ps) { assert(ps); assert(ps->top > 0); ps->top--; } StackDate StackTop(Stack* ps) { assert(ps); assert(ps->top > 0); return ps->a[ps->top - 1]; } int _Qsort(int* a, int begin, int end) { int left = begin; int right = end; int key = left; while (left < right) { //左边为K让右边先走，右边找到小于K的停下 while (left < right && a[right] >= a[key]) { right--; } //右边找到小后停下让左边走去找比K大的然后交换 while (left < right && a[left] <= a[key]) { left++; } swap(&a[left], &a[right]); } //当left==right时两个下标相遇然后让相遇点和key交换，然后相遇点变成新的K swap(&a[left], &a[key]); key = left; return key; } void Qsort(int* a, int begin, int end) { Stack sl; StackInit(&sl); StackPush(&sl, begin); StackPush(&sl, end); while (!StackEmpty(&sl)) { int right = StackTop(&sl); StackPop(&sl); int left = StackTop(&sl); StackPop(&sl); int k = _Qsort(a, left, right); if (k + 1 < right) { StackPush(&sl, k + 1); StackPush(&sl, right); } if (left < k - 1) { StackPush(&sl, left); StackPush(&sl, k-1); } } StackEmpty(&sl); }
栈我们在之前的文章中详细讲解过，我们就直接讲如何用栈实现非递归的快速排序。首先创建一个栈，然后初始化，先将数组的第一个位置的下标和数组的最后一个位置的下标入栈，然后开始进入循环排序，由于栈是后进先出所以先出栈的是右边，我们用两个变量去分别接受左右区间的下标，当左右区间都有值了就去排序，我们在单趟排序的函数中让其函数返回了key的下标，通过key我们就可以分出左区间和右区间了，因为后进先出所以我们要是想先排序左区间的话就得先入右区间，入区间的时候要判断，当区间只有一个数的时候不需要排序所以不入栈，只有区间有两个及两个以上的数才入栈，只要栈不为空就会一直去排序直到完全有序，下面我们画个图演示一下。：
这样我们就完成了非递归的快速排序，当然用完栈后要记得把栈销毁了避免内存泄漏。快排的时间复杂度已经说过了是O（n*logn），那么空间复杂度是多少呢？我们按照递归版本来说每次递归都需要用函数栈帧一共有logn次，所以空间复杂度为O（logn），那么快速排序稳定吗？答案是不稳定，从单趟排序我们就可以看出来key以及left right的多次互换一定会打乱相同的数的相对顺序，所以快速排序是不稳定的。
归并排序：
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有 序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 大概意思就是先一个数和一个数归并，然后再两个数两个数进行归并，当数组左半边区间和右半边区间都归并完成了就整体归并。以下是代码：
void _MergeSort(int* a, int begin, int end, int* tmp) { if (begin >= end) { return; } int mid = (begin + end) / 2; //先归并左半区间让其有序，再归并右半区间让其有序，最后在整体归并。 _MergeSort(a, begin, mid, tmp); _MergeSort(a, mid+1, end, tmp); int begin1 = begin; int end1 = mid; int begin2 = mid + 1; int end2 = end; int i = begin; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] <= a[begin2]) { tmp[i++] = a[begin1++]; } else { tmp[i++] = a[begin2++]; } } while (begin1 <= end1) { tmp[i++] = a[begin1++]; } while (begin2 <= end2) { tmp[i++] = a[begin2++]; } memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1)); } void MergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc:"); exit(-1); } _MergeSort(a, 0, n - 1, tmp); free(tmp); tmp = NULL; }
同样先是采用递归的方法，我们需要开辟一个数组，每次归并完成的数都放在开辟的数组中，然后每次一部分的归并结束后就把开辟的数组中的数复制到原来的数组中，开辟的数组记得用完释放掉。在递归的时候当当只有一个数的时候就不在递归直接去归并即可，下面我们画一个图来讲解一下是如何将一个数组归并成有序的。
下面的图是上面图的右半部分，由于不能左右截图所以只能分两张。通过这张图我们应该能了解到归并是如何进行的，通过中值去归并中值的左边区间和右边区间即使两边的个数不一样也能正常归并，每次归并完两个或者多个数的时候直接拷贝回原来的数组。我们可以看到归并排序的内核是将两个小区间的数根据谁大谁小依次放入新的数组这样就有序了，那么归并排序该如何用非递归实现呢？既然是两个区间的归并那么我们不妨设置一个变量，当这个变量为1的时候就是1个数和另一个数归并，当这个变量为2的时候就是2个数和另外两个数归并依次类推只要这个变量小于总数即可，有了这个思想那么我们就去实现一下。
非递归版归并排序：
解决了区间下标的问题我们再来看一看这个下标造成越界的情况：
一共10个数下标到9但是我们可以发现有三种越界情况，第一种是end1 begin2 end2都越界了，第二种是begin2 end2越界了，第三种是end2越界了。那么这三种情况的越界我们该怎样控制呢？
void MergeSortNonR(int* a, int n, int* tmp) { int rangeN = 1; while (rangeN < n) { for (int j = 0; j < n; j += rangeN * 2) { int begin1 = j; int end1 = j+rangeN-1; int begin2 = rangeN + j; int end2 = j+2*rangeN-1; if (end1 >= n) { end1 = n - 1; begin2 = n; end2 = n - 1; } else if (begin2 >= n) { begin2 = n; end2 = n - 1; } else if (end2 >= n) { end2 = n - 1; } int i = j; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] <= a[begin2]) { tmp[i++] = a[begin1++]; } else { tmp[i++] = a[begin2++]; } } while (begin1 <= end1) { tmp[i++] = a[begin1++]; } while (begin2 <= end2) { tmp[i++] = a[begin2++]; } } memcpy(a, tmp, sizeof(int) * n); rangeN *= 2; } } void MergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc:"); exit(-1); } //_MergeSort(a, 0, n - 1, tmp); MergeSortNonR(a, n, tmp); free(tmp); tmp = NULL; }
以上是修正区间后的代码。range一开始为1当range小于n就进入循环，然后通过一个下标去访问各个区间里的数，j每次跳过2*rangeN是为了在上两个区间归并完成后能跳到下一个要归并的第一个区间。比如1 2 3 4 中1 2归并后下标要跳到3让3和4归并。当end1越界的时候我们要调整end1的区间合法并且要将begin2和end2修改为不能进入归并循环的大小，因为当end1越界就说明begin2 end2都越界了这个时候不需要再和第二个区间归并了，当begin2 end2越界的时候同理不需要归并第二个区间所以直接修改这两个变量的值让其不进入归并循环。当end2越界的时候就必须调整end2的区间，因为第一个区间是合法的，第二个区间部分是合法的只需要把越界的那部分去掉然后让两个区间归并即可。等到for循环结束就意味着所有的数都已经归并完成了，这个时候直接将开辟的数组拷贝到原先的数组就实现了非递归的归并排序。当然修改区间还有另外一种解决办法，如下所示：
void MergeSortNonR2(int* a, int n, int* tmp) { int rangeN = 1; while (rangeN < n) { for (int j = 0; j < n; j += rangeN * 2) { int begin1 = j; int end1 = j + rangeN - 1; int begin2 = rangeN + j; int end2 = j + 2 * rangeN - 1; if (end1 >= n) { break; } else if (begin2 >= n) { break; } else if (end2 >= n) { end2 = n - 1; } int i = j; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] <= a[begin2]) { tmp[i++] = a[begin1++]; } else { tmp[i++] = a[begin2++]; } } while (begin1 <= end1) { tmp[i++] = a[begin1++]; } while (begin2 <= end2) { tmp[i++] = a[begin2++]; } memcpy(a+j, tmp+j, sizeof(int) * (end2-j+1)); } rangeN *= 2; } }
我们发现当end1越界的时候说明第二个区间肯定越界了这个时候就不归并了直接break退出去，同理第二个区间越界了也是直接break即可。只有当end2越界的时候需要考虑部分合法部分越界，只需要将越界的那部分删除然后让两个区间进行归并即可。刚刚第一次我们是range每改变一次就把归并后的数据拷贝到原数组，而这次我们是每一个小循环内两个区间归并完就直接拷贝到原数组，唯一的区别在于部分拷贝需要加上开始拷贝的下标已经大小是这部分区间的大小，因为是闭区间所以要+1。举个例子：当range为1的时候，第一种是第一个数和第二个数归并了，第三个数和第四个数归并了依次到最后两个数归并完成然后整体在拷贝到原数组，range*2后变成两两归并又重复刚才的步骤。第二种是第一个数和第二个数归并了然后直接拷贝到原数组然后再进行第三个数和第四个数归并，然后又拷贝到原数组。相比起来的差别就是第二种拷贝的次数多于第一种。那么归并排序的时间复杂度是多少呢？每次取中分为两个区间是logn次，一共有n个数需要归并所以时间复杂度为O（n*logn），那么空间复杂度是多少呢？我们额外开辟了n个int大小的空间所以空间复杂度为O（n）。归并排序稳定吗？我们已经说了归并的内核就是将两个区间内小的数依次插入新的数组，只要第一个区间的元素小于或者等于第二个区间的元素就把第一个区间的元素放入tmp，这样并不会改变相同数的相对顺序所以是稳定的。
以上就是排序的所有内容了。
总结
排序中快速排序和归并排序的难度不亚于二叉树甚至比二叉树更大。我们通过画图等方式可以看出只有直接插入排序 冒泡排序 归并排序是稳定的，并且时间复杂度最好的排序有希尔排序 堆排序 快速排序 归并排序这四个。
