常用排序算法之—

快速排序的原理：

首先找一个标兵值，等于某一个元素值；遍历数组，将数组分为小于标兵值和大于标兵值的两部分；然后分别对两个部分采用快速排序，递归。

分开数组时，维持一个指针，指向已找到小部分的最后一个元素；一个指针用于遍历。

不稳定排序算法。当数组已经有序时，时间复杂度最差，为O(N²)，平均、最优情况下都为O(N lgN)。

代码如下：

 1 #include <iostream>
 2 using namespace std;
 3 
 4 template<typename T>
 5 void quickSort(T num[], int first, int last)
 6 {
 7     if(first >= last)
 8         return;
 9 
10     T pviot = num[first];
11 
12     int small = first;  //指针，指向已经处理过的小部分的最后一个值
13 
14     for(int i = first + 1; i <= last; ++i)
15     {
16         if(num[i] <= pviot)
17         {
18             ++small;  //将小部分后第一个值和找到的小于标兵的值交换
19             if(small < i)
20             {
21                 swap(num[small], num[i]);
22             }
23         }
24     }
25 
26     swap(num[first], num[small]);
27 
28     quickSort(num, first,     small - 1);
29     quickSort(num, small + 1, last);
30 }
31 
32 int main()
33 {
34     const int n = 5;
35 
36     int    ia[n] = {1, 3, 6, 2, 4};
37     double da[n] = {1.2, 3.4, 6.7, 2.3, 4.5};
38 
39     quickSort(ia, 0, n - 1);
40     quickSort(da, 0, n - 1);
41 
42     for(int i = 0; i < n; ++i)
43         cout << ia[i] << ' ';
44     cout << endl;
45 
46     for(int i = 0; i < n; ++i)
47         cout << da[i] << ' ';
48     cout << endl;
49 
50     return 0;
51 }

常用排序算法之——快速排序

推荐阅读