首页 > > 程序设计 > C/C++ >

快速排序

2018-06-17 23:03:47来源：未知阅读 ()

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

假设待排序的序列为{a[L],a[L+1],a[L+2],……,a[R]}，首先任意选取一个记录（通常可选中间一个记作为枢轴或支点），然后重新排列其余记录，将所有关键字小于它的记录都放在左子序列中，所有关键字大于它的记录都放在右子序列中。由此可以将该“支点”记录所在的位置mid作分界线，将序列分割成两个子序列和。这个过程称作一趟快速排序（或一次划分）。

一趟快速排序的具体做法是：附设两个指针i和j，它们的初值分别为L和R，设枢轴记录取mid，则首先从j所指位置起向前搜索找到第一个关键字小于的mid的记录，然后从i所指位置起向后搜索，找到第一个关键字大于mid的记录，将它们互相交换，重复这两步直至i>j为止。

快速排序的时间的复杂性是O(nlog2n)，速度快,但它是不稳定的排序方法。就平均时间而言，快速排序是目前被认为是最好的一种内部排序方法

由以上讨论可知，从时间上看，快速排序的平均性能优于前面讨论过的各种排序方法，但快速排序需一个栈空间来实现递归。若每一趟排序都将记录序列均匀地分割成长度相接近的两个子序列，则栈的最大深度为log(n+1)。

 1 #include<iostream>
 2 #include<algorithm> 
 3 using namespace std;
 4 int a[10001];
 5 
 6 int n;
 7 void qsort(int l,int r)
 8 {
 9     int i=l;
10     int j=r;
11     int mid=a[(l+r)/2];
12     do
13     {
14         while(a[i]<mid&&i<=j)
15         {
16             i++;
17         }
18         while(a[j]>mid&&i<=j)
19         j--;
20         if(i<=j)
21         {
22             swap(a[i],a[j]);
23             i++;
24             j--;
25         }
26     }while(i<=j);
27     if(l<j)
28     qsort(l,j);
29     if(i<r)
30     qsort(i,r);
31 }
32 int main()
33 {
34     
35     cin>>n;
36     for(int i=0;i<n;i++)
37     {
38         cin>>a[i];
39     }
40     qsort(0,n-1);
41     for(int i=0;i<n;i++)
42     cout<<a[i]<<" ";
43     return 0;
44 }