排序查找之快速排序

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

排序查找之概述

快速排序

分析

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

1. 从数列中挑出一个元素，称为 “基准”（pivot）；
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
3. 在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
4. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

时间复杂度

最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(nlogn)

代码实现

import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {
        int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

        quickSort(array);

        System.out.println(Arrays.toString(array));
    }

    public static void quickSort(int[] array) {
        quickSort(array, 0, array.length - 1);
    }


    private static void quickSort(int[] array, int left, int right) {
        // array 为空 => 没有需要快排的数组
        // left >= right => 左边赶上右边了,表示已经排完了
        // array.length <= 1 => 数组长度小于等于1无需排序了
        if (array == null || left >= right || array.length <= 1) {
            return;
        }
        // 进行分区, 找中间值
        int mid = partition(array, left, right);
        // 使用快排排列左边的子段
        quickSort(array, left, mid);
        // 使用快排排列右边的子段
        quickSort(array, mid + 1, right);
    }


    private static int partition(int[] array, int left, int right) {
        // 选择基准(pivot)
        int temp = array[left];
        // right与left相遇, 表示分区完成, 跳出循环
        while (right > left) {
            // 先判断基准数和后面的数依次比较,
            // right指针从right位置开始往前遍历, 最大边界是left指针的位置, 如果大于等于基准, 则right指针往前, 一直到找到比基准小的数, 才跳出while循环
            while (temp <= array[right] && left < right) {
                --right;
            }
            // 当基准数大于了 arr[left]，则填坑
            // left指针小于right指针的位置, 表示在中途遇到了比基准更小的数, 需要
            if (left < right) {
                // left位置的值重新赋值, 值为 right位置的值, 这个值比基准小
                array[left] = array[right];
                // left指针向后移动一个位置
                ++left;
            }
            // 现在是 arr[right] 需要填坑了
            // left指针从right位置开始往后移动, 最大边界是right指针的位置, 如果小于等于基准值, 则left指针往前, 一直找到比基准大的数, 才会跳出while循环
            while (temp >= array[left] && left < right) {
                ++left;
            }
            // left指针小于right指针的位置, 表示在移动中途遇到了比基准更大的数
            if (left < right) {
                // right位置的值重新赋值, 值为left位置的值, 这个值比基准大
                array[right] = array[left];
                // right指针向前移动一个位置
                --right;
            }
        }
        // right与left相遇了, 给left位置赋值, 值为基准值
        array[left] = temp;
        // 返回基准值位置
        return left;
    }
}