快速排序详解 ------------Java语言描述

绝地灬酷狼 2022-05-17 13:39 205阅读 0赞

# 1.1 用具体例子说明 #

> 十人排序问题：
> 
> 1.  你先吆喝一声，比第一个人低的所有人都站在第一名前面，其余人站后面
> 2.  然后队伍就被你分成了两个部分，而且原来队伍的第一名的位置将被确定为切割点，不再改动。
> 3.  对于前面的队伍，你进行如下操作
>     
>     1.  你先吆喝一声，比第一个人低的所有人都站在第一名前面，其余人站后面
>     2.  然后队伍就被你分成了两个部分，而且原来队伍的第一名的位置将被确定为切割点，不再改动。
> 4.  对于后面的队伍，你进行如下操作
>     
>     1.  你先吆喝一声，比第一个人低的所有人都站在第一名前面，其余人站后面
>     2.  然后队伍就被你分成了两个部分，而且原来队伍的第一名的位置将被确定为切割点，不再改动。
> 5.  然后重复上述步骤直到每个队伍都只有一个人时，停止排序，此时队伍将成为有序。

# 1.2 排序思想 #

> 明显用到了分而治之，使用第一位值作为分割值，所有小于的值都将被放置在第一位的前面，其余值放在后面，并且这个分割值位置确定，不再参与后续改动。并对每一个分割出来的队伍递归使用分割，直到不可分割为止。

# 1.3 见名知意 #

> 快速排序的名字与其他排序的名称不同，因为其他排序几乎都是使用排序的手段或者过程命名：插入排序，选择排序，归并排序，基数排序，等等。快速排序的名字似乎只告诉我们快速排序很快。所以记忆快速排序建议用"随机切割排序"这种名字。

# 1.4 抽象过程 #

> 遇到一组待排序的数组。
> 
> 1.  先以第一个数int m = a\[0\] 作为切割点，然后将小于a\[0\] 的数全部放在a\[0\]的紧接的后面，不小于a\[0\]的一堆数放在小于的数组之后，即放在数组的最后面。
> 2.  将 a\[0\] 与小于a\[0\]的数的最后一个数交换位置，此时数组被切割为两个部分，在原来a\[0\]前面的都是小于a\[0\]的数，后面的数都是不小于a\[0\] 的数.
> 3.  逻辑上独立出来上面两个数组。
> 4.  对这两个数组进行循环上述操作，直到切割出来的数组的大小为1时，停止操作。
> 5.  经过上述四步，此时数组有序。

# 1.5 实例操作 #

![70][]

# 1.6 代码实现（JAVA版本） #

## 1.6.1 快排接口 ##

所有排序的接口，我都给两个接口

public static void quickSort(int[] a) {
            quickSort(a, 0, a.length - 1);
        }
    
        private static void quickSort(int[] a, int lo, int hi) {
            if (hi <= lo || lo < 0 || hi >= a.length) {
                return;
            }
            // 使用第一位作为枢纽，进行分割数组
            int pivotIndex = partition(a, lo, hi);
            // 递归排序，先排切割值前面的数组，再排之后的数组（分而治之）
            quickSort(a, lo, pivotIndex - 1);
            quickSort(a, pivotIndex + 1, hi);
        }

## 1.6.2 切割部分(重要) ##

切割部分是整个代码中最重要的部分，将所有的小于第一位的数字全部紧贴着第一位连续放置，之后将其中的最后一位与第一位交换，此时所有数字都由切割数字分为了两个部分。

/**
         * 
         * Description: 找到所有比第一位值小的值并放在第一位的前面，其余值在第一位的后面。
         *
         * @Title: getSplitIndex
         * @param a
         * @param lo
         * @param hi
         * @return int
         */
        private static int partition(int[] a, int lo, int hi) {
            int head = lo + 1;
            int SplitIndex = lo;
    
            for (int rear = hi; head < rear && rear >= lo; rear--) {
                if (a[rear] < a[lo]) {
                    while (head < rear && a[head] < a[lo]) {
                        head++;
                    }
                    if (head >= rear) {
                        break;
                    }
                    // 交换 headIndex和rearIndex的值.
                    int t = a[head];
                    a[head++] = a[rear];
                    a[rear] = t;
                }
            }
            if (a[head] >= a[SplitIndex]) {
                head--;
            }
            int t = a[head];
            a[head] = a[SplitIndex];
            a[SplitIndex] = t;
            SplitIndex = head;
            return SplitIndex;
        }

# 1.7 代码实现（C语言版） #

TODO,改天写

# 1.8 算法分析 #

快排是最优秀的算法，但是不稳定。

此外，凡是使用分而治之，递归的高级排序，那么在数组被切割到比较小的时候，我们都可以让其转化为基本简单排序增快速度，因为基本简单排序不需要频繁的入栈出栈，所以时间反而效果更好。

此外，切分数组效果最好的时候明显是均分数组，最坏情况是以最大值/最小值切分数组。而我在本文中直接使用了第一位，如果是降序/升序数组，那么快排将会有最坏的效果O(n^2)，为了避免这种最坏情况，现在有两种建议：

1.  在第一次排序前随机打乱数组(可能不好理解，但确实是很多时候需要做的)。无论什么数组，增加一次打乱来避免最坏情况，打乱后完全不可能出现最坏情况(别给我说有可能，明白说不可能，)
2.  要么就是选择a\[lo\],a\[(lo+hi)/2\], a\[hi\] 中的中位数，让其与a\[lo\]交换顺序，接着使用a\[lo\]，这样尽可能避免最坏情况，坏处是每次切割都需要排序，相当于把打乱数组的代价均摊到了每次排序中。

# 1.9全部源码 #

package unit09.sort;
    
    /**
     * Description: 快速排序java实现
     *
     * @ClassName: QuickSort
     * @author 过道
     * @date 2018年8月11日 下午3:07:26
     */
    public class QuickSort {
        
        public static void quickSort(int[] a) {
            quickSort(a, 0, a.length - 1);
        }
    
        private static void quickSort(int[] a, int lo, int hi) {
            if (hi <= lo || lo < 0 || hi >= a.length) {
                return;
            }
            // 使用第一位作为枢纽，进行分割数组
            int pivotIndex = partition(a, lo, hi);
            // 递归排序，先排切割值前面的数组，再排之后的数组（分而治之）
            quickSort(a, lo, pivotIndex - 1);
            quickSort(a, pivotIndex + 1, hi);
        }
    
        /**
         * 
         * Description: 找到所有比第一位值小的值并放在第一位的前面，其余值在第一位的后面。
         *
         * @Title: getSplitIndex
         * @param a
         * @param lo
         * @param hi
         * @return int
         */
        private static int partition(int[] a, int lo, int hi) {
            int head = lo + 1;
            int SplitIndex = lo;
    
            for (int rear = hi; head < rear && rear >= lo; rear--) {
                if (a[rear] < a[lo]) {
                    while (head < rear && a[head] < a[lo]) {
                        head++;
                    }
                    if (head >= rear) {
                        break;
                    }
                    // 交换 headIndex和rearIndex的值.
                    int t = a[head];
                    a[head++] = a[rear];
                    a[rear] = t;
                }
            }
            if (a[head] >= a[SplitIndex]) {
                head--;
            }
            int t = a[head];
            a[head] = a[SplitIndex];
            a[SplitIndex] = t;
            SplitIndex = head;
            return SplitIndex;
        }
    
    }

[70]: /images/20220517/7aed2a703c9a41208b52da5b56283a48.png