算法排序-快速排序

简介

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

时间复杂度

O(n^2)

思路分析

接下来把中轴左端的元素继续取中轴，跟上面过程一样，继续找比中轴小的元素放中轴左边，比中轴大的元素放中轴右边。中轴右边元素同理。

直到中轴的左边、右边只剩一个元素则排序完成。 因为只剩一个元素中轴前面的元素一定是比中轴小 ，只剩一个元素中轴后面的元素一定比中轴大。

代码实现

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {2, 6, 5, 7, 9, 1, 3, 4};
        //int[] arr = {2, 1, 1, 1, 1, 2};
// int[] arr = new int[80];
// Random random = new Random();
//
// for (int i = 0; i < 80; i++) {
// arr[i] = random.nextInt(80000);
// }
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    /** * 快速排序 * * @param arr 待排序数组 * @param left 数组最左端 * @param right 数组最右端 */
    public static void quickSort(int[] arr, int left, int right) {
        // 保证两端索引不会交叉越过 同时保证递归能够结束避免死循环
        // 当pivot左边没有元素 left=0 right=-1 
        // 当pivot左边只有一个元素 left=0 right=0
        if (left >= right) {
            return;
        }
        // 保存最左端在过程中left不被修改 修改l
        int l = left;
        // 保存最右端在过程中right不被修改 修改r
        int r = right;
        // 取中轴 （取第一个数为中轴）
        int pivot = arr[left];
        // 如果左边和右边索引没碰撞 或者没交叉越界 说明元素还没找完 继续找
        while (left < right) {
            // 循环里的比较方向如下
            // left → ← right
            // ↓ ↓
            // 2 6 5 7 9 1 3 4

            // 下面两个循环必须是从right--这个循环开始 因为我们开始取中轴取的是第一个数 并且间接性的把他给保存起来了
            // 又因为left停留在第一个位置 所以就先从右边开始找，找到比pivot小的数就往left位置放

            // left < right 是为了保证right不会小于0而导致索引越界，极端情况下12345 该循环会一直--到-1然后导致越界
            // arr[right] >= pivot 如果=true证明当前元素比pivot大 那么继续right--往前一个找
            while (left < right && arr[right] >= pivot) {
                right--;
            }
            // 循环退出证明arr[right]比pivot小 就把arr[right]往left放
            arr[left] = arr[right];
            // 同理 arr[left] <= pivot 如果=true证明当前元素比pivot小 那么继续right--往前一个找
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            // 同理 循环退出证明arr[left]比pivot大 就把arr[left]往right放
            arr[right] = arr[left];
        }
        // 循环结束的时候也就是left和right碰撞的时候
        // 碰撞时：碰撞的左边全是比pivot小的元素 碰撞的右边都是比pivot大的元素 所以碰撞时的位置就是中轴要放的位置
        // 因为碰撞时left==right 所以这里使用left或者right都行
        arr[left] = pivot;
        // 把中轴左边的元素 再次取中轴找左右边的元素
        quickSort(arr, l, left - 1);
        // 把中轴右边的元素 再次取中轴找左右边的元素
        quickSort(arr, left + 1, r);
        //递归到中轴的左边、右边只剩一个元素则排序完成 因为只剩一个元素中轴前面的元素一定是比中轴小 ，只剩一个元素中轴后面的元素一定比中轴大
    }
}

运行输出：

[1, 2, 3, 4, 5, 6, 7, 9]

总结

快速排序快是因为空间换取了时间。快速排序是不稳定的排序算法，当一个数组是有序或者基本有序，则退化成冒泡排序，这种情况可以考虑使用随机pivot来处理。在数组无序时快速排序速度极快。

算法一定要明白思路，明白思路，代码实现都是大同小异。