排序算法之交换排序（快排的递归，非递归）_沙漠下的胡杨

大大的周 02-07 4118

??个人主页：欢迎大家光临——>沙漠下的胡杨

? 各位大帅哥，大漂亮

?如果觉得文章对自己有帮助

?可以一键三连支持博主

?你的每一分关心都是我坚持的动力

??：本期重点：快排的递归，非递归和排序的优化

??希望大家每天都心情愉悦的学习工作。?

? ?：本期重点：快排的递归，非递归和排序的优化

关于递归会不会影响效率的解释：

?递归版：

非递归版：

快速排序的时间复杂度分析：

我们先拿最坏的举例（O(N*N)）：

一般情况下复杂度为（? O(N*log(N))? ?）：

快速排序的优化：

三数取中：

减少最后几层递归调用：

书接上回，我们讲过了三种办法的单趟排序的实现，下一步我们就重点讲解快排的递归，非递归和排序的优化。

关于递归会不会影响效率的解释：

递归现代编译器优化很好，性能已经不是大问题最大的问题->递归深度太深，程序本身没问题，但是栈空间不够，导致栈溢出，只能改成非递归，改成非递归有两种方式： 1、直接改循环-》斐波那契数列求解

2、树遍历非递归和快排非递归等等，只能用Stack存储数据模拟递归过程

?递归版：

首先我们使用单趟排序把数据分为三部分了，[0,keyi] 和 keyi 以及[keyi+1,keyi]这三部分，那么我们进行递归分析，首先我们递归结束的条件是，当范围内的数据只剩下1个或者没有数据时就停止。那么就比较容易写出来了，其中任意一个单趟排序都可以调用。

代码如下：

//前后指针法单趟排序 int PartSort1(int *a,int left,int right) { int keyi = left;//先保存最左侧下标，作为keyi while (left < right) { //先让右走，找小，并且不能越界 while (left < right && a[right] >= a[keyi]) { --right; } //再让左走，找大，不越界。 while (left < right && a[left] <= a[keyi]) { ++left; } //交换左边大的，和右边小的 Swap(&a[left], &a[right]); } //循环完成，我们在最后交换下，相遇位置的和原来keyi位置的值 Swap(&a[keyi], &a[left]); //返回相遇位置的下标是为进行下一步递归。 return left; } //挖坑法 int PartSort2(int* a, int left, int right) { int key = a[left];//保存最左边初始位置的值 while (left < right) { while (left < right && a[right] >= key) { --right; } a[left] = a[right];//产生一个坑位 while (left < right && a[left] <= key) { ++left; } a[right] = a[left];//上一个坑位填上，产生新的坑位 } a[left] = key;//把最后的坑位填上了。 return left;//返回最后相遇的下标，以便后序递归 } //前后指针法 int PartSort3(int *a, int left, int right) { int prev = left;//后指针 int cur = left + 1;//前指针 int keyi = left;//初始位置 while(cur <= right)//当cur小于等于最右边时进入循环 { //当cur找到比初始位置大的数，如果此时cur不等于prev， //那么就交换cur和++prev，一定是前置++。 if (a[cur] < a[keyi] && prev != cur) { Swap(&a[cur], &a[++prev]); } cur++; } Swap(&a[prev], &a[keyi]);//最后交换prev和初始位置即可 return prev;//返回prev为了后续递归做铺垫 } void QuickSort(int *a, int begin, int end) { if (begin >= end)//如果 begin >= end表示区间只有一个数，或者没有数 { return; } //接收第一趟排序的返回值，即是我们下面数据的分割线 int keyi = PartSort3(a, begin, end); //分为左区间和右区间，进行递归 QuickSort(a, begin, keyi - 1); QuickSort(a, keyi + 1, end); } 非递归版：

非递归版本我们使用栈这个数据结构帮助我们解决，我们利用栈?后进先出的特性，把下标放入栈中，然后单趟排序，再把单趟排序的两段分别放入栈中，如此反复，我们就可以把数据排序完成。

代码如下：

//非递归版本实现 void QuickSortNonR(int* a, int begin, int end) { ST st; StackInit(&st); StackPush(&st, begin);//把最开始数据的第一个下标放入栈中 StackPush(&st, end);//把最开始数据的最后一个下标放入栈中 while (!StackEmpty(&st))//栈不为空继续 { int left, right;//定义左右下标，用来判断是否要继续排序 right = StackTop(&st);//出右下标 StackPop(&st); left = StackTop(&st);//出左下标 StackPop(&st); int keyi = PartSort1(a, left, right);//单趟排序 //排序好左边的数据个数大于1个，就继续排序 if (left < keyi - 1) { StackPush(&st, left);//把左下标入栈 StackPush(&st, keyi - 1);//把排序好位置的左边的下标入栈 } //排序好右边的数据个数大于1个，就继续排序 if (keyi + 1 < right) { StackPush(&st, keyi + 1);//把排序好位置的右边的下标入栈 StackPush(&st, right);//右下标入栈 } } StackDestroy(&st); }

下面用流程图演示下：

快速排序的时间复杂度分析：我们先拿最坏的举例（O(N*N)）：

?快速排序每次确定一个数，每次交换为等差数列，（n，n-1，n-2，...，2,1），一共n个数，所以在最坏的情况下是O(N*N）。

一般情况下复杂度为（? O(N*log(N))? ?）：

快速排序的优化：三数取中：

1.我们要避免最坏的情况出现，所以我们加上一个算法，叫三数取中算法即可，这样的最坏情况下的逆序变成最好情况啦。

代码实现：

int GetMidIndex(int* a, int left, int right) { int mid = (left + right) / 2; if (a[left] < a[mid]) { if (a[mid] < a[right]) { return mid; } else if (a[right] < a[left]) { return left; } else { return right; } } else { if (a[mid] > a[right]) { return mid; } else if (a[left]<a[right]) { return left; } else { return right; } } } 减少最后几层递归调用：

?2.我们可以在递归调用的最后几层使用其他的排序算法，因为最后几层的递归调用太多，消耗的成本太大啦，所以使用插入排序更好点。我们使用插入排序时，注意我们要排序的区间不要整错了。

//递归版 void QuickSort(int *a, int begin, int end) { if (begin >= end)//如果 begin >= end表示区间只有一个数，或者没有数 { return; } if (end - begin > 20) { //接收第一趟排序的返回值，即是我们下面数据的分割线 int keyi = PartSort3(a, begin, end); //分为左区间和右区间，进行递归 QuickSort(a, begin, keyi - 1); QuickSort(a, keyi + 1, end); } else { //使用插入排序 InsertSort(a + begin, end - begin - 1); } }