快速排序及其优化【图文详解】

快速排序及其优化【图文详解】

引用

CSDN

1.

https://m.blog.csdn.net/m0_75266675/article/details/144146127

快速排序是一种高效的排序算法，其基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

经典快速排序

一次划分

什么是快速排序的一次划分？一次划分就是，找到一个基准x，经过调整，也就是一次划分过后，可以把数组分为两个部分，一个都是大于x的，一个都是小于x的部分。比如给你一个数组，以6为基准的话,经过一次划分后，变成如下图：左边部分是都是小于6的，右边部分都是大于6的，这就是一次划分的作用。

快速排序的一次划分过程可以概括为以下步骤：

1. 选择一个基准元素（通常是第一个元素）
2. 从后往前找比基准小的数据往前移动
3. 从前往后找比基准大的数据往后移动
4. 重复1)和2)直到找到基准位置

这个过程也叫partition过程，时间复杂度是O(n)。

以下是快速排序的C++代码实现：

int Partion(int* arr, int low, int high)//O(n)
{       
    while (low < high)
    {
        //从后往前找小的，大的往后挪动
        while (low<high && arr[high]>tmp)
        {
            high--;
        }//找到了
        if (low < high)
            arr[low] = arr[high];//把小的数值往前挪
        //从前往后找小的，小的往前挪动
        while (low < high && arr[low] < tmp)
        {
            low++;
        }//找到了
        if (low < high)//把大的数值往后挪动
            arr[high] = arr[low];
    }
    arr[low] = tmp;
    return low;
}
void Quick(int* arr, int low, int high)
{
    if(low>=high)return ;
    int par = Partion(arr, low, high);//par是下标，是经过一次划分过后的下标
    Quick(arr, low, par - 1);
    Quick(arr, par + 1, high);
}
//递归地调用快速排序
void QuickSort(int* arr, int len)//对外表现都是两个参数，自己内部需要三个参数，自己内部解决
{
    Quick(arr, 0, len - 1);//把下标传进去
}
int main()
{
    int arr[] = { 12,3,4,5 };
    QuickSort(arr, sizeof(arr) / sizeof(arr[0]));
    for (int i = 0;i < sizeof(arr) / sizeof(arr[0]);i++)
        printf("%d ", arr[i]);
    return 0;
}

快速排序的优化

快速排序虽然效率很高，但在某些情况下可能会退化成O(n^2)的时间复杂度。为了提高算法的稳定性，可以进行以下优化：

1. 在选择基准的时候，随机选择数字，而不是挨个选

   int x = nums[l + rand() % (r - l + 1)];
   

2. 一次划分的过程，如果有大量的重复元素存在，那么经典的快速排序就会降低速度，我们可以每次把同一个数字全都整理好，比如数字1，每次全都处理了，左边的数字全都是小于1的，中间的数字全都是大于1的，右边的数字全都是大于1的。也叫荷兰国旗划分！

接下来举个例子，代码是如何操作的！

比如有一个数组是
2,1,3,4,2,0
，以2为基准

最后目标是变成这个样子

定义三个变量，i，L，R分别表示遍历的下标，左边界，和右边界，i一个一个遍历，如果当前数字小于基准，那么往左边界发货，如果等于基准，i++，如果大于基准，那么往右边发货。具体来说；

1. 如果
   nums[i]==x
   那么
   i++
2. 如果
   nums[i]<x
   ，那么交换
   nums[i]
   ,
   nums[L]
   ,
   i++
   ，
   L++
3. 如果
   nums[i]>x
   ,那么交换
   nums[i],nums[R]
   ,
   R--

图解：i开始遍历

最后一次划分就就得到了2的左边界都是小于2的，2的右边界都是大于2的。把2这个数字全都处理好了

以下是优化后的快速排序C++代码实现：

class Solution {
public:
    static int first;
    static int last;
public:
    //三路划分，一次性把x划分好
    void partition(vector<int>&nums,int l,int r,int x){
        first=l;
        last=r;
        int i=l;
        while(i<=last){
            if(nums[i]==x){
                i++;
            }else if(nums[i]<x){
                swap(nums[first++],nums[i++]);
            }else{
                swap(nums[i],nums[last--]);
            }
        }
    }
    void Qsort(vector<int>&nums,int l,int r)
    {
        if(l>=r){
            return ;
        }
        //随机
        int x = nums[l + rand() % (r - l + 1)];
        partition(nums,l,r,x);
        int left=first;
        int right=last;
        Qsort(nums,l,left-1);
        Qsort(nums,right+1,r);
    }
    int sort+(vector<int>& nums, int k) {
        Qsort(nums,0,nums.size()-1);
    }
};

通过以上优化，快速排序在处理大量重复元素时的性能将得到显著提升。