快速排序

今年又败给了qsort，还是因为自己以前不重视，重新复习qsort。

快速排序

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

（1）基本思想

快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。假设待排序的序列为{a[l],a[l+1],a[l+2],…,a[r]}，首先任意选取一个记录（通常可选中间一个记作为枢轴或支点），然后重新排列其余记录，将所有关键字小于它的记录都放在左子序列中，所有关键字大于它的记录都放在右子序列中。由此可以将该“支点”记录所在的位置 mid 作分界线，将序列分割成两个子序列和。
这个过程称作一趟快速排序（或一次划分）。
（2）排序过程一趟快速排序的具体做法是：

①附设两个指针 i 和 j，它们的初值分别为 l 和 r，设枢轴记录取 mid；

②首先从 j 所指位置起向前搜索找到第一个关键字小于的 mid 的记录；

③然后从 i 所指位置起向后搜索，找到第一个关键字大于 mid 的记录，将它们互相交换；
④重复②③步直至 i>j 为止。

（3）算法实现输入一列数，按照从小到大输出。

 1 #include <iostream>
 2 using namespace std;
 3 
 4 void qsort(int, int);
 5 int a[101];
 6 
 7 int main()
 8 {
 9     int n, i;
10     cin >> n;
11     for(i=1;i<=n;i++)
12         cin >> a[i];
13     qsort(1, n);
14     for(i=1;i<=n;i++)
15         cout << a[i] << " ";
16     cout << endl; 
17     
18     return 0;
19 }
20 
21 void qsort(int l, int r)
22 {
23     int i, j, mid, p;
24     i = l;
25     j = r;
26     mid = a[(l+r)/2];        //将当前序列在中间位置的数定义为分隔数 
27     do{
28         while(a[i] < mid)    //在左半部分寻找比中间数大的数 
29             i++;
30         while(a[j] > mid)    //在右半部分寻找比中间数小的数
31             j--;
32         if(i<=j){            //若找到一组与排序目标不一致的数对，则交换它们 
33             p = a[i]; a[i] = a[j]; a[j] = p;
34             i++; j--;        //继续找 
35         }
36     }while(i<=j);            //注意这里不能少了等号 
37     
38     if(l < j)
39         qsort(l, j);        //若未到两个数的边界，则递归搜索左右区间 
40     if(i < r)    
41         qsort(i, r);
42     
43 }

快速排序的时间的复杂性是 O(nlog2n)，速度快,但它是不稳定（数值相同的记录经过快速排序后，相对次序可能会发生改变）的排序方法。就平均时间而言，快速排序是目前被认为是最好的一种内部排序方法。由以上讨论可知，从时间上看，快速排序的平均性能优于前面讨论过的各种排序方法，但快速排序需一个栈空间来实现递归。若每一趟排序都将记录序列均匀地分割成长度相接近的两个子序列，则栈的最大深度为 log(n+1)。