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.unitymake.com/archives/programming-life/cpp/3551
本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0许可协议,转载请注明!
THE END
分享
打赏
海报
C/C++ 快速排序算法思想与实现
简述 快速排序采用分治思想,是根据冒泡排序改进而成的,主要改进后的效果是快速排序能通过一次交换,消除多个逆序序列,大大加快排序速度。 具体实现思路可以……
<<上一篇
下一篇>>
文章目录
关闭
目 录