对快速排序的理解以及相关c++代码
2019-08-16 08:00:54来源:博客园 阅读 ()
对快速排序的理解以及相关c++代码
快速排序:在一组数据中,可以将左边的数字当作枢轴(右边也可以),接下来要做的就是,先从右边找到比枢轴小的数,
再从左边找到比枢轴大的数,接着将这两个数进行交换,重复上述步骤找出所有符合条件的数进行交换,
最后将枢轴放到比枢轴大的数与比枢轴小的数之间。之所以要从右边开始找,并且找到比枢轴小的数是因为交换后小的数就在枢轴的左边了。
下面举个比较特殊的例子希望能增加理解。
1 |
9 |
8 |
5 |
6 |
7 |
3 |
2 |
0 |
4 |
先从右往左找到比1小的第一个数字为0,此时的索引位置j=8,再从左往右找到比1大的第一个数字为9,此时的索引位置i=1,此时交换0和9,
1 |
0 |
8 |
5 |
6 |
7 |
3 |
2 |
9 |
4 |
继续下一次重复任务
先从右往左找到比1小的第一个数字为0,此时的索引位置,j=1,而从左往右找到比1大的第一个数字8此时的索引i=2,很明显i>j,这是不允许的,
所以这时候就可以让所选的枢轴1与j位置上的值交换(也就是把枢轴放到两组数字中间)
0 |
1 |
8 |
5 |
6 |
7 |
3 |
2 |
9 |
4 |
先看1左边的情况此时就一个数字1已经排好,
再看右边的情况,从j+1的位置开始到最后,且以j+1的位置为枢轴,
从右边找比8小的第一个数字为4,索引j=9,从左边找比8大的第一个数字为9,索引i=8,交换4和9
8 |
5 |
6 |
7 |
3 |
2 |
4 |
9 |
按照上述逻辑继续
9 |
5 |
6 |
7 |
3 |
2 |
8 |
9 |
8的左边
4 |
5 |
6 |
7 |
3 |
2 |
从右往左找比4小的数字,从左往右找比4大的数字,并交换
4 |
2 |
6 |
7 |
3 |
5 |
继续
4 |
2 |
3 |
7 |
6 |
5 |
继续
3 |
2 |
4 |
7 |
6 |
5 |
8的左边又被4分成两段
8的右边
9 |
4的左边
3 |
2 |
2 |
3 |
4的右边
7 |
6 |
5 |
这一次同样以左边为枢轴,从右边找到5,左边会一直找知道找到5所在的位置此时j=i
跳出循环直接把7与j的位置交换,让枢纽7将这3个数分开,实际上7的右边没有值了
只需考虑7的左边
5 |
6 |
7 |
所以最终就排好了
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
以下是c++带模版的快速排序代码
1 #include <iostream> 2 3 using namespace std; 4 5 template<class T> 6 void QuickSort(T *q, int left, int right); 7 8 int main() 9 { 10 int a[]={1,9,8,5,6,7,3,2,0,4}; 11 QuickSort(a, 0, 9); 12 for(int i=0; i<10; i++) 13 cout << a[i] << endl; 14 return 0; 15 } 16 17 template<class T> 18 void QuickSort(T *q, const int left, const int right) 19 { 20 if(left<right) 21 { 22 int i=left, j=right; 23 int temp = q[left]; 24 while(i<j) 25 { 26 while(q[j]>=temp && i<j) 27 { 28 j--; 29 } 30 while(q[i]<=temp && i<j) 31 { 32 i++; 33 } 34 swap(q[i],q[j]); 35 } 36 swap(q[left], q[j]); 37 QuickSort(q, left, j-1); 38 QuickSort(q, j+1, right); 39 } 40 }
原文链接:https://www.cnblogs.com/yang901112/p/11332763.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++冒泡排序 (基于函数模板实现) 2020-05-31
- 排序汇总 2020-05-05
- 前缀和 2020-05-04
- 二叉排序树 2020-05-02
- 透彻理解C++11新特性:右值引用、std::move、std::forward 2020-04-30
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash