0

算法整理(二)—快速排序的两种实现方式:双边扫描和单边扫描

首先简单谈下快速排序的特点,时间复杂度O(nLog n),最差时间复杂度O(n^2),平均时间O(nLog n).因为用到了函数栈,空间复杂度为O(lg n),最差为O(n).是一种不稳定的排序方法。基本思想是分治法,这位大大的http://blog.csdn.net/morewindows/article/details/6684558 讲的非常清楚了,分治法+挖坑法,我就不多说了。就是以某个数为参照,使得左边的都小于他,右边的数都大于他。然后对他的左右两个区间采取同样的方法进行递归。

就其整体实现而言,有两大种思路,一是双边扫描,二是单边扫描。下面分别来上程序:

一、双边扫描

双边扫描是谭浩强书中的方法,个人觉得比下面的单边扫描更好理解,也是博文里采用的方法。下面看程序:

 

  1. <span style=“font-family:Comic Sans MS;font-size:18px;”>void quickSort1(int* x, int l, int r){  
  2.   
  3.     if(l < r){  
  4.         int i = l, j = r, key = x[l];  
  5.         while(i < j){  
  6.             while( i < j && x[j] >= key){  
  7.                 j–;  
  8.             }  
  9.             if(i < j){  
  10.                 x[i++] = x[j];  
  11.             }  
  12.             while(i < j && x[i] <= key){  
  13.                 i++;  
  14.             }  
  15.             if(i < j){  
  16.                 x[j–] = x[i];  
  17.             }  
  18.         }  
  19.         cout<<“i = “ <<i<<” j = “<<j<<endl;  
  20.         x[i] = key;  
  21.         quickSort1(x, l, i-1);  
  22.         quickSort1(x, i+1, r);  
  23.     }  
  24.   
  25. }</span>  

双边扫描非常直观,首先进到程序里判断是否l<r,当满足条件才进去。这也是用递归的一个必要条件,一定要让函数有尽头,有边界。然后进入大while循环,接着进入小while循环,先从右边找,只要满足数字大于key就一直让j往左移。直到第一个不满足条件的,就是第一个小于key的数跳出while循环,将它放在左边挖的“坑”上。同时让坑的索引+1,接着从左边开始扫描,找到第一个大于key的数,再将它填到右边的坑上。右边的坑索引-1,接着再从右边扫描。直到最后跳出大while循环,此时i = j。也就是完成了一次快速排序的扫描。之后将最初的key放到x[i],其实放到x[j]也是一样的。因为i等于j么,此时!然后进行递归,对区间[l, i – 1], [i+1, r]进行同样的操作。

 

双边排序的要点: 1、最初的if一定要有,这是最后递归出来的标志位。2,为了找到一个数使它的左边都大于它,右边都小于它,要多次循环,这个循环就是大while循环。3、双边排序不需要swap,即无需交换。

 

二、单边扫描

上面的双边排序,出来一次大while循环,要从两边进行多次。单边扫描,则只需从左走到右就能完成一次 快排。

 

  1. <span style=“font-family:Comic Sans MS;font-size:18px;”>void quickSort2(int x[], int l, int r){  
  2.     if(l >= r)  
  3.         return;  
  4.     int m = l;  
  5.     for(int i = l + l; i <= r; i++ ){  
  6.         if(x[i] < x[l]){  
  7.             swap2(x[++m], x[i]);  
  8.         }  
  9.     }  
  10.     swap2(x[l], x[m]);  
  11.     quickSort2(x, l, m – 1);  
  12.     quickSort2(x, m + 1, r);  
  13.   
  14. }  
  15. void swap2(int &a,int &b){  
  16.     if(a==b) return;//对同一地址的数据交换,会使其结果为0  
  17.     a=a^b;  
  18.     b=a^b;  
  19.     a=a^b;  
  20. }</span>  

代码是不是更简单了?程序先进行判断,如果l>=r直接return,这点跟双边扫描的if一个意思,都是为递归创造结束的标志。然后用m记录最左边的那个的索引,这里默认的是第一个,即x[l]的索引。[注,m的初始值不一定指向key!,仅仅是指向最左边的。]然后进入扫描,直接从l + 1开始,如果右边的小于key,就让x[++m]和x[i]交换。如果右边的大于key,则不进行任何操作。这里有个特例,如果l = 0, 则m = 0.如果x[1]小于x[0],则让x[1] 和x[1]进行交换,也就等于没交换。如果数组是5 4 3 2 1,则这里的交换就失效了。 再往后看,直到for循环结束,走出循环,让最后m指的位置的数和最初的key进行交换。如上面 5 4 3 2 1,则第一次快排的结果是 1 4 3 2 5,只有for出来后的那次swap才起作用。这里的m有个特殊含义,即指向小于key的最右边的那个数。所以出来后才用它(x[m])和key(即x[l])进行交换。

 

单边扫描的特点:

1、程序需要交换;

2、更有冒泡法的色彩;冒泡的目的不是让最大的数沉到最右边,而是让小于key的都左移,找到分界索引m。使之和key进行交换。

3、此版本的的单边扫描属于最基础的,还可以优化。

本想测出两个算法的时间 消耗差异,遗憾的是c++获得程序运行时间太费劲了,弄半天没弄成。下面附上完整程序:

 

  1. <span style=“font-family:Comic Sans MS;font-size:18px;”>//============================================================================  
  2. // Name        : QuikSort.cpp  
  3. // Author      : YanZi  
  4. // Version     :  
  5. // Copyright   : Your copyright notice  
  6. // Description : Hello World in C++, Ansi-style  
  7. //============================================================================  
  8.   
  9. #include <iostream>  
  10. #include <malloc.h>  
  11.   
  12. using namespace std;  
  13. void swap1(int a, int b);  
  14. void printArray(int* in, int n);  
  15.   
  16. void quickSort1(int* x, int l, int r);//双边扫描,快速排序  
  17. void quickSort2(int x[], int l, int r);//单边扫描,快速排序  
  18. void swap2(int &a,int &b); //交换,在MinGW上必须采用此方法,swap1无效  
  19.   
  20.   
  21. #define N 8 //数组的长度  
  22.   
  23. int main() {  
  24.     int* input = NULL;  
  25.     input = (int*)malloc(N * sizeof(int));  
  26.     if(input == NULL){  
  27.         cout<<“内存溢出”<<endl;  
  28.     }  
  29.     for(int i = 0; i < N; i++){  
  30.         input[i] = rand();  
  31.     }  
  32.     //  int input[] = {55, 41, 59, 26, 53, 58, 97, 93};  
  33.   
  34.     cout<<“原始数据:”<<endl;  
  35.     printArray(input, N);  
  36.   
  37.     quickSort2(input, 0, N-1);  
  38.     printArray(input, N);  
  39.   
  40.     return 0;  
  41. }  
  42. void swap1(int a, int b){  
  43.     int temp = a;  
  44.     a = b;  
  45.     b = temp;  
  46. }  
  47. void printArray(int * in, int n){  
  48.     if(in == NULL){  
  49.         return;  
  50.     }  
  51.     for(int i = 0; i<n; i++){  
  52.         cout<<” “<<in[i];  
  53.     }  
  54.     cout<<endl;  
  55.   
  56. }  
  57.   
  58. void quickSort1(int* x, int l, int r){  
  59.   
  60.     if(l < r){  
  61.         int i = l, j = r, key = x[l];  
  62.         while(i < j){  
  63.             while( i < j && x[j] >= key){  
  64.                 j–;  
  65.             }  
  66.             if(i < j){  
  67.                 x[i++] = x[j];  
  68.             }  
  69.             while(i < j && x[i] <= key){  
  70.                 i++;  
  71.             }  
  72.             if(i < j){  
  73.                 x[j–] = x[i];  
  74.             }  
  75.         }  
  76.         cout<<“i = “ <<i<<” j = “<<j<<endl;  
  77.         x[i] = key;  
  78.         quickSort1(x, l, i-1);  
  79.         quickSort1(x, i+1, r);  
  80.     }  
  81.   
  82. }  
  83. void quickSort2(int x[], int l, int r){  
  84.     if(l >= r)  
  85.         return;  
  86.     int m = l;  
  87.     for(int i = l + l; i <= r; i++ ){  
  88.         if(x[i] < x[l]){  
  89.             swap2(x[++m], x[i]);  
  90.         }  
  91.     }  
  92.     swap2(x[l], x[m]);  
  93.     quickSort2(x, l, m – 1);  
  94.     quickSort2(x, m + 1, r);  
  95.   
  96. }  
  97. void swap2(int &a,int &b){  
  98.     if(a==b) return;//对同一地址的数据交换,会使其结果为0  
  99.     a=a^b;  
  100.     b=a^b;  
  101.     a=a^b;  
  102. }</span>  

天边的星星