他的思想是找到一个值,小的放在他的左面,大的放在他的右面。
这样左右两边都只需要在自己的范围内比较了
一般用递归来实现
快速排序和其他基于比较的排序方法来说 比较次数少
下面是没有优化的快排代码
void QuickSort(int arr[],int nLow,int nHigh)
{
if(arr == NULL || nLow >= nHigh)return;
//标准值,标准值左侧都小于它,右侧都大于它
int nStandard;
nStandard = Sort(arr,nLow,nHigh);
//递归,排序标准值的左面和右面
QuickSort(arr,nLow,nStandard-1);
QuickSort(arr,nStandard+1,nHigh);
}
其中Sort的代码如下:
利用的是挖坑填补法,把数组第一个参数的位置当做标准值
int Sort(int arr[],int nLow,int nHigh)
{
int temp;
temp = arr[nLow];
while(nLow < nHigh)
{
//从后向前找比标准值小的
while(nLow < nHigh)
{
if(arr[nHigh] < temp)
{
//放前面
arr[nLow] = arr[nHigh];
nLow++;
break;
}
nHigh--;
}
//从前向后找比标准值大的
while(nLow < nHigh)
{
if(arr[nLow] > temp)
{
//放后面
arr[nHigh] = arr[nLow];
nHigh--;
break;
}
nLow++;
}
}
//标准值放入
arr[nLow] = temp;
return nLow;
}
优化1
上面这种写法是两个while的嵌套,效率非常低
所以我们想到下面这种写法,一层循环就可以了,用区间分割法
int Sort(int arr[],int nLow,int nHigh) { //小于标准值的数组下标 int nSmall; nSmall = nLow-1; //把数组最后一个元素当做标准值 for(nLow;nLow<nHigh;nLow++) { //如果数组当前元素比标准值小,小于标准值的数组下标++ if(arr[nLow] < arr[nHigh]) { //如果数组当前元素前面有≥标准值的,将≥标准值的那个与当前元素交换 if(++nSmall != nLow) { arr[nLow] = arr[nSmall]^arr[nLow]; arr[nSmall] = arr[nSmall]^arr[nLow]; arr[nLow] = arr[nSmall]^arr[nLow]; } } } //标准值放入 if(++nSmall != nHigh) { arr[nSmall] = arr[nSmall]^arr[nHigh]; arr[nHigh] = arr[nSmall]^arr[nHigh]; arr[nSmall] = arr[nSmall]^arr[nHigh]; } return nSmall; }
这种写法有几个比标准值小的small就++几次,最后small等于最后一个比标准值小的数组下标
将small后一个的元素与标准值交换 这样就能做到标准值左面都比它大,右边都比它小
优化2
快速排序如果你找到的标准值是整个数组的最大值或者最小值,那么它就没办法将数组分成两部分
或者说你取得值很大或很小都不利于我们快排
所以我们可以在数组中取第一个,中间一个,最后一个,找到他们三个之中的中位数
进而减小遇到这种情况的概率
代码实现上可以找到之后将中位数与最后一个数进行交换,重复优化1的步骤
优化3
频繁的调用递归会降低系统的效率 我们可以借助辅助栈和循环来代替递归
代码在下面
void QuickSort(int arr[],int nLow,int nHigh)
{
if(arr == NULL || nLow >= nHigh)return;
Stack* st = NULL;
s_Init(&st);
//栈里装的是数组的高低下标
s_Push(st,nLow,nHigh);
int low,high;
//因为low和high在变化,用a,b记录他们
int a,b;
//小于标准值的数组下标
int nSmall;
while(st->nCount != 0)
{
s_Pop(st,&low,&high);
a = low;
b = high;
nSmall = low-1;
//把数组最后一个元素当做标准值
for(low;low<high;low++)
{
//如果数组当前元素比标准值小,小于标准值的数组下标++
if(arr[low] < arr[high])
{
//如果数组当前元素前面有≥标准值的,将≥标准值的那个与当前元素交换
if(++nSmall != low)
{
arr[low] = arr[nSmall]^arr[low];
arr[nSmall] = arr[nSmall]^arr[low];
arr[low] = arr[nSmall]^arr[low];
}
}
}
//标准值放入
if(++nSmall != high)
{
arr[nSmall] = arr[nSmall]^arr[high];
arr[high] = arr[nSmall]^arr[high];
arr[nSmall] = arr[nSmall]^arr[high];
}
//判断是否入栈
if(nSmall-1 >= a)
s_Push(st,a,nSmall-1);
if(b >= nSmall+1)
s_Push(st,nSmall+1,b);
}
}
优化4
快速排序中如果元素个数很小(小于等于3),可以将快速排序改为插入排序
插入排序前面有介绍,就不写代码了