快速排序是一个非常经典也非常常用的排序算法。在平均状况下,排序 n 个项目需要 Ο(nlogn) 次比较,在最坏状况下则需要 Ο(n2) 次比较,但这种状况其实并不常见。快速排序是分而治之思想在排序算法上的典型应用。
算法步骤:
1.从数列中挑出一个元素,称为 "基准"。
2。设置两个"哨兵",利用"哨兵"将所有比基准值小的元素摆放在基准值前面,所有比基准值大元素的摆在基准值的后面(相同的数可以到任一边)。当两个"哨兵"相遇时,"基准"就找到了正确的位置,同时基准就将数列的左右两边分成了两个区域。
3.递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
c++代码实现:
点击查看代码
void quicksort(int left,int right)//左右哨兵
{
int i,j,t,temp;
if(left>right)
return;//这里是对于第一个基准数归位后出现的分区的情况的处理
temp=a[left]//temp存的就是基准数,
i=left,j=right;
while(i!=j)
{
//顺序很重要,
while(a[j]>=temp and i<j)
j--;
while(a[i]<=temp and i<j)
i++;
//交换两个数的位置
if(i<j)//哨兵未相遇
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
//最终归位基准数
a[left]=a[i];
a[i]=temp;
quicksort(left,i-1);//继续处理左边的,这是一个递归的过程
quicksort(i+1,right);//继续处理右边的,这是一个递归的过程
}
}