排序算法系列之【快排算法】

　　快速排序的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。请看代码：

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int Partion(int a[], int low, int high){
 5     int pivotkey;
 6     pivotkey = a[low];
 7     while (low < high){
 8         while (low < high&&pivotkey <= a[high])
 9             high--;
10         swap(a[low], a[high]);
11         while (low < high&& pivotkey >= a[low])
12             low++;
13         swap(a[low], a[high]);
14     }
15     return low;
16 }
17 
18 void QSort(int a[], int low, int high){
19     int pivot;
20     if (low < high){
21         pivot = Partion(a, low, high);
22         cout << endl;
23         QSort(a, low, pivot - 1);
24         QSort(a, pivot + 1, high);
25     }
26 }
27 
28 
29 void QuickSort(int a[], int n){
30     QSort(a, 0, n - 1);
31 }
32 
33 int main(){
34     int a[] = { 9, 5, 1, 6, 2, 3, 8, 4, 7,12,11,10 };
35     int n = 12;
36     QuickSort(a, n);
37     for (int i = 0; i < 12; i++){
38         cout << a[i] << " ";
39     }
40     cout << endl;
41     return 0;
42 }

上图是每进行一次递归后的序列。