快速排序（数据结构）

港控/mmm° 2024-04-23 20:13 32阅读 0赞

![在这里插入图片描述][be8e71dd33114183b3f1c8f8ec10075f.png]  
快速排序属于交换排序的一种。

--------------------

#### 快速排序 ####

**算法思想：**  
![在这里插入图片描述][0ca7d6561f2c472cb612a8eab5bddd63.png]

![在这里插入图片描述][f2f14e75657b4152aae017ad91ff43aa.png]

--------------------

#### 复杂度 ####

![在这里插入图片描述][7b37285e5d2f41d99210a6bfd0388697.png]

![在这里插入图片描述][87a0bcb18fc34bf1ad4154ad1311189f.png]

--------------------

**递归调用层数：**  
![在这里插入图片描述][ab36f000b69348749e2f6c0d42a22166.png]

--------------------

![在这里插入图片描述][225c7498b7b94f6c89d563634aff79b4.png]

*  最好时间复杂度：每次选的枢轴元素都能将序列分成均匀的两部分。
 *  最坏时间复杂度：序列原本就是有序或者逆序的，此时 *时间、空间复杂度最高* (可以进行优化，尽量选择可以把数据均匀分成两部分的枢纽元素)。

> 快速排序是所有内部排序算法中平均性能最优的排序算法。

--------------------

#### 最坏情况与较好情况 ####

###### 最坏情况 ######

![在这里插入图片描述][413f2c9598394c06a5365b5993d1783f.png]

--------------------

###### 比较好的情况 ######

![在这里插入图片描述][30e019edc2ca4da68aa8d9f33c25d4c9.png]

--------------------

#### 代码实现 ####

/**
     * 快速排序
     * @file QuickSort.cpp
     * @author xg
     * @date 2022-11-02
     * 
     */
    #include <iostream>
    #include <stdio.h>
    
    using namespace std;
    
    
    // 利用基准值划分区间
    int partition(int A[], int low, int high) {
        
        // 1.用数组中第一个元素作为基准值
        int pivot = A[low];
        // 2.从表的两端交替的向中间扫描
        while(low < high) {
        
            while(low < high && A[high] >= pivot) {
        
                high--;
            }
            A[low] = A[high];// 将比基准值小的元素移动到左区间
            
            while(low < high && A[low] <= pivot) {
        
                low++;
            }
            A[high] = A[low];// 将比基准大的元素移动到右区间
        }
        // 最终low=high指向空位置
        A[low] = pivot; // 将基准值存放到最终位置;
        return low;
    }
    
    void quickSort(int A[], int low, int high) {
        
        if(low < high) {
        
            // 将待排序数组一分为二，算出枢轴值
            int pivotPosition = partition(A, low, high);
            quickSort(A, low, pivotPosition-1);// 左区间
            quickSort(A, pivotPosition+1, high);// 右区间
        }
    }
    
    void PrintArray(int A[], int n) {
        
        for(int i = 0;i < n;i++) {
        
            cout << A[i] << " ";
        }
        cout << endl;
    }
    
    int main() {
        
        int arr[] = {
        100,6,5,3,2,1,99};
        cout << "排序前：";
        PrintArray(arr, 7);
        quickSort(arr,0,6);
        cout << "排序后：";
        PrintArray(arr, 7);
        return 0;
    }

> 注：以上图片来自B站王道数据结构截图

[be8e71dd33114183b3f1c8f8ec10075f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/d348fbc925f64da094efcb4cff1b978e.png
[0ca7d6561f2c472cb612a8eab5bddd63.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/74f9bae1526249c7b916dbe0df9aa766.png
[f2f14e75657b4152aae017ad91ff43aa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/5d21a48f3fa247738b4bf834d8ae2291.png
[7b37285e5d2f41d99210a6bfd0388697.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/2b7e70c6eb72415bb8a6d9fd9de2f574.png
[87a0bcb18fc34bf1ad4154ad1311189f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/ff5e8d6952904b90ac65301eebe230ea.png
[ab36f000b69348749e2f6c0d42a22166.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/85ff2ea934434d34b086899b71cef1e7.png
[225c7498b7b94f6c89d563634aff79b4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/058213eff0ba416f9bf90658f4933e83.png
[413f2c9598394c06a5365b5993d1783f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/19d84c68dc924ba38d1254596c25c5f2.png
[30e019edc2ca4da68aa8d9f33c25d4c9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/fbbe710518414a3ea9e40877a1cf5259.png