十大算法系列之(一)——快速排序

&1 思想和时间复杂度

分治法思想(Divide and Conquer)，这是算法导论里面讲的第一个算法思想，很经典也很实用。时间复杂度分析，最好是O(n)，最差是O(n²)，平均性能是O(nlog(n))。

 

&2 算法

　　#1. 在待排数列中(n个数)选择一个基准数(理论上可以任意)；

　　#2. 剩下的 n-1 个数与基准数对比，比基准数小的放左边，反之在右边；(也有人称为划分操作)

　　#3. 一轮循环结束，此时基准数是位于它的最终位置；

　　#4. 重复步骤#1~#3，直到最后一个基准数左边和右边的元素个数为0或1，则排序完成。

 

&3 举例

 

&4 c++程序实现

1 #include<iostream> 2 #include<vector> 3 4 using namespace std; 5 6 void QuickSort(vector<int > &A, int p, int q); 7 int Partition(vector<int> &a, int p, int q); 8 void swapv(int &a, int &b); 9 10 int main(){ 11 　　vector<int> seti = { 13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11 }; 12 　　int len = seti.size(); 13 　　QuickSort(seti,0,len-1); 14 15 　　cout << "The sorted array is: \n"; 16 　　for (vector<int>::iterator iter = seti.begin(); iter != seti.end(); iter++) 17 　　cout << *iter << "\t"; 18 　　cout << endl; 19 20 　　system("Pause"); 21 　　return 0; 22 } 23 24 void QuickSort(vector<int > &A,int p,int q){ 25 　　if (p < q){ 26 　　　　int pos = Partition(A, p, q); 27 　　　　QuickSort(A, p, pos - 1); 28 　　　　QuickSort(A, pos + 1, q); 29 　　} 30 } 31 32 int Partition(vector<int> &a,int p, int q){ 33 　　int val = a[p]; 34 　　int j = q + 1; 35 　　for (int i = q; i > p-1; i--){ 36 　　　　if (a[i]>val){ 37 　　　　　　j = j - 1; 38 　　　　　　if (i != j) 39 　　　　　　　　swapv(a[j],a[i]); 40 　　　　} 41 　　} 42 43 　　if (p != j - 1) 44 　　　　swapv(a[p],a[j-1]); 45 46 　　return j - 1; 47 } 48 49 void swapv(int &a,int &b){ 50 　　a = a + b; 51 　　b = a - b; 52 　　a = a - b; 53 } 快速排序

 

 

&5 程序实现结果截图

如果对代码优化，亲有更好的想法，咱可以一起学习讨论哦！