排序算法之快速排序

在平均状况下，排序n个元素要O(nlogn)次比较。在最坏状况下则需要O(n^2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他O(nlogn)算法更快，因为它的内部循环可以在大部分的架构上很有效率地被实现出来。

步骤：

1.从数列中挑出一个元素，称为 “基准”（pivot），

2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。对每个分区递归地进行步骤1~3，递归的结束条件是序列的大小是0或1，这时整体已经被排好序了。

#include

usingnamespacestd;

voidQsort(inta[],intlow,inthigh)

{

if(low>high) {

return;

}

intfirst = low;

intlast = high;

intkey = a[first];//基准

while(first<last)

while(first=key) {//从最后一个元素开始向前便利，获得第一个小于基准的元素。

last--;

}

a[first]=a[last];//将比第一个小的放到数组低下标处

while(first

first++;

}

a[last]=a[first];//将比第一个大的放在数组高处

}

a[first] = key;

Qsort(a, low, first-1);//递归

Qsort(a, first+1, high);

}

intmain(){

inta[]={23,45,72,54,34,23,13,12,56,89,12};

Qsort(a,0,sizeof(a)/sizeof(a[0])-1);

for(inti =0; i<sizeof(a)/sizeof(a[0]);i++)

cout<<a[i]<<" ";

}

return0;

}