快速排序

算法思想

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

适用说明

快速排序是一种比较快速的排序算法，它的平均运行时间是 O(nlogn)，之所以特别快是由于非常精练和高度优化的内部循环，最坏的情形性能为 O(n^2)。像归并一样，快速排序也是一种分治的递归算法。从空间性能上看，快速排序只需要一个元素的辅助空间，但快速排序需要一个栈空间来实现递归，空间复杂度也为O(logn)。

过程图示

在一个数组中选择一个基点，比如第一个位置的 4，然后把4挪到正确位置，使得之前的子数组中数据小于 4，之后的子数组中数据大于 4，然后逐渐递归下去完成整个排序。

快速排序.png

我的理解

随机选择一个基准元素，遍历元素将小于基准元素的放置在左边，将大于基准元素的放置在右边，递归以上过程达到有序排列的目的

java代码实现

/**
 * Author: 编程的猫 iCat
 * Emil: 15827348069@163.com
 * Date: 3/31/21 9:36 PM
 * Desc: 快速排序
 */
public class PartitionSort {

    /**
     * 将数组分成大小两组，返回中间值的索引
     *
     * @param array 数组
     * @param left  数组的起始索引
     * @param right 数组的结束索引
     * @return 返回基准元素中间位置的索引（该索引元素的左边都小于该索引的元素，该索引右边都大于该索引的元素）
     */
    public static int partition(int[] array, int left, int right) {
        // 在array[left...right]间随机选一个元素作为基准元素
        swap(array, left, (int) (Math.random() * (right - left + 1) + left));//打乱首个元素的位置
        int pivot = array[left];
        int j = left;
        for (int i = left + 1; i <= right; i++) {

            // 数组内的元素大小分组（小的左边，大的右边）
            if (array[i] < pivot) {
                j++;
                swap(array, i, j);
            }

        }
        // 将基准元素交换到目标位置
        swap(array, left, j);
        return j;
    }

    /**
     * 递归快速排序
     *
     * @param array 数组
     * @param left  left
     * @param right right
     */
    private static void quickSort(int[] array, int left, int right) {
        if (left >= right) return;
        // 找到分界的元素的索引位置,同时aimIndex也是已排好序的元素索引
        int aimIndex = partition(array, left, right);

        quickSort(array, left, aimIndex - 1);
        quickSort(array, aimIndex + 1, right);
    }

    /**
     * 快速排序的思想：随机选择一个基准元素，
     * 遍历元素将小于基准元素的放置在左边，将大于基准元素的放置在右边，递归以上过程达到有序排列的目的
     *
     * @param array array
     */
    public static void sort(int[] array) {
        quickSort(array, 0, array.length - 1);
    }

    /**
     * 交换数组元素
     *
     * @param array 数组
     * @param left  前边索引
     * @param right 后边索引
     */
    private static void swap(int[] array, int left, int right) {
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }
}

C++代码实现

//快速排序
int partition(int array[], int left, int right) {
    // 随机选择一个基准元素
    swap(array[left], array[rand() % (right - left + 1) + left]);
    int pivot = array[left];
    int j = left;
    for (int i = left + 1; i <= right; ++i) {
        if (array[i] < pivot) {
            ++j;
            //大小元素分组
            swap(array[j], array[i]);
        }
    }
    swap(array[left], array[j]);
    return j;
}

void quickSort_(int array[], int left, int right) {
    if (left >= right)return;
    int p = partition(array, left, right);

    //递归执行
    quickSort_(array, left, p - 1);
    quickSort_(array, p + 1, right);
}

void quickSort(int array[], int len) {
    quickSort_(array, 0, len - 1);
}

部分内容引用自菜鸟教程