题解 | 【模板】排序(C语言)(快速排序法)

#include <stdio.h>

void quick_sort(int arr[],int left,int right)
{
    //递归结束条件
    if(left >= right)
        return;
    //枢轴，不同的取法有不同的效果，这里图方便取最左边的值
    int pivot = arr[left];
    int leftIndex = left;//左索引
    int rightIndex = right;//右索引

    //索引“左右横跳”与枢轴比大小
    while(leftIndex < rightIndex)
    {
        //因为把最左边的值给了枢轴
        //所以先从右往左找比枢轴大的值，大或等就索引往左，小就停
        while(leftIndex < rightIndex && arr[rightIndex] >= pivot)
            rightIndex--;//大或等就索引往左

        //最终右索引找到了比枢轴小的数
        if(leftIndex < rightIndex)
            arr[leftIndex] = arr[rightIndex];//小的放左边

        //现在右索引为“空”，开始从左往右找比枢轴小的数，小或等就索引往右，大就停
        while(leftIndex < rightIndex && arr[leftIndex] <= pivot)
            leftIndex++;//小或等就索引往右

        //最终左索引找到了比枢轴大的数
        if(leftIndex < rightIndex)
            arr[rightIndex] = arr[leftIndex];
    }
    //现在左右索引处于相同位置
    //把枢轴放进最后留出来的空里
    arr[leftIndex] = pivot;

    //以枢轴为分界点，左右两边分别开始新的排序
    quick_sort(arr,left,leftIndex-1);//新右索引是旧左索引减一
    quick_sort(arr,rightIndex+1,right);//新左索引是旧右索引加一
}
int main() {
    //数组长度
    int n;
    scanf("%d",&n);
    //给数组赋值
    int arr[n];
    int i;
    for(i=0;i<n;i++)
    {
        scanf("%d",&arr[i]);
    }
    //排序
    quick_sort(arr,0,n-1);//右边两个传的是数组索引
    //排序结束后输出
    for(i=0;i<n;i++)
    {
        printf("%d",arr[i]);
        if(i != n-1)
            printf(" ");
    }
    return 0;
}