【高级排序】之快速排序

柔光的暖阳◎ 2022-02-02 12:59 197阅读 0赞

### 算法评价： ###

*  **时间复杂度：![20190511093749312.png][]。**  
    注：快速排序最坏情况下的时间复杂度是![20190511185338290.png][]，其平均时间复杂度是![20190511185346166.png][]。
 *  **空间复杂度：![20190511185353424.png][]**。
 *  **稳定性：不稳定。**
 *  **适用数据规模量：大规模。**  
    注：**快速排序通常是实际排序中的最好的选择，因为它的平均性能非常好**。快速排序的平均时间复杂度为，  
           相比起基本排序(冒泡、插入、选择排序)的要快得多，相比起同样时间复杂度的归并排序，快速排序的  
           隐含的常数因子小于归并排序的隐含的常数因子，因此快速排序又要比归并排序快。对于用空间换时  
           间的桶排序，虽然快速排序时间上要慢与桶排序，但空间上要节省得多，且快速排序相对适用范围更广、  
           更贴近大多数实际使用情况。

**算法复杂度与数据规模量关系图：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p1c3RyeV9kZW5n_size_16_color_FFFFFF_t_70][]

### 算法介绍： ###

快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

**具体的实现思路是：**  
        首先任意选取一个数据(通常选用数组的第一个数作为关键枢纽数据，然后将所有小于等于(或大于)它的数都放到它左边，所有大于(或大于等于)它的数都放到它右边，这个过程称为一趟快速排序。重复进行此步骤，最终就会得到有序的数据。

### 算法演示图及说明： ###

![20190511191813157.gif][]

**说明：**  
       上图示例的是左右指针法实现快速排序。以数组array的第一个元素array\[left\]为枢纽，i从左往右找大于枢纽的数，j从右往左找小于等于枢纽值的数。然后将找到的那两个数进行互换，这样一来就将大的数移动至右边，小的数移动至左边了,最后枢纽再与小于等于枢纽值区域的最后一个数(假设其位置的索引为idx)进行互换，当i与j相遇时，如果j处于小于等于枢纽的区域，那么此时idx就为j所在的位置的索引，如果当i与j相遇时,j处于大于枢纽的区域，那么idx就为接下来j移动到小于等于枢纽区域的第一个位置的索引。idx定下来后，枢纽值与idx位置的值进行互换。之后，再分别对\[left, idx - 1\] 与 \[idx + 1， right\]进行快速排序。

提示：此文字描述可参考下面的代码进行理解。

### Java对快速排序的(左右指针法)实现： ###

/**
     * 快速排序的Java实现
     *
     * @author JustryDeng
     * @date 2019/5/11 11:57
     */
    public class Quick {
    
        /**
         * 快速排序的java实现
         *
         * @param originArray
         *         数组
         * @date 2019/5/11 11:58
         */
        public static void sort(int[] originArray) {
            if (originArray == null || originArray.length <= 1) {
                return;
            }
            sortExecutor(originArray, 0, originArray.length - 1);
        }
    
        /**
         * 快速排序实现方法
         *
         * @param originArray
         *         数组
         * @param left
         *         数组的起始元素索引
         * @param right
         *         数组的结尾元素索引
         * @date 2019/5/11 11:58
         */
        private static void sortExecutor(int[] originArray, int left, int right) {
            if (left >= right) {
                return;
            }
            // 枢纽
            int pivot = originArray[left];
    
            int i = left, j = right;
            int tmp;
            while (i < j) {
                // 注意: 这里需要先循环 j--, 再循环i++;
                // 如果先循环i++,再循环j--的话，那么 快速排序 实现起来就会麻烦很多，而且性能也会下降
                while (j > i && originArray[j] > pivot) {
                    j--;
                }
                while (i < j && originArray[i] <= pivot) {
                    i++;
                }
                if (i < j) {
                    // 互换值
                    tmp = originArray[i];
                    originArray[i] = originArray[j];
                    originArray[j] = tmp;
                }
            }
            // 互换值
            originArray[left] = originArray[j];
            originArray[j] = pivot;
    
            // 递归进行快速排序
            sortExecutor(originArray, left, j - 1);
            sortExecutor(originArray, j + 1, right);
        }
    }

### 测试一下： ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p1c3RyeV9kZW5n_size_16_color_FFFFFF_t_70 1][]

控制台输出：

![20190511191944846.png][]

**快速排序，学习完毕！**

### ^\_^ 如有不当之处，欢迎指正 ###

### ^\_^ 本文已被收录进《程序员成长笔记(五)》，笔者JustryDeng ###

[20190511093749312.png]: /images/20220202/acf26e04fe08418891b6ac401509a0cf.png
[20190511185338290.png]: https://img-blog.csdnimg.cn/20190511185338290.png
[20190511185346166.png]: /images/20220202/3b766edf38fe4672bcd3c844db4d5dd3.png
[20190511185353424.png]: /images/20220202/0885604a78844a3c9bb37664389bb8a5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p1c3RyeV9kZW5n_size_16_color_FFFFFF_t_70]: /images/20220202/5127a6b85a5345a5a147e75710adda73.png
[20190511191813157.gif]: /images/20220202/63d7e66403c545db8e16d01bd7292954.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p1c3RyeV9kZW5n_size_16_color_FFFFFF_t_70 1]: /images/20220202/49e3b2ffd4614d628319f2dbd26ca62a.png
[20190511191944846.png]: /images/20220202/0a38d2ea030943a4acabe200b833e25c.png