基础算法--快速排序法（附yxc快排模板）

解题思路:

                快速排序法是使用分治法的策略把一个串行分成两个子串行（即把数组以一个数为基准分为小于基准值的数列和大于基准值的数列）。快速排序法应该算是在冒泡排序法基础上的递归分治法。分为以下三个步骤：

                1、取基准点

                    确定一个基准点，可以随机取。但是取数组中间的元素作为基准点，可以更快。

                2、划分区间

                    把小于基准点的数无序放在基准点左边，大于基准点的数无序放在基准点右边。（代码实现原理：使用两个指针i和j，从数组左右两边开始走，如果不满足条件就互换）

                3、递归排序

                    递归排序左右两边的数列，使之整个数组排好序。

注意事项:
                一定要理解快速排序法的逻辑是什么，不然还是不懂。

                1、基准点尽量去数组中间的元素，可以减少时间。

                2、划分区间时，指针i不能是数组首元素下标，j不能说数组尾元素下标。因为do while循环，是先把i和j指针往前推一位再进行判断。要不然会把首尾元素没有排序。

                3、递归排序左右两边时，要注意传入的参数

                觉得写的不错的，麻烦各位点个评分或者评论，支持一下阿辉。谢谢
参考代码:

#include <stdio.h>
void quick_sort(int nums[],int l,int r)
{
    if(l >= r)//如果数组只有1个元素或者没有元素，直接退出函数
        return;
    int i = l - 1,j = r + 1,x = nums[(l + r ) / 2];//i和j是指针，为了下面的do while循环，使用把它们往前后者往后推了一位，x为基准点
    while(i < j)//开始划分区间，当i和j没有相遇时，继续走
    {
        do i++;while(nums[i] < x);
        do j--;while(nums[j] > x);
        if(i < j)//如果i和j跳出do while循环，说明nums[i]比x大，nums[j]比x小，这两个数需要进行互换
        {
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
    }
    quick_sort(nums,l,j);//递归排序左边
    quick_sort(nums,j + 1,r);//递归排序右边
}
int main()
{
    int n,nums[100000];
    scanf("%d",&n);
    for(int i = 0;i < n;i++)
    {
        scanf("%d",&nums[i]);
    }
    quick_sort(nums,0,n - 1);//快速排序法
    for(int i = 0;i < n;i++)
    {
        printf("%d ",nums[i]);
    }
    return 0;
}

附yxc大佬的快排模板

void quick_sort(int nums[],int l,int r)
{
    if(l >= r)
        return;
    int i = l - 1,j = r + 1,x = nums[(l + r) / 2];
    while(i < j)
    {
        do i++;while(nums[i] < x);
        do j--;while(nums[j] > x);
        if(i < j)
        {
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
    }
    quick_sort(nums,l,j);
    quick_sort(nums,j + 1,r);
}