首页 > 代码库 > 快速排序详解

快速排序详解

说一说快速排序

 

快速排序,实际中最常用的一种排序算法,速度快,效率高,在N*logN的同等级算法中效率名列前茅。·

 

基本思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分所有数据要小,然后再按此方法对这两部分数据分别进行快速排序。整个排序过程可以递归进行,以此达到整个数据变成有序序列。

技术分享

将数列变成上述形式,这一步很关键,做好这一步,才能对主元左右的部分进行递归调用。以下是实现这一部分的代码:

 1 int partition_sort(int arr[],int l,int r)//l是数组最左边,r为最右边 
 2 {
 3     int j=l;//设计标记 
 4     int t=arr[l];//设置主元 
 5 
 6     for(int i=l+1;i<=r;i++)
 7     {
 8         if(arr[i]<t){
 9             swap(arr[j+1],arr[i]);
10             j++;
11         }
12     }
13     
14     swap(arr[l],arr[j]);
15     return j;
16 }

上述代码中,我把最左边的元素当作主元,这样的代码对大多数排序都很高效,但是不排除个别情况(当数组近乎有序或者当数组内有大量重复元素),这时,我们的排序算法相比于归并排序显得并不是那么高效,这和我们的排序算法原理密不可分,细细分析,当数组近乎有序时,我们的快速排序竟然退化到了O(n^2)级别,这显然是非常不高效的。

 要想实现上述不足的优化,我们可以将主元随机选择,或者采用其他方式的快速排序(双路快速排序,三路快速排序),本篇内容仅作为学习快排的基本思想和基本实现,不深入涉及,有兴趣的读者可查阅资料了解。

 

下面是全部的实现代码:

 1 #include <iostream>
 2 #include <math.h>
 3 using namespace std;
 4 //实现函数,用于partition的递归 
 5 int partition_sort(int arr[],int l,int r)//l是数组最左边,r为最右边 
 6 {
 7     int j=l;//设计标记 
 8     int t=arr[l];//设置主元 
 9 
10     for(int i=l+1;i<=r;i++)
11     {
12         if(arr[i]<t){
13             swap(arr[j+1],arr[i]);
14             j++;
15         }
16     }
17     
18     swap(arr[l],arr[j]);
19     return j;
20 }
21 //实现递归的调用函数 
22 void partition(int arr[],int l,int r)
23 {
24     if(l>=r)return ;
25     
26     int p=partition_sort(arr,l,r);
27     partition(arr,l,p-1);
28     partition(arr,p+1,r);
29 }
30 
31 int main()
32 {
33     int a[5];
34     for(int i=0;i<5;i++)
35     {
36         cin>>a[i];    
37     } 
38     partition(a,0,4);
39     
40     
41     for(int i=0;i<5;i++)
42     {
43         cout<<a[i]<<" ";    
44     } 
45     return 0;    
46 } 

 

快速排序详解