快速排序算法

题目

给定一个长度为 n的整数数列。请使用快速排序对这个数列按照从小到大进行排序。并将排好序的数列按顺序输出。

输入格式
输入共两行，第一行包含整数 n。
第二行包含 n个整数（所有整数均在 1∼109范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
1≤n≤100000
样例
输入
5
2 1 3 5 4
输出
1 2 3 4 5

快速排序介绍

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。快速排序是一种高效的排序算法，通过选取一个“基准”元素，将数组分为两部分：比基准小的元素和比基准大的元素，然后递归地对这两部分进行排序，从而实现对整个数组的排序。该算法平均时间复杂度为O(nlogn)，最坏情况下为O(n²)，但由于实际应用中很少出现最坏情况，因此快速排序仍然是一种广泛使用的排序算法。它采用了一种分治的策略，通常称其为分治法。

基本思想

1. 先从数组中取出一个数作为基准数，通常取第一个、最后一个或者中间数。
2. 将比这个数大的数全部放到它的左边，将小于等于它的数全部放到它的左边。
3. 对左右区间重复第二步，直到各个区间只有一个数。

详细说明：
在快速排序的具体实现中，通常选择数组中的一个元素作为基准元素，然后将数组中的其他元素与基准元素进行比较，根据比较结果将元素放到两个子数组中。这个过程可以通过使用==双指针技术==来实现，一个指针从数组的开头开始向右移动，另一个指针从数组的末尾开始向左移动，当左指针指向的元素小于等于基准元素，且右指针指向的元素大于等于基准元素时，交换这两个元素的位置。当左指针移动到右指针的位置时，整个数组就被划分为了两个子数组。

接下来，对这两个子数组分别进行快速排序。==递归==地调用快速排序函数，传入子数组的首尾指针作为参数，直到整个数组都被排序完毕。

过程模拟

初始状态：i = 0，j = 4，取中间元素为基准元素x = 2
3 1 2 5 4

然后i与j的对应元素与基准元素比较，i为下标对应的元素如果小于x时i++，当i对应的元素不小于x时停下来，然后将j为下标对应的元素与x比较，如果j为下标对应的元素如果大于x时j–，当j对应的元素不大于x时停下来。如果i<j则交换a[i]与a[j]的值，这能够使x左边的数字都是小于等于x的，x右边的数都是大于等于x的是数。
此时i为0，j为3，a[0]与a[3]交换。即第一次划分的结果为划分结果: [2, 1] [ 3 ,5, 4]
2 1 3 5 4

然后我们处理左部分的数组[2,1]，取基准值x = 2，i = 0,j = 1,交换a[i]与a[j]，划分结果为[1] | 2
同理，处理右部分的数组[3,5,4]，i = 2 , j = 4,基准值x = 5,划分结果为[3,4] | 5
最终结果为[1,2,3,4,5]
C++实现代码如下：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5+10;
int n;
int a[N];

void quick_sort(int a[],int l,int r){
    //数组中只有一个元素时，无需排序直接返回
    if(l >= r)  return;
    //取中间元素为基准元素用作比较
    int x = a[l+r>>1];
    //边界分别往前和往后取一位，方便处理
    int i = l-1, j = r+1;
    //第一遍划分先将数组分为两个部分
    while(i<j)
    {
        do i++; while(a[i] < x);
        do j--; while(a[j] > x);
        if(i < j)
        swap(a[i],a[j]);
    }
    //对左部分递归排序
    quick_sort(a,l,j);
    //对右部分递归排序
    quick_sort(a,j+1,r);
}

int main()
{
    scanf("%d",&n);

    for(int i = 0;i < n ;++ i)
    scanf("%d",&a[i]);

    quick_sort(a,0,n-1);

    for(int i = 0;i <n ;++ i)
    printf("%d ",a[i]);

    return 0;
}

如果上面的方法不清楚也可以将快速排序看作挖坑法，简单来说就是

1．i =l; j = r; 将基准数挖出形成第一个坑a[i]。
2．j–由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。

C++实现代码如下：

//快速排序
void quick_sort(int s[], int l, int r)
{
    if (l < r)
    {
        //基准元素取第一个数s[l],s[l]即s[i]就是第一个坑
        int i = l, j = r, x = s[l];
        while (i < j)
        {
             // 从右向左找第一个小于x的数来填s[i]
            while(i < j && s[j] >= x) 
                j--;  
            ////将s[j]填到s[i]中，s[j]就形成了一个新的坑
            if(i < j) 
                s[i++] = s[j];
            // 从左向右找第一个大于等于x的数来填s[j]
            while(i < j && s[i] < x) 
                i++;  
             //将s[i]填到s[j]中，s[i]又形成了一个新的坑
            if(i < j) 
                s[j--] = s[i];
        }
        //退出时，i等于j。将x填到这个坑中
        s[i] = x;
        quick_sort(s, l, i - 1); // 递归调用 
        quick_sort(s, i + 1, r);
    }
}

以上为我对于快速排序算法的理解，如果有问题欢迎大家批评指正，也欢迎大家一起交流。
https://blog.csdn.net/qq_75092124/article/details/147311959?spm=1011.2415.3001.5331