快速排序是对冒泡排序的一种改进。它的基本思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
假设待排序的序列为{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 }