十大经典排序算法之快速排序

快速排序(Quick Sort)采用的是分治思想，即在一个无序的序列中选取一个任意的基准元素pivot，利用pivot将待排序的序列分成两部分，前面部分元素均小于或等于基准元素，后面部分均大于或等于基准元素，然后采用递归的方法分别对前后两部分重复上述操作，直到将无序序列排列成有序序列。

算法特性

• 稳定性

快速排序是一种不稳定的排序算法。

• 时间复杂度

快速排序的时间复杂度在最坏情况下是O(n^2)，平均的时间复杂度是O(N*logN)。

• 空间复杂度

快速排序是一种原地排序算法，不需要额外的空间进行排序。因此，快速排序的空间复杂度为O(1)。

算法步骤

快速排序算法通过多次比较和交换来实现排序，其流程如下：

1、首先设定一个基准值，通过该基准值将数组分成左右两部分。

2、将大于或等于基准值的数据集中到数组右边，小于基准值的数据集中到数组的左边。此时，左边部分中各元素都小于基准值，而右边部分中各元素都大于或等于基准值。

3、然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个基准值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

4、重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

动画演示

快速排序.gif

代码实现

Java代码:

private static int[] quickSort(int[] array, int left, int right) {
    if (left < right) {
        int partitionIndex = partition(array, left, right);
        quickSort(array, left, partitionIndex - 1);
        quickSort(array, partitionIndex + 1, right);
    }

    return array;
}

private static int partition(int[] array, int left, int right) {
    // 设定基准值
    int pivot = left;
    int index = pivot + 1;
    for (int i = index; i <= right; i++) {
        if (array[i] < array[pivot]) {
            swap(array, i, index);
            index ++;
        }
    }

    swap(array, pivot, index - 1);

    return index - 1;
}

private static void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

推荐阅读

• 轻松掌握二分法查找

•【技术教程】JRebel激活指南：让你的Java开发更高效！

• Java日志脱敏框架sensitive使用

• Zookeeper客户端Curator使用(分布式锁实现)

• 真绝了~使用Wireshark工具抓取https数据明文包