对快速排序的理解以及相关c++代码

2019-08-16 08:00:54来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

对快速排序的理解以及相关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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:49.Qt-网络编程之QTCPSocket和QTCPServer(实现简易网络调试助手)

下一篇:博客导航