数据结构-快速排序“人红是非多”？看我见招拆招

2023-11-22 13:44
文章标签 快速 数据结构 排序 是非 见招拆招 人红

本文主要是介绍数据结构-快速排序“人红是非多”？看我见招拆招，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

1.快速排序

Hoare版本：

挖坑法：

前后指针版本:

快速排序的时间复杂度

2.快速排序的优化

三数取中法选key

随机数选key

三路划分法

3. 非递归实现快速排序

1.快速排序

快速排序一共有三种版本：Hoare版本、挖坑法、前后指针版本。

Hoare版本：

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

也就是说如果我们要排一个升序，我们可以在待排数据中选择一个值key，把大于该值的数据放在该值的右边，小于该值的数据放在该值的左边，然后在左边的数据中同样选择一个值，重复以上步骤，同时，在右边的数据中选择一个值，重复以上步骤，直到key的左边和右边都是有序的，此时所有数据都有序了。

过程如图所示，是一个递归的过程：

下面我们先来实现一趟的排序：

可以选左边第一个数据为key，然后从右边先开始遍历，当右边找到小于key的值时，停下来，当左边遍历找到大于key的值时，也停下来，然后交换左右两边的数据，最后当左右相遇的时候，把key交换到相遇位置，这就保证了小于key的数据落入key左边，大于key的数据落在key右边。

上代码：

int PartSort(int* a, int left, int right)
{int key = a[left];int keyi = left;while (left < right){while (left < right && a[right] >= key){right--;}while (left < right && a[left] <= key){left++;}Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);return left;
}

我们单趟排完之后应该如下图所示：

下面来解释一下代码中的循环判断条件：

最外层循环：left<right，左右相遇时就停止。

内层循环：left < right && a[right] >= key，这段代码解决了两个可能存在的问题：

1.  死循环问题

当待排数据如下面所示就可能造成死循环：

所以a[right] >= key时继续遍历。

2. 越界问题

如果a[right] >= key时继续遍历，下面极端情况可能导致越界：

所以我们在内层循环中还要判断一下 left<right。

这就是单趟排序的代码了，我们要实现对所有数据的升序，递归调用就行了，当完成一趟排序时，返回相遇位置，然后对相遇位置的左边和右边数据继续重复进行以上操作。这有些类似于二叉树的递归问题。

代码如下：

//交换函数
Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
//快速排序
int PartSort(int* a, int left, int right)
{int key = a[left];int keyi = left;while (left < right){while (left < right && a[right] >= key){right--;}while (left < right && a[left] <= key){left++;}Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);return left;
}void QuickSort(int* a, int begin, int end)
{if (begin >= end){return;}int keyi = PartSort(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1,end);
}Print(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}
int main()
{int a[] = { 9,7,5,2,4,7,1,6,0,8 };QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);Print(a, sizeof(a) / sizeof(int));return 0;
}

整个排序过程如下图：

注意下面这段代码的作用是：当区间只有一个值或者出现区间不存在的情况的时候就返回。

 if (begin >= end)
    {
        return;
    }

不知道大家有没有注意到一个情况，我们在选择key为左边的数据时，先让右边开始遍历，这是为什么呢？

首先，我们选左边的数据为key，那最终相遇位置的数就一定要比key的值小，这样交换后才能保证key的左边的值都比它小，右边的值都比它大，那我们如何保证相遇位置的值一定就比key小呢？

先给结论:

1. 左边做key，右边先走；保证了相遇位置的值比key小。

2. 右边做key，左边先走；保证了相遇位置的值比key大。

下面我们来论证一下：

结论2的论证同上。

这就是Hoare版本，但是通过上文的学习，这种版本存在的坑太多，下面我们来学一种方法避坑。

挖坑法：

挖坑法的单趟排序过程如图所示：

先选左边的一个数据，把它作为坑，并保存它的值，然后继续右边遍历找到比key小的值就停下，挖走这个值填坑，挖走后形成新的坑，左边遍历找比key大的值就停下，挖走这个值填坑......最后左右相遇，把保存的key值填坑。

代码实现如下:

//挖坑法
int PartSort2(int* a, int left, int right)
{int key = a[left];int hole = left;while (left < right){while (left < right && a[right] >= key){right--;}a[hole] = a[right];hole = right;while (left < right && a[left] <= key){left++;}a[hole] = a[left];hole = left;}a[hole] = key;return hole;
}void QuickSort(int* a, int begin, int end)
{if (begin >= end){return;}int keyi = PartSort2(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}
Print(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}
int main()
{int a[] = { 9,7,5,2,4,7,1,6,0,8 };QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);Print(a, sizeof(a) / sizeof(int));return 0;
}

前后指针版本:

前后指针版本单趟排序过程如下图所示：

我们可以看到，cur在找小，如果a[cur]<key，prev++，然后交换a[prev]和a[cur]，如果a[cur]>key，prev不动，整个过程中cur一直不停的往后走，直到cur越界就结束了，此时再交换key和a[prev]。

代码如下：

//前后指针版本
int PartSort3(int* a, int left, int right)
{int prev = left;int cur = left + 1;int keyi = left;while (cur <= right){if (a[cur] <= a[keyi]){prev++;Swap(&a[prev], &a[cur]);}cur++;}Swap(&a[prev], &a[keyi]);keyi = prev;return keyi;
}
void QuickSort(int* a, int begin, int end)
{if (begin >= end){return;}int keyi = PartSort3(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}
Print(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}
int main()
{int a[] = {6,1,2,7,9,3,4,5,10,8};QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);Print(a, sizeof(a) / sizeof(int));return 0;
}

快速排序的时间复杂度

时间复杂度（最好）：O(N*logN)。

时间复杂度（最坏）：O(N^2)。

什么时候最好呢？

当每次选的key恰好是中位数时，每次都把数据分成两份，每次减少一半的运算量，相当于二分法：

什么时候最坏呢？

当待排数据本来就是有序的时候，每次选key，选的都是最小的值，此时就相当于等差数列：

那我们选key有两种方案：

1. 随机数取key。

2. 三数取中法选key。

这样可以保证不会是最坏的情况。

2.快速排序的优化

三数取中法选key

三数取中法就是，把左边、右边和中间的三个数相比较，取出其中的中位数，把它作为key，这样就可以提高快速排序的效率。

代码如下：

//三数取中法选key
int GetMidIndex(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[mid] < a[left]){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[right] > a[left]){return right;}else{return left;}}
}
//快速排序
//Hoare版本
int PartSort(int* a, int left, int right)
{int midi = GetMidIndex(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;while (left < right){while (left < right && a[right] >= a[keyi]){right--;}while (left < right && a[left] <= a[keyi]){left++;}Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);return left;
}void QuickSort(int* a, int begin, int end)
{if (begin >= end){return;}int keyi = PartSort(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}

以上就是三数取中法对快速排序的优化了，下面我们来看一道题，看看我们的快速排序能不能通过？

题目链接：力扣（LeetCode）

结果呢？

超出时间限制了，这其实是力扣针对快速排序三数取中专门设计的一个测试用例，他故意把左边、右边和中间的值都设的很小，这样即使你三数取中，选出的key依旧很小，接近我们上文说的最坏情况，所以会超出时间限制，那我们不玩三数取中能不能过呢？

结果很明显，还是过不了，这次他直接给了个有序的测试用例，这就直接是我们上文中所说的最坏情况了，那怎么办呢？别急，我们还有一招：

随机数选key

随机数取key的意思是，我们保证左右的数据位置不变，中间数据的位置取一个随机数，这样我们三数取中得到的key也是随机的数据，这样力扣就针对不到我们了。

代码如下：

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//三数取中法选key
int GetMidIndex(int* a, int left, int right)
{//随机数取keyint mid=left+(rand()%(right-left));if (a[mid] < a[left]){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[right] > a[left]){return right;}else{return left;}}
}
//前后指针版本
int PartSort3(int* a, int left, int right)
{int midi = GetMidIndex(a, left, right);Swap(&a[left], &a[midi]);int prev = left;int cur = left + 1;int keyi = left;while (cur <= right){if (a[cur] <= a[keyi]){prev++;Swap(&a[prev], &a[cur]);}cur++;}Swap(&a[prev], &a[keyi]);keyi = prev;return keyi;
}
void QuickSort(int* a, int begin, int end)
{if (begin >= end){return;}int keyi = PartSort3(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}int* sortArray(int* nums, int numsSize, int* returnSize) {srand(time(0));QuickSort(nums,0,numsSize-1);*returnSize=numsSize;return nums;
}

int mid=left+(rand()%(right-left));

表示中间位置取随机位置，为了防止随机数越界，我们用它取余（right-left）。

但是这就结束了吗？还是太天真了，力扣预判了你的预判，不信再运行一下：

这次它给的数据全部相同，那不管我们怎么取key值都是取的最小的，这就又相当于最坏的情况，可见这道题为了针对快速排序是费尽了心思，那我们就没办法了吗？

当然不是，我们还有终极一招，

三路划分法

何谓三路划分呢？我们之前的快速排序是把大于等于key的放在右边，小于等于key的放在左边，相当于待排数据分为两份，而三路划分的意思是把小于key的放在左边，大于key的放在右边，等于key的放在中间，如图所示：

这种方法就是把等于key的收拢在中间位置，当我们递归子区间的时候，只递归小于和大于的区间，这样当待排数据中有重复数据时，可以大大提高效率，尤其是上述测试用例，收拢之后，左右子区间直接就没有值了，都不用再递归。

下图就是三路划分的思想：

我们可以演示一下三路划分的过程：

可以看到，三路划分的本质就是：

1. 和key相等的值都被收拢到中间

2. 小的被甩到左边，大的被甩到右边。

代码如下：

//三数取中法选key
int GetMidIndex(int* a, int left, int right)
{//随机数取keyint mid=left+(rand()%(right-left));if (a[mid] < a[left]){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[right] > a[left]){return right;}else{return left;}}
}void QuickSort(int* a, int begin, int end)
{if (begin >= end){return;}//三数取中int midi = GetMidIndex(a, begin, end);Swap(&a[begin], &a[midi]);int left=begin;int right=end;int cur=left+1;int key=a[left];//三路划分while (cur  <= right){if (a[cur] < key){Swap(&a[left], &a[cur]);left++;cur++;}else if (a[cur] > key){Swap(&a[right], &a[cur]);right--;}else{cur++;}}//递归QuickSort(a, begin, left - 1);QuickSort(a, right + 1, end);
}int* sortArray(int* nums, int numsSize, int* returnSize) {srand(time(0));QuickSort(nums,0,numsSize-1);*returnSize=numsSize;return nums;
}

到这，这道题就用了三种优化方式了，而且三种方式缺一不可，那能不能解决问题呢？

当然可以啦，如果没有上述优化方式，用快排做这道题会很坑，不是快排不快，而是“人红是非多”啊，快排在这道题上被针对的体无完肤，反而堆排、希尔排序等还能通过。

3. 非递归实现快速排序

 我们前文讲的递归方式，实际上递归过程处理的是左右子区间，现在我们不能用递归，那要如何处理左右子区间呢？

其实可以用栈实现，每次从栈中拿出一段区间，单趟分割处理，然后让左右子区间入栈。

代码如下（栈部分的代码可以拷贝前面章节的，这里只给核心代码）：

//前后指针版本
int PartSort3(int* a, int left, int right)
{int prev = left;int cur = left + 1;int keyi = left;while (cur <= right){if (a[cur] <= a[keyi]){prev++;Swap(&a[prev], &a[cur]);}cur++;}Swap(&a[prev], &a[keyi]);keyi = prev;return keyi;
}
//非递归方式实现快排
void QuickSortNonR(int* a, int begin, int end)
{ST st;STInit(&st);STPush(&st, end);STPush(&st, begin);while (!STEmpty(&st)){int left = STTop(&st);STPop(&st);int right = STTop(&st);STPop(&st);int keyi = PartSort3(a, left, right);if (keyi + 1 < right){STPush(&st, right);STPush(&st, keyi + 1);}if (left < keyi-1){STPush(&st, keyi-1);STPush(&st, left);}}STDestroy(&st);
}

好了，以上就是快速排序，下节继续学习归并排序，

未完待续。。。 

这篇关于数据结构-快速排序“人红是非多”？看我见招拆招的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/410561。

相关文章

电脑桌面文件删除了怎么找回来？别急，快速恢复攻略在此

电脑桌面文件删除了怎么找回来？别急，快速恢复攻略在此

在日常使用电脑的过程中，我们经常会遇到这样的情况：一不小心，桌面上的某个重要文件被删除了。这时，大多数人可能会感到惊慌失措，不知所措。 其实，不必过于担心，因为有很多方法可以帮助我们找回被删除的桌面文件。下面，就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件，并且还没有进行其他操作，那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心： 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数，若返回值为正，qsort 函数判定a>b ；为负，a<b；为0，a==b； int milkcmp(const void *va,c
阅读更多...
hdu 1285（拓扑排序）

hdu 1285（拓扑排序）

题意： 给各个队间的胜负关系，让排名次，名词相同按从小到大排。 解析： 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式，对一个有向无回路图进行拓扑排序后，所有的顶点形成一个序列，对所有边(u,v)，满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上，某些工程完成后，另一些工程才能继续，此时
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
hdu 4565 推倒公式+矩阵快速幂

hdu 4565 推倒公式+矩阵快速幂

题意 求下式的值： Sn=⌈ (a+b√)n⌉%m S_n = \lceil\ (a + \sqrt{b}) ^ n \rceil\% m 其中： 0<a,m<215 0< a, m < 2^{15} 0<b,n<231 0 < b, n < 2^{31} (a−1)2<b<a2 (a-1)^2< b < a^2 解析 令： An=(a+b√)n A_n = (a +
阅读更多...
v0.dev快速开发

v0.dev快速开发

探索v0.dev：次世代开发者之利器 今之技艺日新月异，开发者之工具亦随之进步不辍。v0.dev者，新兴之开发者利器也，迅速引起众多开发者之瞩目。本文将引汝探究v0.dev之基本功能与优势，助汝速速上手，提升开发之效率。 何谓v0.dev？ v0.dev者，现代化之开发者工具也，旨在简化并加速软件开发之过程。其集多种功能于一体，助开发者高效编写、测试及部署代码。无论汝为前端开发者、后端开发者
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
【软考】希尔排序算法分析

【软考】希尔排序算法分析

目录 1. c代码2. 运行截图3. 运行解析 1. c代码 #include <stdio.h>#include <stdlib.h> void shellSort(int data[], int n){// 划分的数组，例如8个数则为[4, 2, 1]int *delta;int k;// i控制delta的轮次int i;// 临时变量，换值int temp;in
阅读更多...
学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一：循环解法二：递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1：（图一）输入：head = [1,1,2]输出：[1,2]示例 2：（图
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2