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;
    }
}