设计思想:
找到一个基准(第一个数据),1)从后往前找比基准小的数据往前移动,2)从前往后找比基准大的数据往后移动 3).重复1)和2)直到找到基准位置 这个就是快速排序的 一次划分
之后多次调用一次划分,直到完全有序;
详细过程(一次划分):
首先,我们需要传进来待排序的数组,即数组的初始位置和结束位置(low和high)(这里不懂可以结合着下面的例子看一下,就会更容易理解了),还需要定义一个基准tmp,并初始化成待排序的第一个值,
然后从后往前去找比基准小的数移动到基准的位置,也就是第一个值,此时找到的这个数的位置就是新的尾巴(也就是说这个值后面的我们此次一次划分就不管了,
然后再从前往后的去找比基准大的数移动到尾巴那里去,那里刚好空出来,这时找到的这个数所在的位置就是新的头(新的空位)
最后,我们再把基准移动到这个空位上。
重复上述步骤
例:99 ,100, 88 ,80 ,100, 90, 77, 22, 33, 90
第一遍:
基准tmp=99,从后往前找比基准小的90,此时high=9,然后将90移到low位置,
然后从前往后找比基准大的100,此时的low=1,然后将100移动到high位置,
最后再将基准放在low位置
结果:90,99,88,80,100,90,77,22,33,100
第二遍:
基准不变,low=1,high=9
从后往前找找到33,此时high=8,然后将33移到low位置
从前往后找找到100,此时low=4,然后将100移到high位置
最后再将基准放在low位置
结果:90,33,88,80,99,90,77,22,100,100
第三遍:
基准不变,low=4,high=8
从后往前找找到22,此时high=7,然后将22移到low位置
从前往后找,一直找到low=high时,发现没有比基准大的了,此时low=high=7,跳出循环
最后将基准放在low位置
结果:90,33,88,80,22,90,77,99,100,100
至此,第一次一次划分结束,我们发现,基准前面的都是比基准小的数,基准后面的都是比基准大的数,所以每次一次划分基准都会变成有序的(即基准的位置与完全有序的位置相同)
因为,我们每次一次划分最后基准落在的位置可能在数组中间也可能在数组两边,如果在中间呢,就需要对基准前面的再排序,基准后面的再排序,所以我们需要在一次划分外面加个包装,一次划分还要返回基准最后落到的位置,给一次划分传要进行一次划分的开头low和结尾high。所以,我们一次划分还需要再将最后基准落在的位置(即跳出循环时的low或high)返回一下
代码实现:
int Partition(int* arr, int low, int high)//一次划分
{
int tmp = arr[low];//基准
while (low < high)
{
//从后往前找
while (low < high && arr[high] > tmp)
{
high--;
}
if (low < high)
{
arr[low] = arr[high];
}
//从前往后找
while (low < high && arr[low] <= tmp)
{
low++;
}
if (low < high)
{
arr[high] = arr[low];
}
}
arr[low] = tmp;
return low;
}
//快速排序
void Quick(int* arr, int low,int high)
{
int par=Partition(arr, low, high);
if (low < par - 1)//左边的数据超过一个
{
Quick(arr, low, par - 1);
}
if (par + 1 < high)//右边的数据超过一个
{
Quick(arr, par + 1, high);
}
}
void QuickSort(int* arr, int len)
{
Quick(arr, 0, len - 1);
}
算法的效率分析:
O(nlogn),O(logn),不稳定
算法特性:
快速排序的缺点:不稳定,空间复杂度大
快速排序最大的缺点:越有序越慢;完全有序时间复杂度为O(n^2)完全有序退化成选择排序;