分治思想的应用：C++实现快速排序和随机化的快速排序

分治思想的应用：C++实现快速排序和随机化的快速排序

原创 2014年09月08日 14:04:49
  • 947

1. 快速排序时冒泡排序的升级版

都知道冒泡排序需要从0-n-1轮n-1次两两比较。并且进行多次两两交换才能得到最后的排列结果。需要 

for(i from 0 to n-1)

   for(j from i+1 to n-1)

   compare(a[i], a[j])  and switch(a[i], a[j])

算法复杂度为O（n power 2）

快速排序通过对冒泡的改进，j将i和j从两边移到中间，使得第一次循环结果为以选取的中心值为中心。如果需要升序，

left = 0, right = n-1, pivot = a[left]

while(i< =j)

{

  if(a[j]<pivot) a[i]= a[i] ， i++小的往左边移动

      if(a[i]>pibot) a[j] = a[j], j++， 大的往右移动

      else i++     

 else j++

}

quicksort(a,left,i-1);

quicksort(a,i+1,right);


快速排序则添加入循环迭代思想， 不断的拆分这个数组。

①选取中心元素的问题

选取第一个数为中心元素

②如何划分问题
③如何重复步骤①②将所有数据排序

使用递归

函数头：quicksort(inta[],intleft,intright)

①初始化：i=left;j=right;inttemp=a[left];
②划分：do{一次划分} while(i<j);
③中心元素填入：a[i]=temp;
④递归地对剩余段作快速排序

quicksort(a,left,i-1);

quicksort(a,i+1,right);

2. 如何随机排列数列？

用这个 random_shuffle() 可以得到一个随即排序：
先用数组构造一个 vector 容器，
然后给 random_shuffle() 算法传递容易的首尾迭代器即可 

参考地址： http://www.cnblogs.com/afarmer/archive/2011/05/01/2033715.html

如何从一个数列中随机得到一个数？

#include <iostream> 
#include <stdlib.h> 
#include <time.h>  
using namespace std;  
int main() 
{  
srand((unsigned)time(NULL));  
for(int i = 0; i < 10;i++ )  
        cout << rand() << ' ';  
cout << endl;  
return 0; 
}

产生一定范围随机数的通用表示公式 
要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 
要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a

3.下面实现随机化的快速排序

[cpp] view plain copy
 
  1. #include <iostream>  
  2. #include <stdio.h>  
  3. #include <stdlib.h>  
  4. #include <time.h>  
  5. using namespace std;  
  6. bool static Inc(const int& x, const int& y)  
  7. {  
  8.     return x<y;  
  9. }  
  10. bool static Dec(const int& x, const int& y)  
  11. {  
  12.     return x>y;  
  13. }  
  14. //template<bool  cmp(const int&, const int&)>  
  15. void quicksort(int a[],int left,int right)  
  16. {   int i,j;  
  17.     if(left<right)  
  18.     {   i=left;j=right;  
  19.         int temp=a[left]; //store the pivot number, it can be anyone of the array a[]  
  20.         do  
  21.         {   while(Inc(a[j],temp) && i<j)//Inc for des  
  22.             j--; //j一直减直到可以交换  
  23.             if(i<j)  
  24.             {   a[i]=a[j];//blank postion i = a[j]  
  25.                 i++;  
  26.             }  
  27.             while(Inc(temp, a[i]) && i<j)//i一直加直到a[i]大于j  
  28.             i++;  
  29.             if(i<j)  
  30.             {   a[j]=a[i];  
  31.                 j--;  
  32.             }  
  33.         }while(i<j);// do while can make sure the i=j will be executed  
  34.         a[i]=temp;//i =j, only one positon left, so its the last temp  
  35.         quicksort(a,left,i-1);  
  36.         quicksort(a,i+1,right);  
  37.     }  
  38. }  
  39. int main()  
  40. {  
  41.     cout<<"input n"<<endl;  
  42.     int n;  
  43.     scanf("%d",&n);  
  44.     int a[100];  
  45.     cout<<"input "<< n<<" numbers"<<endl;  
  46.     for(int i = 0; i< n; i++)  
  47.     {  
  48.         scanf("%d", a+i);  
  49.     }  
  50.     int left = 0, right = n-1;  
  51.     srand(time(NULL));  
  52.     left = rand()%n;  
  53.     cout<<"random pivot is "<<a[left]<<endl;  
  54.   
  55.     //swap with the first one  
  56.     int tmp;  
  57.     tmp = a[0];  
  58.     a[0]= a[left];  
  59.     a[left] = tmp;  
  60.     quicksort(a,0,n-1);  
  61.   
  62.     cout<<"the result is："<<endl;  
  63.     for(int i = 0; i< n; i++)  
  64.     {  
  65.         cout<<a[i]<<" ";  
  66.     }  
  67.   
  68.     system("pause");  
  69.     return 0;  
  70. }  
[cpp] view plain copy
 
  1. 或者<pre name="code" class="cpp">   if(left<right)  
  2.     {   i=left;j=right;  
  3.         int pivot = a[left]; //store the pivot number, it can be anyone of the array a[]  
  4.         while(i <= j)  
  5.         {  
  6.             if(Inc(a[j],pivot) && i<j)  
  7.             {  
  8.                 a[i] = a[j]; //大的往左边移动  
  9.                 i++;  
  10.                 if(Inc(pivot, a[i]) && i<j)  
  11.                 {  
  12.                     a[j] = a[i];//小的往右边移动  
  13.                     j--;  
  14.                 }  
  15.                 else  
  16.                 {  
  17.                     i++;  
  18.                 }  
  19.             }  
  20.             else  
  21.             {  
  22.             j--;  
  23.             }  
  24.         }  
  25.         a[i]=pivot;//i =j, only one positon left, so its the last temp  
  26.         quicksort(a,left,i-1);  
  27.         quicksort(a,i+1,right);  
  28.     }  


4. 快速排序的变体



注意最后是交换a[i] 和A[r] 不是i+1







[cpp] view plain copy

 






  1. #include <iostream>  
    2. 

  2. #include <stdio.h>  
    3. 

  3. #include <stdlib.h>  
    4. 

  4. #include <time.h>  
    5. 

  5. using namespace std;  
    6. 

  6. bool static Inc(const int& x, const int& y)  
    7. 

  7. {  
    8. 

  8.     return x<y;  
    9. 

  9. }  
    10. 

  10. bool static Dec(const int& x, const int& y)  
    11. 

  11. {  
    12. 

  12.     return x>y;  
    13. 

  13. }  
    14. 

  14. //template<bool  cmp(const int&, const int&)>  
    15. 

  15. void quicksort(int a[], int left, int right)  
    16. 

  16. {   int i,j;  
    17. 

  17.     if(left < right)  
    18. 

  18.     {     
    19. 

  19.         i=left;//j=size -1;  
    20. 

  20.         int pivot = a[left];  
    21. 

  21.         int tmp;  
    22. 

  22.         //int temp=a[i]; //store the pivot number, it can be anyone of the array a[]  
    23. 

  23.         for(j = i+1; j <= right; j++)  
    24. 

  24.         {  
    25. 

  25.             if(a[j]<pivot)  
    26. 

  26.             {  
    27. 

  27.                 if(j> ++i)  
    28. 

  28.                 {  
    29. 

  29.                 tmp = a[j];  
    30. 

  30.                 a[j] = a[i];//sawp i+1 and j  
    31. 

  31.                 a[i]=tmp;  
    32. 

  32.                 }  
    33. 

  33.             }  
    34. 

  34.         }  
    35. 

  35.         tmp = a[i];  
    36. 

  36.         a[i] = a[left];  
    37. 

  37.         a[left] = tmp;  
    38. 

  38.         quicksort(a,left,i-1);  
    39. 

  39.         quicksort(a,i+1,right);  
    40. 

  40.     }  
    41. 

  41.   
    42. 

  42. }  
    43. 

  43. int main()  
    44. 

  44. {  
    45. 

  45.     cout<<"input n"<<endl;  
    46. 

  46.     int n;  
    47. 

  47.     scanf("%d",&n);  
    48. 

  48.     int a[100];  
    49. 

  49.     cout<<"input "<< n<<" numbers"<<endl;  
    50. 

  50.     for(int i = 0; i< n; i++)  
    51. 

  51.     {  
    52. 

  52.         scanf("%d", a+i);  
    53. 

  53.     }  
    54. 

  54.     int left = 0, right = n-1;  
    55. 

  55.     srand(time(NULL));  
    56. 

  56.     left = rand()%n;  
    57. 

  57.     cout<<"random pivot is "<<a[left]<<endl;  
    58. 

  58.   
    59. 

  59.     //swap with the first one  
    60. 

  60.     int tmp;  
    61. 

  61.     tmp = a[0];  
    62. 

  62.     a[0]= a[left];  
    63. 

  63.     a[left] = tmp;  
    64. 

  64.     quicksort(a,0,n-1);  
    65. 

  65.   
    66. 

  66.     cout<<"the result is："<<endl;  
    67. 

  67.     for(int i = 0; i< n; i++)  
    68. 

  68.     {  
    69. 

  69.         cout<<a[i]<<" ";  
    70. 

  70.     }  
    71. 

  71.   
    72. 

  72.     system("pause");  
    73. 

  73.     return 0;  
    74. 

  74. }  
    75. 






                                      


        

	      

	    

	  

	  

	    
      
        【推广】
        免费学中医，健康全家人
      
	  

    

    

          原文地址：https://www.cnblogs.com/caiyishuai/p/13271087.html