快速排序

发布日期: 2021-04-23

文章字数: 687

快速排序的基本步骤：

找出一个基准数（一般选数组第一位即可）
将数组中比基准数大的数移动到它右边
将数组中比基准数小的数移动到它左边
以基准数为界，左右两边的子数组递归执行上述步骤

举一个简单的例子（使用_表示一个空位）：

假设数组有[4,7,2,3]，取第一个元素4为基准数，腾出一个空位：[_,7,2,3]
指针j从右往左遍历，发现3比基准数4小，于是把3移动到空位上：[3,7,2,_]
指针i从左往右遍历，发现7比基准数4大，于是把7移动到空位上：[3,_,2,7]
指针j从右往左遍历，发现2比基准数4小，于是把2移动到空位上：[3,2,_,7]
指针j继续移动，发现i等于j，于是第一轮遍历结束，把基准数4移动空位上：[3,2,4,7]
此时，比基准数4小的数都跑到左边，比4大的数都跑到了右边
以基准数4为界，将数组拆分两个子数组[2,3]和[7]，两个子数组递归执行上述步骤

再举个例子：

代码示例如下：

public class Quick {

    public static void main(String[] args) {
        int[] array = {3, 44, 38, 5, 27, 15, 36};
        quickSort(array);
        printArray(array);
    }

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

    private static void sort(int[] array, int i, int j) {
        if (i >= j) {
            return;
        }
        int start = i;
        int end = j;
        // 默认取序列第一位作为基准数
        int pivot = array[i];
        while (i < j) {
            // 从右向左遍历
            //跳过比pivot大的数，找到比pivot小的数
            while (i < j && array[j] > pivot) {
                j--;
            }
            if (i < j) {
                array[i++] = array[j];
            }

            // 从左向右遍历
            //跳过比pivot小的数，找到比pivot大的数
            while (i < j && array[i] < pivot) {
                i++;
            }
            if (i < j) {
                array[j++] = array[i];
            }
        }
        // 最后，将pivot填入空位
        array[i] = pivot;

        // 左右两边的子序列分别重复上述步骤
        sort(array, start, i - 1);
        sort(array, i + 1, end);
    }


    public static void printArray(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
    }
}