?个人博客：www.hellocode.top
?Java知识导航：Java-Navigate
?CSDN：HelloCode.
?知乎：HelloCode
?掘金：HelloCode
⚡如有问题，欢迎指正，一起学习~~
快速排序（Quick Sort）是一种高效的排序算法，是对冒泡排序的优化。它采用分治法（Divide and Conquer）的思想，将待排序序列不断分割成较小的子序列，然后对每个子序列进行排序，最后合并得到有序的序列。快速排序在大多数情况下具有优异的性能，是许多常见排序算法中最快的之一。

基本思想

快速排序动画演示

这里的动画用大佬五分钟学算法的图，很清晰
  1. 选择一个基准元素（pivot）作为参考点。
  2. 将所有比基准元素小的元素移到基准元素的左边，将所有比基准元素大的元素移到基准元素的右边。此过程称为分区（partitioning）。
  3. 对基准元素左右两边的子序列递归地进行相同的快速排序，直到子序列的大小为1或0，表示子序列已经有序。
如上图所示，快速排序的基本思想就是选取一个基准数，将基准数小的都放在左边，大的都放在右边，也就是每次循环都会确定出基准数应该在的正确位置。

代码实现

对应在代码层面，需要使用到递归法来实现，对于快速排序来说，递归相对还是很容易想到的

下面展示Java和C两种版本（C语言版本由俺的女朋友小周提供?）

/**
 * @author HelloCode
 * @blog https://www.hellocode.top
 * @date 2023年08月08日 21:14
 */
public class QuickSort {
    public static void quickSort(int[] arr) {
        // 特殊情况处理
        if (arr == null || arr.length == 0 || arr.length == 1) {
            return;
        }
        // 递归入口
        sort(arr, 0, arr.length - 1);
    }

    private static void sort(int[] arr, int left, int right) {
        // 递归出口
        if (left > right) {
            return;
        }
        // 初始化双指针
        int i = left, j = right;
        // 选取基准数
        int base = arr[left];
        while (i != j) {
            // （注意！！！！）从右边开始
            // 找比基准数小的
            while (i < j && arr[j] >= base) {
                j--;
            }
            // 从左边找比基准数大的
            while (i < j && arr[i] <= base) {
                i++;
            }
            // 交换i j
            if (i < j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // 基准数归位(此时i == j)
        arr[left] = arr[i];
        arr[i] = base;
        // 开始左右两边分别快排
        sort(arr, left, i - 1);
        sort(arr, i + 1, right);
    }
}

测试：

/**
 * @author HelloCode
 * @blog https://www.hellocode.top
 * @date 2023年08月08日 21:14
 */
public class Test {
    public static void main(String[] args) {
        int[] arr = {21, 13, 4, 10, 7, 65, 32, 15, 32, 19, 33, 65, 89, 72, 12};
        System.out.println("排序前：" + Arrays.toString(arr));
        QuickSort.quickSort(arr);
        System.out.println("排序后：" + Arrays.toString(arr));
    }
}

image-20230808213942941

C语言：

#include <stdio.h>
#include<string.h>
void quick_sort(int* arr, int left, int right)
{
    if (left > right)
        return;
    int i = left, j = right;
    int key = arr[i];
    while (i != j)
    {
        while (arr[j] >= key && i < j)
        {
            j--;
        }
        while (arr[i] <= key && i < j)
        {
            i++;
        }
        if (i < j)    //进行交换
        {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }
    arr[left] = arr[i];
    arr[i] = key;
    quick_sort(arr, left, i - 1);
    quick_sort(arr, i + 1, right);
}
int main()
{
    int arr[] = { 21, 13, 4, 10, 7, 65, 32, 15, 32, 19, 33, 65, 89, 72, 12 };
    int size = sizeof(arr) / sizeof(arr[0]);
    printf("排序前：");
    for (int i = 0; i < size; i++)
    {
        printf("%d  ", arr[i]);
    }
    quick_sort(arr, 0, size - 1);
    printf("\n排序后：");
    for (int i = 0; i < size; i++)
    {
        printf("%d  ", arr[i]);
    }
    printf("\n");
    return 0;
}

C++：

//C++实现
#include <iostream>
using namespace std;

void quick_sort(int* arr, int left, int right)
{
    if (left > right)
        return;
    int i = left, j = right;
    int key = arr[i];
    while (i != j)
    {
        while (arr[j] >= key && i < j)
        {
            j--;
        }
        while (arr[i] <= key && i < j)
        {
            i++;
        }
        if (i < j)    //进行交换
        {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }
    arr[left] = arr[i];
    arr[i] = key;
    quick_sort(arr, left, i - 1);
    quick_sort(arr, i + 1, right);
}
int main()
{
    int arr[] = { 21, 13, 4, 10, 7, 65, 32, 15, 32, 19, 33, 65, 89, 72, 12 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    cout << "排序前：";
    for (int i = 0; i < sz; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
    quick_sort(arr, 0, sz - 1);
    cout << "排序后：";
    for (int i = 0; i < sz; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

这里先移动j还是先移动i主要是需要看基准数选取的位置，如果选最左边的数，就需要先移动j（确保i == j 时对应的值是小于基准数的，再把基准数和该数交换，符合排序规则）
如果选取的基准数是最右边，则先移动i指针（确保 i == j 时对应的值是大于基准数的）

优化

快排的优化主要需要关注基准数的选取，如果待排序数组整体偏降序，此时还选最左侧的为基准数的话，效率就相对慢一些，所以选取一个好的基准数可以让快排的效率更加稳定~

主要的方法有以下几种：

  1. 随机选择基准元素：选择随机的基准元素可以降低最坏情况的概率，进而提高算法性能。
  2. 三数取中法：在选取基准元素时，不是简单地选取第一个或最后一个元素，而是选择中间元素、第一个元素和最后一个元素中的中位数作为基准元素，也可以降低最坏情况的概率。

这里基准数的选取可以很巧妙，还有很多种其他方法，都可以降低最坏情况的发生，本文以三数取中法为例：

/**
 * @author HelloCode
 * @blog https://www.hellocode.top
 * @date 2023年08月08日 21:14
 */
public class QuickSort {
    public static void quickSort(int[] arr) {
        // 特殊情况处理
        if (arr == null || arr.length == 0 || arr.length == 1) {
            return;
        }
        // 递归入口
        sort(arr, 0, arr.length - 1);
    }

    private static void sort(int[] arr, int left, int right) {
        // 递归出口
        if (left > right) {
            return;
        }
        // 初始化双指针
        int i = left, j = right;
        // 选取基准数
        getBase(arr, left, right);
        int base = arr[left];
        while (i != j) {
            // （注意！！！！）从右边开始
            // 找比基准数小的
            while (i < j && arr[j] >= base) {
                j--;
            }
            // 从左边找比基准数大的
            while (i < j && arr[i] <= base) {
                i++;
            }
            // 交换i j
            if (i < j) {
                swap(arr, i, j);
            }
        }
        // 基准数归位(此时i == j)
        arr[left] = arr[i];
        arr[i] = base;
        // 开始左右两边分别快排
        sort(arr, left, i - 1);
        sort(arr, i + 1, right);
    }

    // 取三点中间值（最终会移动到left位置，这样可以不改变原有代码）
    private static void getBase(int[] arr, int left, int right) {
        // 这里可以防止溢出且使用 >> 效率相对能高一些
        // 等价于 (left + right) / 2
        int mid = left + ((right - left) >> 1);
        // 确保第一个元素最小
        if (arr[left] > arr[right]) {
            swap(arr, left, right);
        }
        // 确保最后一个元素最大
        if (arr[mid] > arr[right]) {
            swap(arr, mid, right);
        }
        // 确定mid就是中间值，交换到最左边
        if (arr[left] < arr[mid]) {
            swap(arr, left, mid);
        }
        System.out.println("基准数为：" + arr[left]);
    }

    // 交换数组两下标元素位置
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

测试：

/**
 * @author HelloCode
 * @blog https://www.hellocode.top
 * @date 2023年08月07日 21:02
 */
public class Test {
    public static void main(String[] args) {
        int[] arr = {21, 13, 4, 10, 7, 65, 32, 15, 32, 19};
        System.out.println("排序前：" + Arrays.toString(arr));
        BubbleSort.bubbleSortOptimized1(arr);
        System.out.println("排序后：" + Arrays.toString(arr));
    }
}
排序前：[21, 13, 4, 10, 7, 65, 32, 15, 32, 19, 33, 65, 89, 72, 12]
基准数为：15
基准数为：7
基准数为：4
基准数为：12
基准数为：10
基准数为：13
基准数为：32
基准数为：21
基准数为：19
基准数为：32
基准数为：65
基准数为：33
基准数为：65
基准数为：72
基准数为：89
排序后：[4, 7, 10, 12, 13, 15, 19, 21, 32, 32, 33, 65, 65, 72, 89]

C语言：

//C语言实现
#include <stdio.h>

void Swap(int* a, int* b)        //交换变量
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
int GetMidIndex(int* arr, int left, int right)        //三值取中
{
    int mid = (left + right) / 2;
    if (arr[left] < arr[right]){
        if (arr[mid] < arr[left]){
            return left;
        }else if (arr[mid] < arr[right]){
            return mid;
        }else{
            return right;}
    }else{
        if (arr[mid] < arr[right]){
            return right;
        }else if (arr[mid] < arr[left]){
            return mid;
        }else{
            return left;
        }
    }
}
void quick_sort(int* arr, int left, int right)    //排序
{
    if (left > right)
        return;
    int i = left, j = right;
    int key=GetMidIndex(arr,left,right);
    Swap(&arr[key], &arr[left]);
    key = arr[left];

    while (i != j)
    {
        while (arr[j] >= key && i < j)
        {
            j--;
        }
        while (arr[i] <= key && i < j)
        {
            i++;
        }
        if (i < j)    //进行交换
        {
            Swap(&arr[i], &arr[j]);
        }
    }
  
    arr[left] = arr[i];
    arr[i] = key;    //使每次基准值得以确定
    //左右两边分别再次进行排序
    quick_sort(arr, left, i - 1);
    quick_sort(arr, i + 1, right);
}
int main()    //测试
{
    int arr[] = { 21, 13, 4, 10, 7, 65, 32, 15, 32, 19, 33, 65, 89, 72, 12 };
    int size = sizeof(arr) / sizeof(arr[0]);
    printf("排序前：");
    for (int i = 0; i < size; i++)
    {
        printf("%d  ", arr[i]);
    }
    quick_sort(arr, 0, size - 1);
    printf("\n排序后：");
    for (int i = 0; i < size; i++)
    {
        printf("%d  ", arr[i]);
    }
    printf("\n");
    return 0;
}

C++：

//C++实现
#include <iostream>
using namespace std;

void Swap(int* a, int* b)        //交换变量
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
int GetMidIndex(int* arr, int left, int right)        //三值取中
{
    int mid = (left + right) / 2;
    if (arr[left] < arr[right]) {
        if (arr[mid] < arr[left]) {
            return left;
        }
        else if (arr[mid] < arr[right]) {
            return mid;
        }
        else {
            return right;
        }
    }
    else {
        if (arr[mid] < arr[right]) {
            return right;
        }
        else if (arr[mid] < arr[left]) {
            return mid;
        }
        else {
            return left;
        }
    }
}
void quick_sort(int* arr, int left, int right)    //排序
{
    if (left > right)
        return;
    int i = left, j = right;
    int key = GetMidIndex(arr, left, right);
    Swap(&arr[key], &arr[left]);
    key = arr[left];

    while (i != j)
    {
        while (arr[j] >= key && i < j)
        {
            j--;
        }
        while (arr[i] <= key && i < j)
        {
            i++;
        }
        if (i < j)    //进行交换
        {
            Swap(&arr[i], &arr[j]);
        }
    }
    arr[left] = arr[i];
    arr[i] = key;    //使每次基准值得以确定
    //左右两边分别再次进行排序
    quick_sort(arr, left, i - 1);
    quick_sort(arr, i + 1, right);
}
int main()
{
    int arr[] = { 21, 13, 4, 10, 7, 65, 32, 15, 32, 19, 33, 65, 89, 72, 12 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    cout << "排序前：";
    for (int i = 0; i < sz; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
    quick_sort(arr, 0, sz - 1);
    cout << "排序后：";
    for (int i = 0; i < sz; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

总结

优点

  1. 高效性：快速排序是一种高效的排序算法，在大多数实际情况下，它的性能通常比其他常见排序算法（如冒泡排序、插入排序）更好。
  2. 原地排序：快速排序是原地排序算法，不需要额外的辅助空间，只需在原始数组上进行交换操作。

缺点

  1. 最坏情况下的性能：当待排序序列已经基本有序或完全逆序时，快速排序的时间复杂度退化为 O(n^2)，导致性能下降。这是因为基准元素的选择可能导致分区不平衡，使得分区操作不再能有效地减少问题规模。
  2. 不稳定性：快速排序是一种不稳定的排序算法，意味着相等元素的相对顺序在排序后可能发生变化。这在某些情况下可能导致问题，特别是对于复杂对象的排序，需要额外的处理来保持稳定性。

复杂度

  • 时间复杂度：快速排序的平均时间复杂度为O(n log n)，最坏情况下为O(n^2)。
  • 空间复杂度：快速排序是原地排序算法，空间复杂度为O(log n)。
适用于处理大规模数据集的排序，尤其在平均情况下，快速排序的性能较优。但在处理已经有序或近乎有序的数据集时，快速排序的性能可能会下降，这时候其他稳定的排序算法可能更合适。
END
本文作者： 文章标题：【数据结构与算法】十大经典排序算法-快速排序
 本文地址：https://www.jiusi.cc/archives/250/
 版权说明：若无注明，本文皆九思のJava之路原创，转载请保留文章出处。
最后修改：2023 年 08 月 13 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏