个人中心
文章发布
退出
作者热门文章
- Java锁的逻辑（结合对象头和ObjectMonitor）
- 还在用饼状图？来瞧瞧这些炫酷的百分比可视化新图形（附代码实现）⛵
- 自动注册实体类到EntityFrameworkCore上下文，并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
27
4
快速排序 Quick Sort 与归并排序一样，也是典型的分治法的应用。 (如果有对 归并排序还不了解的童鞋，可以看看这里哟~ 归并排序 )❤❤❤ 。
1、选取基准值，获取划分位置。将原数组 a[l, r] 划分为两个子数组 a[l, mid - 1] 和 a[mid + 1, r] 。在前一个数组中所有元素都小于等于 a[mid] ，后一个数组中所有元素都大于等于 a[mid] 。而此时的 a[mid] 的值就是我们所取的基准值， mid 就每次划分的位置； 。
2、递归调用快速排序函数，分别对两个子数组 a[l, mid - 1] 和 a[mid + 1, r] 排序； 。
3、快速排序我们是在原数组上进行操作的，所以我们并不需要合并，最后 a[l, r] 已经有序.
快速排序比较普及的有三种写法，分别是 左右指针法 挖坑法 和 前后指针法 。主要是 取得划分位置实现的方法有所不同 。 接下来会逐个介绍这三种快速排序的写法.
1、首先 我们一般选取最左边的元素作为基准值 key .
2、然后我们需要定义两个变量 i 和 j 。 其中 i 为左指针(其实不是指针啦，只是为了方便这么叫它😋)，初始 i = 0。 j 为右指针，初始 j = r - 1，向左遍历不断找到小于基准值 key 的元素.
3、我们 先动右指针 j 向左遍历直到找到小于当前基准值 key 的元素；然后我们 再动左指针 i 向右遍历直到找到大于当前基准值 key 的元素。 当 i 和 j 分别找到它们要找的元素时，我们需要将两个元素进行位置交换。( 在这个过程中我们要保持 i < j ) 。
4、重复步骤3，直到最后我们可爱的左右指针相遇，这时我们再将基准值 key ，放到这两个指针指向的位置。此时我们就得到了当前划分的位置，基准值 key 也完成了归位.
在上述步骤中，有些人会感到疑惑，那就是我们再移动指针时，每次都要 先移动右指针 ， 再移动左指针 。为什么呢？😕😕😕 。
在取基准值时，我们一般都是将序列的最左边位置的元素作为基准值。我们每次交换完元素后，左右指针都会继续寻找他们要找的值，观感上就是相互靠近。而问题就出在我们 退出循环的那一刻 .
我们一直保持 i < j ，也就是说，我们会在 i == j 时退出循环。假设 在某次交换之后， 此时 j 指向的是交换之后的一个大于基准值的元素 ，如果我们先动左指针 i 去寻找一个大于基准值的元素，然鹅还未找到就已经和右指针 j 相遇了，这个时候我们需要退出循环，交换基准值 key 到当前两个指针指向的位置。 但是!!! ，此时 i 和 j 指向的是他喵的大于基准值的元素，那么我们进行交换基准值位置操作后，这个大于基准值的元素就被换到了序列的最左端，很明显，这时候出现了非常非常非常严重的错误.
那如果我们先动右指针 j ，去寻找一个小于基准值的元素，然鹅没有找到就已经和左指针 i 相遇了，这个时候退出循环， i 和 j 指向的一定是一个小于等于基准值的值.
究其原因，这其实是我们取最左边的元素作为基准值导致的。我们需要保证每次交换过来的元素是小于等于基准值的，所以我们 先动右指针 ， 再动左指针 .
//左右指针法
int Partition_Hoare(vector<int> &a, int left, int right){
int i = left;
int j = right;
int key = a[left];
while(i != j){
while(i < j && a[j] >= key) //向左找到小于基准值的值的下标
j--;
while(i < j && a[i] <= key) //向右找到大于基准值的值的下标
i++;
swap(a[i], a[j]);
}
/* i等于j时跳出循环 当前基准值此时在下标为i的位置(合适的位置) */
swap(a[left], a[i]); //最左边的元素变为处于当前合适位置的元素,把基准值放在合适位置
return i; //返回合适位置(i,j都可以)
}
挖坑法顾名思义，就是每次挖一个坑填入元素使其归位。和左右指针法一样，我们同样需要两个变量 i 和 j 。 1、我们一般取最左边的元素为基准值，然后在基准值处挖空(挖坑) 。
2、先动右指针 j 向左找到一个小于基准值的元素，然后将其填入先前挖的坑中，同时 j 指向的位置也多出来一个坑位.
3、再动左指针 i 向右找到一个大于基准值的元素，然后将其填入先前挖的坑中，同时 i 指向的位置又多出来一个坑位.
4、重复上述操作，直到最后两个指针相遇，此时再在这个坑位上填入基准值，即完成了基准值的归位，也就是我们划分的位置.
(具体实现这个挖坑填坑的方式可以是元素值的覆盖，也可以是元素交换的形式，在后面的核心代码中会给出这两种方式) 。
//挖坑法1
int Partition_DigI(vector<int> &a, int left, int right){
int i = left;
int j = right;
int key = a[left];
while(i != j){
while(i < j && a[j] >= key) //必须先动右边的 因为取的基准值在左边
j--; //向左寻找直到找到比基准值小的
a[i] = a[j]; //挖坑 填入比基准值小的值
while(i < j && a[i] <= key) //再动左边的
i++; //向右寻找直到找到比基准值大的
a[j] = a[i]; //挖坑 填入比基准值大的值
}
/* i等于j时跳出循环 下标为i的位置即为合适的插入位置 */
a[i] = key; //在i,j相遇的地方填入基准值
return i;
}
//挖坑法2
int Partition_DigII(vector<int> &a, int left, int right){
int i = left; //从左边开始
int j = right; //从右边开始
int key = a[left]; //将最左边的数设为基准值
while(i != j){
while(i < j && a[j] >= key) //必须先动右边的 因为取的基准值在左边
j--; //向左寻找直到找到比基准值小的
swap(a[i], a[j]); //交换
i++; //看下一个（可以省略）
while(i < j && a[i] <= key) //再动左边的
i++; //向右寻找直到找到比基准值大的
swap(a[i], a[j]); //交换
j--; //看下一个（可以省略）
}
/* 一轮循环后基准值所在位置左边的数都比基准值小,右边的都比基准值大 */
/* i等于j时跳出循环 当前基准值此时在下标为i的位置(合适的位置) */
return i; //返回基准值合适位置
}
前后指针法同样需要两个指针，一个是 pre ，一个是 curr 。 pre 最后找到的是划分后左半部分最后一个小于基准值的元素。 1、一开始我们一般将前指针 pre 指向待排序序列的第一个元素，后指针 curr 指向 pre 后面的一个元素.
2、然后我们让 后指针 curr 去寻找小于当前基准值的元素，若找到这个元素，此时需要将这个小于基准值的元素和当前 前指针 pre 后一个的位置的元素进行交换，即与 pre + 1 位置的元素进行交换，同时前指针 pre 也往后移动一步.
3、在上述过程中我们需要保持 curr <= r ，当 curr > r 退出循环时，需要将当前 pre 所指向的元素和基准值进行交换。最后返回这个pre，即为我们划分的位置.
//前后指针法
int Partition_PreAndCurr(vector<int> &a, int left, int right){
int pre = left; //pre最后找到左半部分最后一个小于基准值的元素
int curr = pre + 1; //curr找到pre指向元素之后的下一个小于基准值的元素
int key = a[left];
while(curr <= right){
if(a[curr] < key && ++pre != curr) //当a[curr]>=key时pre保持不动,直到最后curr找到下一个小于基准值的元素
swap(a[curr], a[pre]); //pre往后移动到其下一个位置,并交换前后指针指向的元素
curr++;
}
swap(a[left], a[pre]); //最后将基准值和此时处于pre位置的小于基准值的元素交换
return pre;
}
假设时间复杂度为 T(n) 。在进行取得划分位置上我们需要消耗 O(n) 的时间，在递归调用快速排序函数上，最好情况下如果每次我们取得的划分位置为n/2的位置，即消耗了 2T(n/2) 的时间。最坏情况下如果每次我们取得的划分位置为首或尾的位置，即消耗 T(n-1)+T(0) 的时间。 故时间复杂度如下 。
对于取基准值，我们发现 如果当前所取的基准值恰好是当前序列中最小的数或者最大的数，那么我们的划分位置必然是首或尾的位置，如果每次都这个亚籽，我们消耗的时间会非常的多，这显然就是最坏情况下的时间复杂度的状况.
我们自然会想到随机取数，这固然是一个很好的办法，但是这个世界充满了无限可能性。假如我们原先最左边的元素并不是最小或最大的一个元素，但是随机取到的元素却恰好是那个最小或最大的元素呢?
(当然随机取数这个方法也是值得尝试的，后续程序中我不会用这个方式实现取基准值的优化，如果有需要，只需要把取基准值的几行代码改成如下就可以了) 。
int random = rand() % (right - left + 1) + left;
swap(a[random], a[left]);
int key = a[left]
三数取中，就是取序列中的最左边，中间，以及最右边三个数进行比较，以这三个数大小为中的元素作为基准值。这样可以更大程度上避免划分位置不好的情况，即使其并不能彻底避免，但是是一个很好地办法.
int GetMid(int a[], int left, int right){
int mid = (left + right)>>1;
if(a[left] < a[mid])
if(a[mid] < a[right])
return mid; //mid为中间值
else
if(a[left] < a[right])
return right; //right为中间值
else
return left; //left为中间值
else
if(a[mid] > a[right])
return mid; //mid为中间值
else
if(a[left] > a[right])
return right; //right为中间值
else
return left; //left为中间值
}
#include<iostream>
#include<vector>
#include<time.h>
using namespace std;
/* 1 */
//左右指针法
int Partition_Hoare(vector<int> &a, int left, int right){
int i = left;
int j = right;
int key = a[left];
while(i != j){
while(i < j && a[j] >= key) //向左找到小于基准值的值的下标
j--;
while(i < j && a[i] <= key) //向右找到大于基准值的值的下标
i++;
swap(a[i], a[j]);
}
/* i等于j时跳出循环 当前基准值此时在下标为i的位置(合适的位置) */
swap(a[left], a[i]); //最左边的元素变为处于当前合适位置的元素,把基准值放在合适位置
return i; //返回合适位置(i,j都可以)
}
/* 2 */
//挖坑法1
int Partition_DigI(vector<int> &a, int left, int right){
int i = left;
int j = right;
int key = a[left];
while(i != j){
while(i < j && a[j] >= key) //必须先动右边的 因为取的基准值在左边
j--; //向左寻找直到找到比基准值小的
a[i] = a[j]; //挖坑 填入比基准值小的值
while(i < j && a[i] <= key) //再动左边的
i++; //向右寻找直到找到比基准值大的
a[j] = a[i]; //挖坑 填入比基准值大的值
}
/* i等于j时跳出循环 下标为i的位置即为合适的插入位置 */
a[i] = key; //在i,j相遇的地方填入基准值
return i;
}
//挖坑法2
int Partition_DigII(vector<int> &a, int left, int right){
int i = left; //从左边开始
int j = right; //从右边开始
int key = a[left]; //将最左边的数设为基准值
while(i != j){
while(i < j && a[j] >= key) //必须先动右边的 因为取的基准值在左边
j--; //向左寻找直到找到比基准值小的
swap(a[i], a[j]); //交换
i++; //看下一个（可以省略）
while(i < j && a[i] <= key) //再动左边的
i++; //向右寻找直到找到比基准值大的
swap(a[i], a[j]); //交换
j--; //看下一个（可以省略）
}
/* 一轮循环后基准值所在位置左边的数都比基准值小,右边的都比基准值大 */
/* i等于j时跳出循环 当前基准值此时在下标为i的位置(合适的位置) */
return i; //返回基准值合适位置
}
/* 3 */
//前后指针法
int Partition_PreAndCurr(vector<int> &a, int left, int right){
int pre = left; //pre最后找到左半部分最后一个小于基准值的元素
int curr = pre + 1; //curr找到pre指向元素之后的下一个小于基准值的元素
int key = a[left];
while(curr <= right){
if(a[curr] < key && ++pre != curr) //当a[curr]>=key时pre保持不动,直到最后curr找到下一个小于基准值的元素
swap(a[curr], a[pre]); //pre往后移动到其下一个位置,并交换前后指针指向的元素
curr++;
}
swap(a[left], a[pre]); //最后将基准值和此时处于pre位置的小于基准值的元素交换
return pre;
}
/* 4 */
//取基准值的优化 三数取中
int GetMid(int a[], int left, int right){
int mid = (left + right)>>1;
if(a[left] < a[mid])
if(a[mid] < a[right])
return mid; //mid为中间值
else
if(a[left] < a[right])
return right; //right为中间值
else
return left; //left为中间值
else
if(a[mid] > a[right])
return mid; //mid为中间值
else
if(a[left] > a[right])
return right; //right为中间值
else
return left; //left为中间值
}
//左右指针法 三数取中优化
int Partition_Better(vector<int> &a, int left, int right){
int pos = GetMid(a, left, right);
swap(a[pos], a[left]); //将取得的基准值和第一个位置交换
int i = left;
int j = right;
int key = a[left];
while(i != j){
while(i < j && a[j] >= key)
j--;
while(i < j && a[i] <= key)
i++;
swap(a[i], a[j]);
}
swap(a[i], a[left]);
return i;
}
/*******************************************************************/
void Quick_Sort(vector<int> &a, int left, int right){
if( left >= right )
return;
//int i = Partition_Hoare(a, left ,right); //分割 C(n) = n - 1
//int i = Partition_DigI(a, left, right);
//int i = Partition_DigII(a, left, right);
//int i = Partition_PreAndCurr(a, left, right);
int i = Partition_Better(a, left, right);
Quick_Sort(a, left, i - 1); //递归左边的部分
Quick_Sort(a, i + 1, right); //递归右边的部分
}
void show(vector<int> &v){
for(auto &x : v)
cout<<x<<" ";
cout<<endl;
}
main(){
vector<int> v;
srand((int)time(0));
int n = 50;
while(n--)
v.push_back(rand() % 100 + 1);
show(v);
Quick_Sort(v, 0, v.size() - 1);
cout<<endl<<endl;
show(v);
}
最后此篇关于[排序算法]快速排序(C++)(含三种写法)的文章就讲到这里了,如果你想了解更多关于[排序算法]快速排序(C++)(含三种写法)的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
27
4
0
我正在尝试对每个条目有多个值的关联数组进行排序。 例如 [0] => stdClass Object ( [type] => node [sid] => 158 [score] => 0.059600
我在 mysql 中有“日期”列以这种格式保存日期 2014 年 9 月 17 日(日-月-年) 我需要对它们进行升序排序，所以我使用了这个命令: SELECT * FROM table ORDER
我目前正在将 MySQL 存储过程重写为 MS SQL 存储过程，但遇到了问题。 在 MySQL 存储过程中，有一个游标，它根据最近的日期 (effdate) 选择一个值并将其放入变量 (thestt
我想要 gwt r.QuestionId- 排序。但是我得到未排序的 QuestionId 尽管我提到了 QuestionId ASC 的顺序。 SELECT r.QuestionId,
我有一个关于在 scandir 函数中排序的基本问题。到目前为止，我阅读了 POSIX readdir 的手册页，但没有找到有关订购保证的具体信息。 但是当我遍历大目录(无法更改，只读)时，我在多个系
基本上我必须从 SQL 数据库中构建项目列表，但是用户可以选择对 7 个过滤器的任意组合进行过滤，也可以选择要排序的列以及按方向排序。 正如您可以想象的那样，这会以大量不同的组合进行编码，并且数据集非
我有两张 table 。想象第一个是一个目录，包含很多文件(第二个表)。 第二个表(文件)包含修改日期。 现在，我想选择所有目录并按修改日期 ASC 对它们进行排序(因此，最新的修改最上面)。我不想显
我想先根据用户的状态然后根据用户名来排序我的 sql 请求。该状态由 user_type 列设置: 1=活跃，2=不活跃，3=创始人。 我会使用此请求来执行此操作，但它不起作用，因为我想在“活跃”成员
在 C++ 中，我必须实现一个“类似 Excel/Access”(引用)的查询生成器，以允许对数据集进行自定义排序。如果您在 Excel 中使用查询构建器或 SQL 中的“ORDER BY a, b,
我面临这样的挑战: 检索按字段 A 排序的文档 如果字段 B 存在/不为空 . 否则 按字段排序 C. 在 SQL 世界中，我会做两个查询并创建一个 UNION SELECT，但我不知道如何从 Mon
我想对源列表执行以下操作: map 列表 排序 折叠 排序 展开 列表 其中一些方法(例如map和toList)是可链接的，因为它们返回非空对象。但是，sort 方法返回 void，因为它对 List
我制作了一个用于分析 Windows 日志消息编号的脚本。 uniq -c 数字的输出很难预测，因为根据数字的大小会有不同的空白。此时，我手动删除了空白。 这是对消息进行排序和计数的命令: cat n
我有以下词典: mydict1 = {1: 11, 2: 4, 5: 1, 6: 1} mydict2 = {1: 1, 5: 1} 对于它们中的每一个，我想首先按值(降序)排序，然后按键(升序)排序
我刚刚开始使用泛型，目前在对多个字段进行排序时遇到问题。 案例: 我有一个 PeopleList 作为 TObjectList我希望能够通过一次选择一个排序字段，但尽可能保留以前的排序来制作类似 Ex
有没有办法在 sql 中组合 ORDER BY 和 IS NULL 以便我可以在列不为空时按列排序，但如果它为null，按另一列排序？ 最佳答案 类似于: ORDER BY CASE WHEN
我有一个包含 2 列“id”和“name”的表。 id 是常规的自动增量索引，name 只是 varchar。 id name 1 john 2 mary 3 pop 4 mary 5 j
场景 网站页面有一个带有分页、过滤、排序功能的表格 View 。 表中的数据是从REST API服务器获取的，数据包含数百万条记录。 数据库 REST API 服务器 Web 服务器 浏览器 问
假设我有一本字典，其中的键(单词)和值(分数)如下: GOD 8 DONG 16 DOG 8 XI 21 我想创建一个字典键(单词)的 NSArray，首先按分数排序，然后按字
如何在 sphinx 上通过 sql 命令选择前 20 行按标题 WEIGHT 排序，接下来 20 行按标题 ASC 排序(总共 40 个结果)，但不要给出重复的标题输出。 我尝试了这个 sql 命令
我有一个奇怪的问题，当从 SQLite 数据库中选择信息并根据日期排序时，返回的结果无效。 我的SQL语句是这样的: Select pk from usersDates order by dateti
我是一名优秀的程序员,十分优秀！