注意：
1.这里同样也要保存下left和right的值，原因同Hoare法的一样，因为代码过程中其值发生改变会影响递归传递。
2.这里与Hoare法有所不同，这里key要记录a[left],而不是下标，因为你在之后的填坑过程中，left下标处的值可能被交换了，不是我们最初想要的值，所以要记录下来最初的那个值，即a[left]。

前后指针法的单趟排序的基本步骤如下：
1.选出一个key作为比较值，一般是最左或者最右边。让prev指向left，cur指向left+1。
2.之后比较cur位置的值和key的值，首先要保证cur位置的值要小于key，而且++prev！=cur,这时交换prev和cur位置对应的值，不管满不满足这两个条件，cur都要++，这样才能迭代起来。
3.直到cur越界，此时prev为key应该在的位置，此时交换prev位置的值和key，就可以达到我们想要的效果。
4.仍然是递归其左序列和右序列，最终整个序列有序。

//快速排序（前后指针法） void QuickSort3(int *a, int left, int right) { if (left >= right) {return; } //这里没有必要记录left和right的值，因为整个代码中这两个量一开始是什么值，最终仍然是那个值 //int begin= left; //int end = right; int pre = left; int cur = left + 1; int key = left; //这里要记住小标，不然值是交换不过去的，一般快排中用到交换的换，都是记录下标 while (cur <= right) {if (a[cur] < a[key] && ++pre != cur) {swap(&a[pre], &a[cur]); } cur++; } int meet = pre; swap(&a[meet], &a[key]); QuickSort3(a, left, meet - 1); QuickSort3(a, meet + 1, right); }

注意：
1.这里没有必要再和上面一样保存left和right的值了，因为整个过程中left和right的值并没有变化。
2.这里和Hoare法那儿一样，key要记录left这个下标，而不是a[left]这个值，因为你之后要交换meet和key位置处对应的值，而你一开始如果记录a[left]是做不到这一点的。(一般而言如果有swap交换这个需求的话，都要记录下标，而不是下标处对应的值）
3.这里要注意a[cur] < a[key] && ++pre != cur这两个条件写的先后顺序，一定要把比较大小写在前面，如果你的a[cur]都不满足比a[key]小，那么就不需要++prev这一步的判断了。

当我们需要将一个用递归实现的算法改为非递归时，一般需要借用一个数据结构，那就是栈。将Hoare版本、挖坑法以及前后指针法的快速排序改为非递归版本，其实主体思想一致，只是调用的单趟排序的算法不同而已。

//快速排序（前后指针法） void QuickSort3(int *a, int left, int right) { if (left >= right) {return; } //这里没有必要记录left和right的值，因为整个代码中这两个量一开始是什么值，最终仍然是那个值 //int begin= left; //int end = right; int pre = left; int cur = left + 1; int key = left; while (cur <= right) {if (a[cur] < a[key] && ++pre != cur) {swap(&a[pre], &a[cur]); } cur++; } int meet = pre; swap(&a[meet], &a[key]); QuickSort3(a, left, meet - 1); QuickSort3(a, meet + 1, right); }

//挖坑法（单趟排序） int QuickSort2(int* a, int left, int right) { int key = a[left]; //在最左边形成一个坑位 while (left < right) {//right向左，找小 while (left < right&&a[right] >= key) {right--; } //填坑 a[left] = a[right]; //left向右，找大 while (left < right&&a[left] <= key) {left++; } //填坑 a[right] = a[left]; } int meeti = left; //L和R的相遇点 a[meeti] = key; //将key抛入坑位 return meeti; //返回key的当前位置 }

//前后指针法（单趟排序） int QuickSort3(int* a, int left, int right) { int prev = left; int cur = left + 1; int keyi = left; while (cur <= right)//当cur未越界时继续 {if (a[cur] < a[keyi] && ++prev != cur)//cur指向的内容小于key {Swap(&a[prev], &a[cur]); } cur++; } int meeti = prev; //cur越界时，prev的位置 Swap(&a[keyi], &a[meeti]); //交换key和prev指针指向的内容 return meeti; //返回key的当前位置 }

快速排序的非递归算法基本思路：
1、先将待排序列的第一个元素的下标和最后一个元素的下标入栈。
2、当栈不为空时，读取栈中的信息（一次读取两个：一个是L，另一个是R），然后调用某一版本的单趟排序，排完后获得了meet的下标，然后判断meet的左序列和右序列是否还需要排序，若还需要排序，就将相应序列的L和R入栈；若不需排序了（序列只有一个元素或是不存在），就不需要将该序列的信息入栈。
3、反复执行步骤2，直到栈为空为止。

//类似于二叉树的遍历，根——右子树——左子树 void QuickSort4(int* a, int left, int right) { ST p; StackInit(&p); StackPush(&p, left); StackPush(&p, right); while (!StackEmpty(&p)) {int right= StackTop(&p); //注意栈的性质，或进先出，因此先赋值给right StackPop(&p); int left= StackTop(&p); StackPop(&p); //if (left >= right)可写可不写 //{// return; //} int meet = QuickSort5(a, left, right); if (left < meet - 1)//左序列还存在时 {StackPush(&p, left); StackPush(&p, meet - 1); } if (meet + 1 < right)//右序列还存在时 {StackPush(&p, meet + 1); StackPush(&p, right); } } StackDestory(&p); }

注意：这里要注意栈的性质后进先出，因此要先赋值给right再赋值给left。

时间复杂度：O（nlogn）

快速排序的时间复杂度是O(NlogN)，是我们在理想情况下计算的结果。在理想情况下，我们每次进行完单趟排序后，key的左序列与右序列的长度都相同：

文章图片

?若每趟排序所选的key都正好是该序列的中间值，即单趟排序结束后key位于序列正中间，那么快速排序的时间复杂度就是O(NlogN)。
但是万一当待排序列本就是一个有序的序列时，我们若是依然每次都选取最左边或是最右边的数作为key，那么快速排序的效率将达到最低：

文章图片

这时的时间复杂度为O（n^2)。其实，对快速排序效率影响最大的就是选取的key，若选取的key越接近中间位置，则则效率越高。

为了避免这种极端情况的发生，于是出现了三数取中：
三数取中，当中的三数指的是：最左边的数、最右边的数以及中间位置的数。三数取中就是取这三个数当中，值的大小居中的那个数作为该趟排序的key。这就确保了我们所选取的数不会是序列中的最大或是最小值了。

int GetMidIndex(int* a, int left, int right) { int mid = left + (right - left) / 2; //防止整形溢出 if (a[right] > a[mid]) {if (a[mid] > a[left]) {return mid; } else if (a[right] > a[left]) {return left; } else {return right; } } else {if (a[left] > a[mid]) {return mid; } else if (a[right] > a[left]) {return right; } else {return left; } } }

我们可以看到，就算是上面理想状态下的快速排序，也不能避免随着递归的深入，每一层的递归次数会以2倍的形式快速增长。
为了减少递归树的最后几层递归，我们可以设置一个判断语句，当序列的长度小于某个数的时候就不再进行快速排序，转而使用其他种类的排序。小区间优化若是使用得当的话，会在一定程度上加快快速排序的效率，而且待排序列的长度越长，该效果越明显。

//快速排序的小区间优化 void QuickSort6(int *a, int left, int right) { if (left >= right) {return; } if (right - left + 1 > 20) {int meet = QuickSort5(a, left, right); QuickSort5(a, left, meet - 1); QuickSort5(a, meet + 1, right); } else {ShellSort(a,right-left+1); } }

归并排序是采用分治法的一个非常典型的应用。其基本思想是：先让每个子序列都有序，然后再合并这些子序列，让整个序列有序。这其中要注意了：子序列又可以看成是一个整体又可以分成两个子序列，要直到分到序列只有一个数时，这时才不能继续分了，且当只有一个数时，这个序列就是有序的。其实这儿的思想和二叉树的好像，当你看完代码和递归过程后，你还会发现其实这个和二叉树的后序遍历很相似。
下面来看个例子：

文章图片

其实这张图就相当于是整个递归的过程，分解的过程相当于递归的顺序执行，合并的过程相当于递归返回的过程。

其间我们需要申请一个与待排序列大小相同的数组用于合并过程两个有序的子序列，合并完毕后再将数据拷贝回原数组。

voidMergeSort(int* a, int left, int right,int* temp) { if (left >= right) return; int mid = left + (right - left) / 2; int begin1 = left, end1 = mid; int begin2 = mid+1, end2 = right; int i = left,j=0; //i一定要写成left不能写成0，如果是递归左序列还可以适用，但是递归到右序列时就不行了 MergeSort(a, left, mid, temp); //这里要注意区间的划分，不然可能出现死递归 MergeSort(a, mid + 1, right, temp); while (begin1 <= end1&&begin2 <= end2) {if (a[begin1] < a[begin2]) {temp[i++] = a[begin1++]; } else {temp[i++] = a[begin2++]; } } while (begin1 <= end1) {temp[i++] = a[begin1++]; } while (begin2 <= end2) {temp[i++] = a[begin2++]; } for (j = left; j < right + 1; j++) {a[j] = temp[j]; } }

时间复杂度 ： O（NlogN） 空间复杂度： O（N）

在上面的代码中，我们将区间划分成了[left,mid]和[mid+1，right],是不是只能这样分了？带着这样的好奇，我尝试了另一种分法，将区间划分成[left,mid-1]和[mid,right],这样划分是否可以了？经过画图分析后，答案是不可以的，在这个问题中，区间只能这么划分。

文章图片

如果你是这样划分的话，在某些测试用例中，可能会出现死递归。其原因是你的mid和right有可能永远不会相等，也就无法结束掉某个递归，因此造成了死递归。

归并排序的非递归并不像快速排序那样一定要用栈来实现，我们只需要控制每次参与合并的元素个数即可，最终便能使序列变为有序

这只是一个理想化的例子，在做这种题目时，我们一定要充分考虑到边界情况。

情况一：
第二个小区间存在，但是个数不满，这时我们需要对边界进行控制，不然会导致序列合并时数组越界的问题。

文章图片

情况二：
第二个小区间不存在，第一个小区间存在，这时我们不需要在意第一个小区间有没有满，因为这时只有一个区间，无法进行序列的合并，所以直接不管它，即break出去就行。

文章图片


文章图片

void _MergeSort(int *a, int begin1,int end1,int begin2,int end2, int * temp) { int j = begin1; int i = begin1; while (begin1 <= end1&&begin2 <= end2)//用&&链接，其中有一个结束就结束了 {if (a[begin1] < a[begin2]) {temp[i++] = a[begin1++]; } else {temp[i++] = a[begin2++]; } } while (begin1 <= end1)//如果区间一还有则全部赋值过去 {temp[i++] = a[begin1++]; } while (begin2 <= end2)//如果区间二还有则全部赋值过去，这时两个序列合并完成 {temp[i++] = a[begin2++]; } for (; j <= end2; j++)//将合并好的序列传给原数组 {a[j] = temp[j]; } }void MergeSort2(int *a, int n) { int *temp = (int *)malloc(sizeof(int)*n); if (temp == NULL) {printf("malloc failed\n"); exit(-1); } int gap = 1; //控制每次元素的个数 int i = 0; while (gap < n) {for (i = 0; i < n; i += 2 * gap) {int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + (2 * gap) - 1; if (begin2 >= n)//此时只有第一个区间，不存在两个序列合并的需求，因此直接break {break; } if (end2 >= n) //此时第二个区间元素个数不满，为了防止合并两个序列时数组访问越界，在这里处理掉 {end2 =n-1; } _MergeSort(a, begin1, end1, begin2, end2, temp); } gap *= 2; } free(temp); }

计数排序又叫非比较排序，它不需要比较就可以排序，是不是很神奇了？它主要是利用哈希映射来实现的（这在之后c++部分会详细介绍），这里大概说下它的思路：
1.首先创建一个数组，那么这个数组的大小怎么定了？这取决于原数组中的最大值和最小值。
2.然后我们遍历原数组，遇到哪个值则在创建的数组中以他为下标的位置++。
3.最后打印创建的数组的下标，那个下标存放的值为几，则那个下标就打印几次。
注意：为什么我们这样就能保证数组是有序的了？其实最主要的原因是因为数组的下标本来就是有序的，其次这其中利用了哈希映射。

【数据结构|排序算法学习（2）（快速排序，归并排序，计数排序）（详细解析，建议收藏！！！）】上列中的映射方法称为绝对映射，即arr数组中的元素是几就在count数组中下标为几的位置++，但这样会造成空间浪费。例如，我们要将数组：1001,1002,1005，进行排序，难道我们要开辟1006个整型空间吗？
所以我们使用计数排序时，最好是使用相对映射。下面我们来简单介绍下相对映射：数组中的最小值就相对于count数组中的0下标，数组中的最大值就相对于count数组中的最后一个下标。这样，对于数组1001,1002,1005我们只需要开辟5个空间即可，即此时count数组中下标为i的位置，记录的是1001+i出现的次数。
总的来说：
绝对映射：count数组中下标为i的位置记录的是arr数组中数字i出现的次数。
相对映射：count数组中下标为i的位置记录的是arr数组中数字min+i出现的次数。
这里也要注意：计数排序针对数字较为集中时处理比较高效，如果刚刚那个数组为1,100,1005则不管使用什么映射，都会存在空间的浪费。

//计数排序 void CountSort(int*a, int sz) { int min = a[0], max = a[0]; int i = 0; int j = 0; for (i = 1; i < sz; i++) {if (a[i] < min) {min = a[i]; } if (a[i]>max) {max = a[i]; } } int range = max - min + 1; //min和max之间的自然数个数（包括min和max本身） int *count = (int*)calloc(range, sizeof(int)); //min和max之间的自然数个数（包括min和max本身） if (count == NULL) {printf("calloc failed\n"); exit(-1); } 统计相同元素出现次数（相对映射） for (i = 0; i < sz; i++) {count[a[i]-min]++; } 根据统计结果将序列回收到原来的序列中 for (i = 0; i < range; i++) {while (count[i]--) {a[j++] = i+min; } } free(count); }

推荐阅读

• 

  可以推荐几部非常好看的电视剧吗？
• 

  寸草心谜底揭秘
• 

  去4s店检测故障要钱吗多少钱 去4s店检测故障要钱吗
• 

  mysql版本号怎么查看 mysql 查版本
• 

  鱼汤馄饨做法步骤视频 鱼汤馄饨做法步骤
• 

  遇到西门子洗衣机显示bb怎么办,主要差别在这里
• 

  人工智能 人员分析
• 

  生吃鱼腥草有寄生虫吗
• 

  阴沉木鉴定方法 阴沉木鉴定方法
• 

  在你心里谁是真正的演技派和实力派？
• 

  红米手机怎么关闭流量套餐
• 

  决眦入归鸟上一句是什么
• 

  恐龙的体型为什么那么大
• 

  精通分析师教材
• 

  永远的拼音 永的拼音
• 

  OPPOA73如何使用手势导航 具体操作流程介绍
• 

  万字的笔顺 汉字万字的笔顺
• 

  什么叫代拍摄影，摄影代拍平台
• 

  红豆薏米绿豆的功效
• 

  原理图分析答辩,偿债能力分析答辩问题

• 画解算法（1.|画解算法：1. 两数之和）
• Guava|Guava RateLimiter与限流算法
• 一个选择排序算法
• SG平滑轨迹算法的原理和实现
• 《算法》-图[有向图]
• 排序（归并排序）
• LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
• 虚拟DOM-Diff算法详解
• 《数据结构与算法之美》——队列
• 【图解】9张图彻底搞懂堆排序