1.快速排序思想：从一堆数A中找到一个数x，然后把这堆数x分成两堆B,C，B堆的数小于(或小于等于)该数，放在左边，C堆的数大于(或大于等于)该数，放在右边，有可能把该数x单独分开，放在中间。然后对小于(或小于等于)该数的堆B和大于(或大于等于)该数的堆C进行上述相同的操作，直到堆中的数只有一个，不必排序。
2.快速排序随机化：对数x进行随机化选取。即若对a[l]~a[r]进行排序，则从l~r中选择一个数k，使x=a[k]。
3.求Topk(一个数组从小到大排序第k个数)，O(n)。
若数x在堆中的位置i等于k，则输出x；若小于x，则从堆A(数小于等于x)：a[1]~a[i-1]中找；若大于x，则从堆B(数大于x)：a[i+1]~a[n]中找。
设对a[l]~a[r]排一次序需要r-l+1的时间，则最坏时间复杂度：n+n/2+n/4+……+1=2n-1<2n。
快速排序
——Pascal，C，C++ 含解释
1.Pascal：
var n,i:longint;
a:array [..] of longint;
procedure qsort(l,r:longint);
var i,j,x,y:longint;
begin
i:=l; j:=r; x:=a[(l+r) div ];
repeat
while (a[i]<x) do inc(i);
while (a[j]>x) do dec(j);
if (i<=j) then
begin
y:=a[i];
a[i]:=a[j];
a[j]:=y;
inc(i);
dec(j);
end;
until i>j;
if (i<r) then qsort(i,r);
if (j>l) then qsort(j,l);
end;
begin
readln(n);
for i:= to n do
read(a[i]);
qsort(,n);
for i:= to n do
write(i,' ');
writeln;
end.
2.C
#include <stdio.h>
#include <stdlib.h>
#define maxn 100
long a[maxn+];
void qsort_(long l,long r)
{
long i,j,x,y;
i=l; j=r; x=a[(l+r)>>];
while (i<=j)
{
while (a[i]<x) i++;
while (a[j]>x) j--;
if (i<=j)
{
y=a[i];
a[i]=a[j];
a[j]=y;
i++;
j--;
}
}
if (i<r) qsort_(i,r);
if (j>l) qsort_(l,j);
}
int main()
{
long n,i;
scanf("%ld",&n);
for (i=;i<=n;i++)
scanf("%ld",&a[i]);
qsort_(,n);
for (i=;i<=n;i++)
printf("%ld ",a[i]);
printf("\n");
return ;
}
3.C++：
#include <iostream>
#define maxn 100
using namespace std;
long a[maxn+];
void qsort_(long l,long r)
{
long i,j,x,y;
i=l; j=r; x=a[(l+r)>>];
while (i<=j)
{
while (a[i]<x) i++;
while (a[j]>x) j--;
if (i<=j)
{
y=a[i];
a[i]=a[j];
a[j]=y;
i++;
j--;
}
}
if (i<r) qsort_(i,r);
if (j>l) qsort_(l,j);
}
int main()
{
long n,i;
cin>>n;
for (i=;i<=n;i++)
cin>>a[i];
qsort_(,n);
for (i=;i<=n;i++)
cout<<a[i]<<" ";
cout<<endl;
return ;
}
注释版：
1.Pascal：
var n,i:longint;
a:array [..] of longint;
procedure qsort(l,r:longint);
//对a[l]~a[r]的数进行排序
var i,j,x,y:longint;
begin
//x为a[l]~a[r]中的一个数
i:=l; j:=r; x:=a[(l+r) div ];
//i逐渐增加，j逐渐减少，最终i>=j，结束while循环
//保证能有限次结束循环：if (i<=j) {i=i+1; j=j-1;} 如果i<=j，i增加，j减少
//而while (a[i]<x) i++; while (a[j]>x) j=j-; 也是i增加，j减少的操作
repeat
//执行完下面一条语句后，a[l]~a[i-]的数都小于等于x(i=l另当别论)，而a[i]大于等于x。而为什么是小于等于而不是小于，后面有解释。
while (a[i]<x) do inc(i);
//执行完下面一条语句后，a[j+]~a[r]的数都大于等于x(j=r另当别论)，而a[j]小于等于x。而为什么是大于等于而不是大于，后面有解释。
while (a[j]>x) do dec(j);
//*一开始i=l,j=r,i<=j，后来i增加，j减少，因为执行完上面两条语句后，a[l]~a[i-]的数都小于等于x，而a[i]大于等于x；a[j+]~a[r]的数都大于等于x，而a[j]小于等于x，
//所以执行完上面两条语句后，i<=j+,j>=i-。而第一次执行while循环时，不可能出现i>l,j<r的情况(最坏情况是i or j遇到a[i or j]=x而停止)
//然后if循环语句i=i+,j=j-，使得i<=j+<=l，j>=i->=l，不存在i>r,j<l的情况
//等号不可缺少，否则当i=j，a[i/j]=x时，程序不再有i,j变化的操作，导致死循
if (i<=j) then
begin
//a[i]与a[j]的交换：使得交换后a[i]<=x，a[j]>=x，这就是上面小于等于和大于等于的原因
y:=a[i];
a[i]:=a[j];
a[j]:=y;
//下面两条语句不可缺少，注意不要遗漏
//执行完下面两条语句后，a[l]~a[i-]的数都小于等于x，a[i]是否大于等于x还未确定，需要下一次while循环使得 那时的i满足a[i]大于等于x。
//a[j+]~a[r]的数都大于等于x，a[j]是否小于等于x还未确定，需要下一次while循环使得 那时的j满足a[j]小于等于x。
inc(i);
dec(j);
end;
until i>j;
//上述while循环执行完后，a[l]~a[i-]的值都小于等于x，a[j+]~a[r]的值都小于等于x
//所以上述while (i<=j) 必须包含等号，否则若while (i<j) ,最后i=j，不知道a[i/j]和x的大小关系
//因为每次i都只增加1，每次j只减少1，if循环的代码if (i<=j) {i++; j--;}，所以最后i=j+或i=j+
//当出现i=j+情况，只可能为：执行完两个while语句(while (a[i]<x) i++;,while (a[j]>x) j=j-;)后，i=j
//根据a[i]大于等于x，a[j]小于等于x，(此时i=j)，判断出a[i]=x
//然后 if循环的代码if (i<=j) {i=i+1; j=j-1;}，使得i=j+
//以下情况不可能出现：两个while语句执行完之前，i=j；两个while语句执行完之后，i=j+。
//因为不可能a[i]<x和a[j]>x同时成立，
//当a[i]<x，执行i++，然后a[i+]>=x（a[j+]~a[r]的数都大于等于x，此时i+=j+），结束i的增加；
//当a[j]>x，执行j--，然后a[j-]<=x（a[l]~a[i-]的数都小于等于x，此时j-=i-），结束j的减少
//当i=j+时
//i=j+，qsort_(i,r)：对a[j+]~a[r]进行排序（a[j+]~a[r]的值都小于等于x）
//j=i-，qsort_(l,j)：对a[l]~a[i-]进行排序（a[l]~a[i-]的值都小于等于x）
//qsort_(i,r),qsort_(l,j)执行完后，a[l]~a[j]排好序，且值小于等于x(当前)；a[j+]~a[r]排好序，且值小于等于x(当前)
//即a[l]~a[r]可以分成两部分，a[l]~a[j]小于等于x，a[j+]~a[r]大于等于x，且两部分已排好顺序，所以a[l]~a[r]也排好顺序
//当i=j+时
//a[i-]=a[j+]=x
//a[l]~a[r]可以分成三部分，a[l]~a[j]小于等于x,a[j+]~a[r]大于等于x，且两部分已排好顺序，两部分中间的数a[j+]=x，所以a[l]~a[r]也排好顺序
//上述就是qsort_(i,r),qsort_(l,j)，而不是qsort_(l,i)，qsort_(j,r)的原因，不要打错了
if (i<r) then qsort(i,r);
if (j>l) then qsort(j,l);
end;
begin
readln(n);
for i:= to n do
read(a[i]);
qsort(,n);
for i:= to n do
write(i,' ');
writeln;
end.
2.C
#include <stdio.h>
#include <stdlib.h>
#define maxn 100
long a[maxn+];
void qsort_(long l,long r)
{
//对a[l]~a[r]的数进行排序
long i,j,x,y;
//x为a[l]~a[r]中的一个数
i=l; j=r; x=a[(l+r)>>];
//i逐渐增加，j逐渐减少，最终i>=j，结束while循环
//保证能有限次结束循环：if (i<=j) {i=i+1; j=j-1;} 如果i<=j，i增加，j减少
//而while (a[i]<x) i++; while (a[j]>x) j=j-1; 也是i增加，j减少的操作
while (i<=j)
{
//执行完下面一条语句后，a[l]~a[i-1]的数都小于等于x(i=l另当别论)，而a[i]大于等于x。而为什么是小于等于而不是小于，后面有解释。
while (a[i]<x) i++;
//执行完下面一条语句后，a[j+1]~a[r]的数都大于等于x(j=r另当别论)，而a[j]小于等于x。而为什么是大于等于而不是大于，后面有解释。
while (a[j]>x) j--;
//*一开始i=l,j=r,i<=j，后来i增加，j减少，因为执行完上面两条语句后，a[l]~a[i-1]的数都小于等于x，而a[i]大于等于x；a[j+1]~a[r]的数都大于等于x，而a[j]小于等于x，
//所以执行完上面两条语句后，i<=j+1,j>=i-1。而第一次执行while循环时，不可能出现i>l,j<r的情况(最坏情况是i or j遇到a[i or j]=x而停止)
//然后if循环语句i=i+1,j=j-1，使得i<=j+1<=l，j>=i-1>=l，不存在i>r,j<l的情况
//等号不可缺少，否则当i=j，a[i/j]=x时，程序不再有i,j变化的操作，导致死循环
if (i<=j)
{
//a[i]与a[j]的交换：使得交换后a[i]<=x，a[j]>=x，这就是上面小于等于和大于等于的原因
y=a[i];
a[i]=a[j];
a[j]=y;
//下面两条语句不可缺少，注意不要遗漏
//执行完下面两条语句后，a[l]~a[i-1]的数都小于等于x，a[i]是否大于等于x还未确定，需要下一次while循环使得 那时的i满足a[i]大于等于x。
//a[j+1]~a[r]的数都大于等于x，a[j]是否小于等于x还未确定，需要下一次while循环使得 那时的j满足a[j]小于等于x。
i++;
j--;
}
}
//上述while循环执行完后，a[l]~a[i-1]的值都小于等于x，a[j+1]~a[r]的值都小于等于x
//所以上述while (i<=j) 必须包含等号，否则若while (i<j) ,最后i=j，不知道a[i/j]和x的大小关系
//因为每次i都只增加1，每次j只减少1，if循环的代码if (i<=j) {i++; j--;}，所以最后i=j+1或i=j+2
//当出现i=j+2情况，只可能为：执行完两个while语句(while (a[i]<x) i++;,while (a[j]>x) j=j-1;)后，i=j
//根据a[i]大于等于x，a[j]小于等于x，(此时i=j)，判断出a[i]=x
//然后 if循环的代码if (i<=j) {i=i+1; j=j-1;}，使得i=j+2
//以下情况不可能出现：两个while语句执行完之前，i=j；两个while语句执行完之后，i=j+2。
//因为不可能a[i]<x和a[j]>x同时成立，
//当a[i]<x，执行i++，然后a[i+1]>=x（a[j+1]~a[r]的数都大于等于x，此时i+1=j+1），结束i的增加；
//当a[j]>x，执行j--，然后a[j-1]<=x（a[l]~a[i-1]的数都小于等于x，此时j-1=i-1），结束j的减少
//当i=j+1时
//i=j+1，qsort_(i,r)：对a[j+1]~a[r]进行排序（a[j+1]~a[r]的值都小于等于x）
//j=i-1，qsort_(l,j)：对a[l]~a[i-1]进行排序（a[l]~a[i-1]的值都小于等于x）
//qsort_(i,r),qsort_(l,j)执行完后，a[l]~a[j]排好序，且值小于等于x(当前)；a[j+1]~a[r]排好序，且值小于等于x(当前)
//即a[l]~a[r]可以分成两部分，a[l]~a[j]小于等于x，a[j+1]~a[r]大于等于x，且两部分已排好顺序，所以a[l]~a[r]也排好顺序
//当i=j+2时
//a[i-1]=a[j+1]=x
//a[l]~a[r]可以分成三部分，a[l]~a[j]小于等于x,a[j+2]~a[r]大于等于x，且两部分已排好顺序，两部分中间的数a[j+1]=x，所以a[l]~a[r]也排好顺序
//上述就是qsort_(i,r),qsort_(l,j)，而不是qsort_(l,i)，qsort_(j,r)的原因，不要打错了
if (i<r) qsort_(i,r);
if (j>l) qsort_(l,j);
}
int main()
{
long n,i;
scanf("%ld",&n);
for (i=;i<=n;i++)
scanf("%ld",&a[i]);
//不能使用qsort名称，因为c函数库有qsort函数
//不用向qsort函数一样一般把数组初始下标设为0
qsort_(,n);
for (i=;i<=n;i++)
printf("%ld ",a[i]);
printf("\n");
return ;
}
3.C++
#include <iostream>
#define maxn 100
using namespace std;
long a[maxn+];
void qsort_(long l,long r)
{
//对a[l]~a[r]的数进行排序
long i,j,x,y;
//x为a[l]~a[r]中的一个数
i=l; j=r; x=a[(l+r)>>];
//i逐渐增加，j逐渐减少，最终i>=j，结束while循环
//保证能有限次结束循环：if (i<=j) {i=i+1; j=j-1;} 如果i<=j，i增加，j减少
//而while (a[i]<x) i++; while (a[j]>x) j=j-1; 也是i增加，j减少的操作
while (i<=j)
{
//执行完下面一条语句后，a[l]~a[i-1]的数都小于等于x(i=l另当别论)，而a[i]大于等于x。而为什么是小于等于而不是小于，后面有解释。
while (a[i]<x) i++;
//执行完下面一条语句后，a[j+1]~a[r]的数都大于等于x(j=r另当别论)，而a[j]小于等于x。而为什么是大于等于而不是大于，后面有解释。
while (a[j]>x) j--;
//*一开始i=l,j=r,i<=j，后来i增加，j减少，因为执行完上面两条语句后，a[l]~a[i-1]的数都小于等于x，而a[i]大于等于x；a[j+1]~a[r]的数都大于等于x，而a[j]小于等于x，
//所以执行完上面两条语句后，i<=j+1,j>=i-1。而第一次执行while循环时，不可能出现i>l,j<r的情况(最坏情况是i or j遇到a[i or j]=x而停止)
//然后if循环语句i=i+1,j=j-1，使得i<=j+1<=l，j>=i-1>=l，不存在i>r,j<l的情况
//等号不可缺少，否则当i=j，a[i/j]=x时，程序不再有i,j变化的操作，导致死循环
if (i<=j)
{
//a[i]与a[j]的交换：使得交换后a[i]<=x，a[j]>=x，这就是上面小于等于和大于等于的原因
y=a[i];
a[i]=a[j];
a[j]=y;
//下面两条语句不可缺少，注意不要遗漏
//执行完下面两条语句后，a[l]~a[i-1]的数都小于等于x，a[i]是否大于等于x还未确定，需要下一次while循环使得 那时的i满足a[i]大于等于x。
//a[j+1]~a[r]的数都大于等于x，a[j]是否小于等于x还未确定，需要下一次while循环使得 那时的j满足a[j]小于等于x。
i++;
j--;
}
}
//上述while循环执行完后，a[l]~a[i-1]的值都小于等于x，a[j+1]~a[r]的值都小于等于x
//所以上述while (i<=j) 必须包含等号，否则若while (i<j) ,最后i=j，不知道a[i/j]和x的大小关系
//因为每次i都只增加1，每次j只减少1，if循环的代码if (i<=j) {i++; j--;}，所以最后i=j+1或i=j+2
//当出现i=j+2情况，只可能为：执行完两个while语句(while (a[i]<x) i++;,while (a[j]>x) j=j-1;)后，i=j
//根据a[i]大于等于x，a[j]小于等于x，(此时i=j)，判断出a[i]=x
//然后 if循环的代码if (i<=j) {i=i+1; j=j-1;}，使得i=j+2
//以下情况不可能出现：两个while语句执行完之前，i=j；两个while语句执行完之后，i=j+2。
//因为不可能a[i]<x和a[j]>x同时成立，
//当a[i]<x，执行i++，然后a[i+1]>=x（a[j+1]~a[r]的数都大于等于x，此时i+1=j+1），结束i的增加；
//当a[j]>x，执行j--，然后a[j-1]<=x（a[l]~a[i-1]的数都小于等于x，此时j-1=i-1），结束j的减少
//当i=j+1时
//i=j+1，qsort_(i,r)：对a[j+1]~a[r]进行排序（a[j+1]~a[r]的值都小于等于x）
//j=i-1，qsort_(l,j)：对a[l]~a[i-1]进行排序（a[l]~a[i-1]的值都小于等于x）
//qsort_(i,r),qsort_(l,j)执行完后，a[l]~a[j]排好序，且值小于等于x(当前)；a[j+1]~a[r]排好序，且值小于等于x(当前)
//即a[l]~a[r]可以分成两部分，a[l]~a[j]小于等于x，a[j+1]~a[r]大于等于x，且两部分已排好顺序，所以a[l]~a[r]也排好顺序
//当i=j+2时
//a[i-1]=a[j+1]=x
//a[l]~a[r]可以分成三部分，a[l]~a[j]小于等于x,a[j+2]~a[r]大于等于x，且两部分已排好顺序，两部分中间的数a[j+1]=x，所以a[l]~a[r]也排好顺序
//上述就是qsort_(i,r),qsort_(l,j)，而不是qsort_(l,i)，qsort_(j,r)的原因，不要打错了
if (i<r) qsort_(i,r);
if (j>l) qsort_(l,j);
}
int main()
{
long n,i;
cin>>n;
for (i=;i<=n;i++)
cin>>a[i];
//不能使用qsort名称，因为c函数库有qsort函数
//不用向qsort函数一样一般把数组初始下标设为0
qsort_(,n);
for (i=;i<=n;i++)
cout<<a[i]<<" ";
cout<<endl;
return ;
}
另外：
qsort的另外一种写法
#include <stdio.h>
#include <stdlib.h>
#define maxn 100 long a[maxn+]; void quicksort(long l,long r)
{
long i,j,x,y;
x=a[r];
i=l-;
for (j=l;j<r;j++)
//若数小于等于x，交换到a[l]~a[r]段的左方
if (a[j]<=x)
{
i++;
y=a[i];
a[i]=a[j];
a[j]=y;
}
y=a[i+];
a[i+]=a[r];
a[r]=y;
//a[l]~a[i]为小于等于x的数
if (l<i)
quicksort(l,i);
//a[i+1]=x
//a[i+2]~a[r]为大于x的数
if (i+<r)
quicksort(i+,r);
} int main()
{
long n,i;
scanf("%ld",&n);
for (i=;i<=n;i++)
scanf("%ld",&a[i]);
quicksort(,n);
for (i=;i<=n;i++)
printf("%ld ",a[i]);
printf("\n");
return ;
}
/*
5
2 4 3 1 5
*/
qsort随机化
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define maxn 100 long a[maxn+]; void qsort_(long l,long r)
{
long i,j,x,y;
i=l; j=r; x=a[rand()%(r-l+)+l];
while (i<=j)
{
while (a[i]<x) i++;
while (a[j]>x) j--;
if (i<=j)
{
y=a[i];
a[i]=a[j];
a[j]=y;
i++;
j--;
}
}
if (i<r) qsort_(i,r);
if (j>l) qsort_(l,j);
} int main()
{
srand(time(NULL));
long n,i;
scanf("%ld",&n);
for (i=;i<=n;i++)
scanf("%ld",&a[i]);
qsort_(,n);
for (i=;i<=n;i++)
printf("%ld ",a[i]);
printf("\n");
return ;
}
/*
5
2 4 3 1 5
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define maxn 100 long a[maxn+]; void quicksort(long l,long r)
{
long i,j,x,y;
//从a[l]~a[r]随机选择一个数
i=l+rand()%(r-l+);
x=a[i];
a[i]=a[r];
a[r]=x;
//此时x=a[r]
i=l-;
for (j=l;j<r;j++)
//若数小于等于x，交换到a[l]~a[r]段的左方
if (a[j]<=x)
{
i++;
y=a[i];
a[i]=a[j];
a[j]=y;
}
y=a[i+];
a[i+]=a[r];
a[r]=y;
//a[l]~a[i]为小于等于x的数
if (l<i)
quicksort(l,i);
//a[i+1]=x
//a[i+2]~a[r]为大于x的数
if (i+<r)
quicksort(i+,r);
} int main()
{
srand(time(NULL));
long n,i;
scanf("%ld",&n);
for (i=;i<=n;i++)
scanf("%ld",&a[i]);
quicksort(,n);
for (i=;i<=n;i++)
printf("%ld ",a[i]);
printf("\n");
return ;
}
/*
5
2 4 3 1 5
*/
Topk：
#include <stdio.h>
#include <stdlib.h>
#define maxn 100 //O(n)
//设对a[l]~a[r]排一次序需要r-l+1的时间，
//则最坏时间复杂度：n+n/2+n/4+……+1=2n-1<2n
//使用这种方法的quicksort是因为这种方法能知道取的数x排序后在数组中的位置 long a[maxn+],n,k,pos=; void quicksort(long l,long r)
{
//a[l]~a[r]排序
long i,j,x,y;
x=a[r];
i=l-;
for (j=l;j<r;j++)
if (a[j]<=x)
{
i++;
y=a[i];
a[i]=a[j];
a[j]=y;
}
i++;
y=a[i];
a[i]=a[r];
a[r]=y;
//a[l]~a[i-1]为小于等于x的数
//a[i]=x
//a[i+1]~a[r]为大于x的数
if (i==k)
{
printf("%ld\n",x);
exit();
}
else if (i<k)
quicksort(i+,r);
else
quicksort(l,i-);
} int main()
{
long i;
scanf("%ld%ld",&n,&k);
for (i=;i<=n;i++)
scanf("%ld",&a[i]);
quicksort(,n);
return ;
}
/*
5 1/2/3/4/5
5 2 4 3 1
*/
库中的快速排序函数，是随机化快速排序，且加了一些较复杂的优化，时间效率较高，时间紧张时用(contest)
c:qsort c:sort(#include <algorithm>)
http://www.cnblogs.com/cmyg/p/6810800.html