始.快速排序的简单介绍

1.快速排序简介

快速排序（Quicksort）是一种高效的排序算法，采用分治法（Divide and Conquer）策略。由托尼·霍尔（Tony Hoare）于1960年提出，因其平均时间复杂度为O(n log n)而被广泛应用。

2.核心思想

快速排序通过选取一个基准值（pivot），将数组分为两部分：一部分小于基准值，另一部分大于基准值。递归地对子数组进行排序，最终完成整个数组的排序。

3.算法步骤

1. 选择基准值：从数组中选择一个元素作为基准（通常选择第一个、最后一个或随机元素）。
2. 分区操作：重新排列数组，使得小于基准的元素放在左侧，大于基准的元素放在右侧。基准值位于最终正确位置。
3. 递归排序：对基准值左右两侧的子数组重复上述过程，直到子数组长度为1或0。

4.时间复杂度

• 最佳/平均情况：O(n log n)
• 最坏情况（如数组已排序且基准选择不当）：O(n²)

5.特点

• 原地排序：可通过优化实现原地分区，减少空间复杂度。
• 不稳定排序：相同元素的相对位置可能改变。
• 适用性：适合大规模数据排序，实际性能优于其他O(n log n)算法（如归并排序）。

一.文字描述流程 

这里以使用基础快速排序为 [ 3 , 6 , 8 , 10 , 1 , 2 , 1 ] 排序为例：

初始序列
[3, 6, 8, 10, 1, 2, 1]
选择基准值：3（第一个元素）

        1.第一次分区
        将小于3的元素移到左侧，大于3的元素移到右侧：
        [1, 2, 1, 3, 6, 8, 10]
        此时3位于正确位置。

        1-1.递归处理左子序列 [1, 2, 1]
        选择基准值：1
        分区后：[1, 2, 1] → [1, 1, 2]（1位于正确位置）
        继续处理右子序列 [2]，无需操作。

        1-2.递归处理右子序列 [6, 8, 10]
        选择基准值：6
        分区后：[6, 8, 10]（6已在正确位置）
        继续处理右子序列 [8, 10]，选择基准值8，分区后：[8, 10]。

最终有序序列
[1, 1, 2, 3, 6, 8, 10]

        可以看到，基础快速排序的核心思想是递归地将数据按"基准值"分为两部分，直到分割后的子序列元素不超过两个时，对这些小规模数据进行排序并终止递归。

二.代码实现

以下为基础快速排序的代码实现:

        递归的结束条件：当分区小于等于2时；

       思路：第一次执行方法体会将这段数据变为以一开始的arr[0]做代表的数据为基准值，使得基准值左侧元素全部小于基准值，基准值右侧元素全部大于基准值的一段数据。

             形如Eg:         1        3        6        2        3        9        12        98        19        33

再通过自身调用自身，通过更改后续调用的头尾元素来做到将前半区域和后半区域分别再次分区排序。而新调用的自身也可以继续向下调用，直到分到元素小于等于2时，执行结束递归的语句。

    //无优化快速排序-算法
    public static void quick_sort(int[] arr,int first,int last){
        //递归结束判断->元素数量小于等于2
        if(last - first <= 2){
            if(last-first <= 1) return;
            if(arr[first] > arr[first+1]) MyMath.swap(arr, first, first+1);
            return;
        }
        //排序核心主体
        int x = first;                  //头部 => 下标
        int y = last - 1;               //尾部 => 减一 -> 末尾下标
        int z = arr[first];             //基准值
        while (x < y){
            while (x < y && arr[y] >= z) y--;      //找到右侧一个小于基准值的数据
            if(x < y) arr[x++] = arr[y];           //将小于基准值的数据放在左侧
            while (x < y && arr[x] <= z) x++;      //找到左侧一个大于基准值的数据
            if(x < y) arr[y--] = arr[x];           //将大于基准值的数据放在左侧
        }
        arr[x] = z;                         //将基准值数据重新放回数组 (x == y)
        quick_sort(arr, first, x);          //对前半部分数组排序->递归
        quick_sort(arr, x + 1, last);       //对后半部分数组排序->递归
    }

    /*交换值*/
    public static void swap(int[]arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

三.代码优化

代码问题：

        在上文插入排序中，我们提到了通过减少循环中判定条件的思想来实现对代码的优化，在这里也是如此，我们在将后面的值前置，前面的值后置这一步骤中连续判断了很多重复的条件。

 while (x < y){
            while (x < y && arr[y] >= z) y--;      //找到右侧一个小于基准值的数据
            if(x < y) arr[x++] = arr[y];           //将小于基准值的数据放在左侧
            while (x < y && arr[x] <= z) x++;      //找到左侧一个大于基准值的数据
            if(x < y) arr[y--] = arr[x];           //将大于基准值的数据放在左侧
        }

        那我们要如何将这些重复判断的条件优化掉呢?

优化一:通过减少条件判断次数提升性能

目前多次判断的主要原因体现在我们的排序逻辑上，当前的逻辑是在满足x<y的情况下：

1. 判断尾部下标(y)对应元素(arr[y])是否大于z(基准值,arr[0])，如果大于那就y--之后再继续判断，直到找到一个小于z的数据。
2. 随后将我所找到的这个值与当前左侧头部下标(x)对应元素(arr[x])的值进行覆盖，覆盖完毕后让头部指向下一个位置
3. 再判断头部下标(x，此时是x+1)对应元素(arr[x])是否小于基准值，如果小于那就x++之后再继续判断，知道找到一个大于z的数据。
4. 随后将随找到的值域当前右侧下标(y)对应元素(arr[y])的值进行覆盖，覆盖完毕后让尾部之乡下一个位置。
5. 至此，一次换位操作结束，接下来判断x是否小于y,如果小于，则继续进行换位操作，直到x == y为止，将基准值放入arr[x]的位置

本质上我们就是要将分区后的区域分为左侧元素全部小于或大于右侧元素的情况，那我们完全可以不去把基准值放在两个区域的中间，而是让两个区域直接连在一起，这样我们要做的就是从前面和后面各找到一个满足条件的数据，然后只需要对这两个数据进行直接交换就好了。

所以我们可以将代码优化成这样:

    public static void batter_quick_sort_V1(int[] arr, int first, int last){
        if(last - first <= 2){
            if(last-first <= 1) return;
            if(arr[first] > arr[first+1]) MyMath.swap(arr, first, first+1);
            return;
        }
        int x = first;                  //头部 => 下标
        int y = last - 1;               //尾部 => 减一 -> 末尾下标
        int z = arr[first];             //基准值
//=================================================================================
        do{
            while(arr[x] < z) ++x;      //找到一个大于基准值的数据
            while(arr[y] > z) --y;      //找到一个小于基准值的数据
            if(x <= y){
                MyMath.swap(arr, x, y);
                ++x;
                --y;
            }
        }while(x <= y);
//=================================================================================
        batter_quick_sort_V1(arr, first, x);          //对前半部分数组排序
        batter_quick_sort_V1(arr, x, last);           //对后半部分数组排序
    }

        可以看到，我们修改了代码的两个部分，分别是将while循环改为了do-while循环，以及将后面执行递归所传入的参数改变了，首先我们来看do-while循环内：

        do{
            while(arr[x] < z) ++x;      //找到一个大于基准值的数据
            while(arr[y] > z) --y;      //找到一个小于基准值的数据
            if(x <= y){
                MyMath.swap(arr, x, y);
                ++x;
                --y;
            }
        }while(x <= y);

循环内部的条件判断进行了大幅减少，现在这里要做的就仅仅是：找到两个满足条件的数据，如果同时满足 x <= y ，则交换两个值并使他们分别前移或后移，现在在分完区域后，不但完成了与优化前一样的分区效果，还优化掉了大量判断。 

        接着是递归参数的改变：

        
        //旧的
        quick_sort(arr, first, x);          //对前半部分数组排序
        quick_sort(arr, x + 1, last);       //对后半部分数组排序


        //新的
        batter_quick_sort_V1(arr, first, x);          //对前半部分数组排序
        batter_quick_sort_V1(arr, x, last);           //对后半部分数组排序

        这是因为改变了分区操作的代码后，现在循环体执行完毕后x不再与y相等了，而是会相互错开此时x指向了后半区的第一个元素，也就是说x现在代表了前半区的元素个数，而且因为现在两个半区链接在了一起，少了中间的基准值，使得在给后半部分数组递归传入的参数不再需要+1了。

优化二：通过人为规定分区长度，来进一步提升排序代码的执行效率(大概率)

        基础快速排序的分区是以当前每个分区的第一个元素为基准值进行分区的，但是这样的基准值选取会带来很大的随机性。  分区操作的影响因素主要来源于 “基准值” 的选取 ， 所以如果选择的基准值所能够将数组分为相同的两个半区，代码效率会有明显提升!

        通过使用“三点取中法”，从头部元素，数组中间元素，尾部元素三者中，取位于中间值的那个值来作为基准值：

/*使用三点取中法 来界定数组中间值元素*/
int x = first;                  //头部 => 下标
int y = last - 1;               //尾部 => 减一 -> 末尾下标
int z = three_point_select(arr, x, (first+last)/2, last-1);     //基准值

//三点取中法
/*三点取中法:
*   三点: 头部元素 - 尾部元素 - 中间位置元素
*   将这三个值大小中位于中间的值返回出去
* */
static public int three_point_select(int[] arr, int a, int b, int c){
    if(a > b) MyMath.swap(arr, a, b);   //如果 a比b大,则交换
    if(a > c) MyMath.swap(arr, a, c);   //如果 a比c大,则交换 -> 确保a是最小的
    if(b > c) MyMath.swap(arr, b, c);   //如果 b比c大,则交换 -> 确保b是第二小的
    return arr[b];
}

         “三点取中法”的应用会使得基准值的选取更接近中间值。虽然有所改进，但实际效果不如第一种优化方案显著。

优化三:减少递归使用次数来做到进一步优化排序速度

        采用"单边递归法"可以显著提升快速排序的效率。传统双边递归的实现方式在时间消耗上存在不足，因为它总是先完全处理左侧半区的递归，再转而处理右侧半区。如果能够同时处理左右两侧的排序任务，就能实现对快速排序算法的有效优化。

单边递归法的优化思路：

快速排序的传统实现通常采用双边递归（即同时对左右子数组进行递归调用），而单边递归法（也称为尾递归优化）通过减少递归调用次数来优化空间复杂度。以下是具体思路：

1.减少递归深度

单边递归法每次只对一侧的子数组进行递归，另一侧通过循环处理。例如，优先处理较短的子数组，将较长的子数组通过循环迭代处理。这种策略确保递归深度最多为 $O(\log n)$，避免最坏情况下 $O(n)$ 的栈空间占用。

2.尾递归优化

将递归调用放在函数的最后一步（尾递归），使编译器或解释器能够优化为循环结构。例如：

• 传统递归：quicksort(left, pivot - 1); quicksort(pivot + 1, right);
• 单边递归：仅对一侧递归，另一侧通过修改参数并循环实现。

说完原理，接下来看代码实现：

     public static void batter_quick_sort_V3(int[] arr,int first,int last){
            if(last - first <= 2){
                if(last-first <= 1) return;
                if(arr[first] > arr[first+1]) MyMath.swap(arr, first, first+1);
                return;
            }
            while(first < last){
            //Partition-----------------------------------------------------------
            //使用三点取中法 来界定数组中间值元素
            int x = first;                  //头部 => 下标
            int y = last - 1;               //尾部 => 减一 -> 末尾下标
            int z = three_point_select(arr, x, (first+last)/2, last-1); //基准值
            do{
                while(arr[x] < z) ++x;      //找到一个大于基准值的数据
                while(arr[y] > z) --y;      //找到一个小于基准值的数据
                if(x <= y){
                    MyMath.swap(arr, x, y);
                    ++x;
                    --y;
                }
            }while(x <= y);
            batter_quick_sort_V3(arr, first, x);//对左半部分数组排序
            /*修改右侧起始下标，并将整体套入循环，实现同时左右分区，即“单边递归”*/
            first = x;
        }
    }

        单边递归在嵌入式系统或内存受限环境中优势明显，能有效管理栈空间。对于近乎有序的数据，可避免最坏情况下的性能退化。        

优化四：优化快速排序在面对小范围数据的时候（16个以下）的性能

        虽然快速排序在面对数据量庞大的数据时，它的排序速度十分优秀，但是在面对小于16个元素的小型数据的排序时，却显得十分吃力，甚至不如插入排序，因为它在进行排序之前要进行选定基准值等一系列操作，那么我们这次的优化思路就是让我们的分区进行到16个元素为止，接下来使用插入排序来完成剩余的排序内容。

        代码如下：

    //优化四: 优化快速排序在面对小范围数据的时候（16个以下）的性能
    final static int selectSortNum = 16;
    public static void _batter_quick_sort_V4(int[] arr,int first,int last){
        if(last - first <= 2){
            if(last-first <= 1) return;
            if(arr[first] > arr[first+1]) MyMath.swap(arr, first, first+1);
            return;
        }
        while((last-first) > selectSortNum){
            //Partition----------------------------------------------------------
            //使用三点取中法 来界定数组中间值元素
            int x = first;                  //头部 => 下标
            int y = last - 1;               //尾部 => 减一 -> 末尾下标
            int z = three_point_select(arr, x, (first+last)/2, last-1);  //基准值
            do{
                while(arr[x] < z) ++x;      //找到一个大于基准值的数据
                while(arr[y] > z) --y;      //找到一个小于基准值的数据
                if(x <= y){
                    MyMath.swap(arr, x, y);
                    ++x;
                    --y;
                }
            }while(x <= y);
            _batter_quick_sort_V4(arr, first, x);//对左半部分数组排序
            /*修改右侧起始下标，并将整体套入循环，实现同时左右分区，即“单边递归”*/
            first = x;
        }
    }

    //优化四的本体:
    public static void batter_quick_sort_V4(int[] arr,int first,int last){
        //先将数组分为以16个或者16个以下元素个数为单位的多个区,再使用插入排序对这些区进行排序
        _batter_quick_sort_V4(arr, first, last);
        MyMath.unguarded_insert_sort(arr);
    }

        将庞大的数据分成以16个元素为单位的小区，再由插入排序进行高效处理，进一步提升了快速排序的速度，本次我要介绍的就是这几种优化方式，接下来看性能测试。

四.性能测试:

请输入要测试的数组长度(超过10不打印):
1000
排序成功!
运行时间:1.0ms
排序成功!
运行时间:1.0ms
排序成功!
运行时间:0.0ms
排序成功!
运行时间:1.0ms
排序成功!
运行时间:1.0ms

=====================================

请输入要测试的数组长度(超过10不打印):
10000
排序成功!
运行时间:3.0ms
排序成功!
运行时间:3.0ms
排序成功!
运行时间:3.0ms
排序成功!
运行时间:3.0ms
排序成功!
运行时间:3.0ms

=====================================

请输入要测试的数组长度(超过10不打印):
100000
排序成功!
运行时间:20.0ms
排序成功!
运行时间:15.0ms
排序成功!
运行时间:11.0ms
排序成功!
运行时间:10.0ms
排序成功!
运行时间:10.0ms

=====================================

请输入要测试的数组长度(超过10不打印):
1000000
排序成功!
运行时间:72.0ms
排序成功!
运行时间:74.0ms
排序成功!
运行时间:72.0ms
排序成功!
运行时间:69.0ms
排序成功!
运行时间:65.0ms

=====================================

请输入要测试的数组长度(超过10不打印):
10000000
排序成功!
运行时间:936.0ms
排序成功!
运行时间:692.0ms
排序成功!
运行时间:659.0ms
排序成功!
运行时间:617.0ms
排序成功!
运行时间:594.0ms

=====================================

请输入要测试的数组长度(超过10不打印):
100000000
排序成功!
运行时间:35984.0ms
排序成功!
运行时间:6658.0ms
排序成功!
运行时间:6839.0ms
排序成功!
运行时间:6126.0ms

尾.个人想说的话：

我是一名学习JAVA等编程语言的普通学生，如果我的这篇文章帮助到了你，我很开心，同时如果我的文章有问题，请各位发现后对我所说的有问题的部分做出修改和指正（请详细一些），避免他人看到造成误导，欢迎各位在评论区讨论、补充、以及纠正错误。

#如果觉得博客内容对你有帮助的话可以支持一下我的其它博客：

• (Java)算法学习: 选择排序-排序过程拆解与算法理解
• (Java)算法学习: 插入排序-排序过程拆解与算法优化