排序算法（五）——快速排序

排序算法（五）

• 简介
• 1. 基本快速排序
• 2. 快速排序优化
• 总结

---

简介

排序算法总共可分为四类：

序号	排序名称	基础算法	优化算法
1	插入排序	直接插入排序	希尔排序
2	选择排序	简单选择排序	堆排序
3	交换排序	冒泡排序	快速排序
4	归并排序	归并排序	归并排序

快速排序其实是对冒泡排序的优化。

---

提示：下附代码，亲测可用

1. 基本快速排序

快速排序基于递归。

基本步骤主要包括：

1. 选定基准点，将小于基准点的数据放于左边，大于基准点的数据放于右边。
   

   
   

2. 分别对基准点左边和右边的数据递归进行快速排序。
   

   
   

代码如下：

#include 
using namespace std;
#define MAXSIZE 13
void swap(int k[], int low, int high)
{
    int tmp = k[low];
    k[low] = k[high];
    k[high] = tmp;
}
int Partition(int k[], int low, int high)
{
    int point;
    point = k[low];
    while (low < high)
    {
        while (low < high and k[high] >= point)
        {
            high--;
        }
        swap(k, low, high);
        for (int i = 0; i < 13; i++)
            cout << k[i] << " ";
        cout << endl;
        while (low < high and k[low] <= point)
        {
            low++;
        }
        swap(k, low, high);
    }
}
void QSort(int k[], int low, int high)
{
    int point;
    if (low < high)
    {
        point = Partition(k, low, high);
        QSort(k, low, point-1);
        QSort(k, point+1, high);
    }
}
void QuickSort(int k[], int n)
{
    QSort(k, 0, n-1);
    for (int i = 0; i < n; i++)
        cout << k[i] << " ";
    cout << endl;
}
int main()
{
    int k[] = {2, 1, 5, 7, 5, 6, 10, 20, 15, 17, 16, 14, 13};
    QuickSort(k, 13);
    return 0;
}

运行结果如下：

1 2 5 5 6 7 10 13 14 15 16 17 20 

2. 快速排序优化

对于快速排序的优化主要有以下四个方面：

1. 基准点优化。
   

   
   

   当前基准点为数据的第一个元素，如果基准点刚好为数据的中值就好了，但这比较难办。
   

   
   

   因此选定数据第一个、最后一个、中间索引这3个值的中值为基准点。
   

   
   

2. 减少不必要的交换。
   

   
   

3. 优化小数组时的排序方案。
   

   
   

   经测试，数据元素大于7时，快速排序才能体现其效率，因此优化方案为，少于等于7个数据元素时采用插入排序，大于7个数据采用快速排序。
   

   
   

4. 优化递归 *** 作。
   

   
   

   编译器会对尾递归的情况进行优化，减少栈所占用的空间，因此尽可能采用尾递归。
   

   
   

代码如下：

#include 
using namespace std;
void swap(int k[], int low, int high)
{
    int tmp = k[low];
    k[low] = k[high];
    k[high] = tmp;
}
int Partition(int k[], int low, int high)
{
    int point;
    // 1. 优化基准点
    if (k[low] > k[high])
        swap(k, low, high);
    int m = (high+low)/2;
    if (k[m] > k[high])
        swap(k, m, high);
    if (k[m] > k[low])
        swap(k, low, m);
    point = k[low];
    while (low < high)
    {
        while (low < high and k[high] >= point)
        {
            high--;
        }
        // 2. 减少不必要的交换，将交换改为直接赋值。


        // swap(k, low, high);
        k[low] = k[high];
        while (low < high and k[low] <= point)
        {
            low++;
        }
        // swap(k, low, high);
        k[high] = k[low];
    }
    k[low] = point;
    return low; // 注意返回值！low == high! 若无return，函数返回最后一次赋值的元素!
}
void InsertSort(int k[], int n)
{
    for (int i = 0; i < n-1; i++)
    {
        if (k[i] > k[i+1])
        {
            int tmp = k[i+1];
            int j = i+1;
            for(; k[j-1]>tmp and j > 0; j--)
            {
                k[j] = k[j-1];
            }
            k[j] = tmp;
        }
    }
}
void QSort(int k[], int low, int high)
{
    int point;
    if (high-low > 7) // 3. 优化小数组排序
    {
        while (low < high)
        {
            point = Partition(k, low, high);
            // 4. 采用尾递归，减小空间占用
            if (point - low < high - point)
            {
                QSort(k, low, point-1);
                low = point+1;
            }
            else
            {
                QSort(k, point+1, high);
                high = point-1;
            }
        }
    }
    else
    {
        InsertSort(k+low, high-low+1);
    }
}
void QuickSort(int k[], int n)
{
    QSort(k, 0, n-1);
    for (int i = 0; i < n; i++)
        cout << k[i] << " ";
    cout << endl;
}
int main()
{
    int k[] = {2, 1, 5, 7, 5, 6, 10, 20, 15, 17, 16, 14, 13};
    QuickSort(k, 13);
    return 0;
}

运行结果为

1 2 5 5 6 7 10 13 14 15 16 17 20

---

总结

以下为各种排序算法的性能表现：

需要注意的是，
若数据元素少、基本有序、需求稳定排序的话，采用前三种简单排序算法即可。

具体选用何种排序算法还是看数据表现以及项目需求啦~

数据结构与算法课程到此学习完毕，感谢鱼C工作室！
下附课程链接 https://www.bilibili.com/video/BV1jW411K7yg?spm_id_from=333.999.0.0