C/C++ 快速排序算法思想与实现
简述
快速排序采用分治思想,是根据冒泡排序改进而成的,主要改进后的效果是快速排序能通过一次交换,消除多个逆序序列,大大加快排序速度。
具体实现思路可以看我前几年发的这个视频:
【简单算法】快速排序思想01——为什么一定从右向左开始_哔哩哔哩_bilibili
[算法]快速排序思想02——代码实现篇_哔哩哔哩_bilibili
思想
快排主要思想是采用分治法,让轴点左侧的数都小于轴点右侧的数,可以理解为分块有序,然后对每个块再进行分治,直到排序成功。
步骤
首先我们需要设置一个轴点,一般以第一个或最后一个元素作为轴点。这里使用第一个元素。
一开始把控制权交给high指针,发现右侧有小于轴点的。 把这个数覆盖到low位置,放心一开始k存了low,覆盖完之后high位置无效了。接下来开始移动low指针,如果发现大于轴点的,那就把值覆盖到high位置,low位置又无效了。 在把控制权交给high指针。这样一来,最终无效的那个位置用来存放一开始的k。
一直这样循环,最后i==j时候退出循环,把k放到i位置上。每次再把轴点k左右两侧的分区再分别进行快速排序,直到每个表只有一个记录为止,排序完成。
实现
oid QuickSorted(int *array,int low,int high)
{
if (low>=high)
{
return;
}
int i=low,j=high,k=array[i];
while (i<j)
{
while (i<j&&array[j]>=k)
{
j--;
}
array[i]=array[j];
while (i<j&&array[i]<=k)
{
i++;
}
array[j]=array[i];
}
array[i]=k;
QuickSorted(array,low,i-1);
QuickSorted(array,i+1,high);
}
void Output(int *array,int length)
{
for (size_t i = 0; i < length; i++)
{
cout<<array[i]<<ends;
}
}
作者:Miracle
来源:麦瑞克博客
链接:https://www.playcreator.cn/archives/programming-life/cpp/3551/
本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0许可协议,转载请注明!
来源:麦瑞克博客
链接:https://www.playcreator.cn/archives/programming-life/cpp/3551/
本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0许可协议,转载请注明!
THE END
0
打赏
海报
C/C++ 快速排序算法思想与实现
简述
快速排序采用分治思想,是根据冒泡排序改进而成的,主要改进后的效果是快速排序能通过一次交换,消除多个逆序序列,大大加快排序速度。
具体实现思路可以……
文章目录
关闭