这是挖坑填补法的演示
快排之挖坑填补法：
void Quick(int top/*起始位置*/,int end/*末尾位置*/,int arr[])//挖坑填补法
{
int i=top,j=end,mark;//i是记住前面的坑 j记住后面的坑 mark记住标准值 mark=arr[top];//以起始位置作为标准值，同时起始点成为第一个坑
if(top>=end)return;
while(i<j)
{
while(i<j)//从后向前找比标准值小的值并且把这个值赋予坑，此点成为新的坑
{
if(arr[j]<mark)
{
arr[i]=arr[j]; i++;//前面的坑向后移动一位开始找
break;
}
j--;
}
while(i<j)//从前向后找比标准值大的值并且把这个值赋予坑此点成为新的坑 {
if(arr[i]>mark)
{
arr[j]=arr[i];
j--;//后面的坑向前移动一位开始找 break;
}
i++;
} }
arr[j]=mark;//此时的下标就是标记值的最终位置，他的前面都比他小后面都比他大
Quick(top,i-,arr);//递归
Quick(j+,end,arr);
}
快排之区间分割法：
int sch_sect(int arr[],int j,int top)//区间分割法
{
int s=j+;
while(j>)
{
if(arr[j]>arr[top])//arr[top]就是标准值
{
if(j!=--s)//判断是否指向一个位置,（因为指向一个位置异或符号会使结果为0）
{
arr[j]=arr[j]^arr[s];
arr[s]=arr[s]^arr[j];
arr[j]=arr[s]^arr[j];
} }
j--;
}
s--;
arr[top]=arr[s];//现将最终点的值赋予标准点，函数结束后将标准点的值赋予最终点
return s;
}
void Quick(int top/*起始位置*/,int end/*末尾位置*/,int arr[])
{
int i=top,j=end,mark;//i是记住前面的坑 j记住后面的坑 mark记住坑的值 mark=arr[top];//以起始位置作为坑
if(top>=end)return;
i=sch_sect(arr,end,top);
j=i;
arr[j]=mark;//此时的下标就是标记值的最终位置，他的前面都比他小后面都比他大
Quick(top,i-,arr);//递归
Quick(j+,end,arr);
}
快排是比较最少的一种排序方法
如果数组数量过少的时候直接使用插入排序而不选择快排
排序名称 最好时间复杂 平均时间复杂度度 最坏时间复杂度 空间复杂度 是否稳定
Quick O(n*log2n) O(n*log2n) O(n^2) log2n 不稳定