快速排序

• 快速排序
  • 基本介绍
  • 代码实现
  • 特点及性能

基本介绍

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

视频讲解

1. 选定Pivot中心轴
2. 将大于Pivot的数字放在Pivot的右边
3. 将小于Pivot的数字放在Pivot的左边
4. 分别对左右子序列重复前三步操作

代码实现

// 快速排序交换式
public static void quickSort(int[] arr, int left, int right) {
    int l = left;
    int r = right;
    int pivot = arr[(left + right) / 2];
    int temp;
    while (l < r) {
        while (arr[l] < pivot) {
            l++;
        }
        while (arr[r] > pivot) {
            r--;
        }
        // 说明已经满足条件
        if (l >= r) {
            break;
        }
        // 交换位置
        temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
        if (arr[l] == pivot) {
            r--;
        }
        if (arr[r] == pivot) {
            l++;
        }
        if (l == r) {
            l++;
            r--;
        }
        if (left < r) {
            quickSort(arr, left, r);
        }
        if (l < right) {
            quickSort(arr, l, right);
        }
    }
}
// 快速排序填坑式 速度快
public static void quickSort2(int[] arr, int left, int right) {
    int pivot = arr[left];
    int l = left;
    int r = right;
    while (l < r) {
        while (arr[r] > pivot && l < r) {
            r--;
        }
        if (l == r) {
            break;
        }
        arr[l] = arr[r];
        l++;
        while (arr[l] < pivot && l < r) {
            l++;
        }
        if (l == r) {
            break;
        }
        arr[r] = arr[l];
        r--;
    }
    arr[l] = pivot;
    if (l > left) {
        quickSort2(arr, left, l - 1);
    }
    if (r < right) {
        quickSort2(arr, r + 1, right);
    }
}

快速排序填坑式的另一种，速度稍慢，但代码简洁

快速排序

特点及性能

快速排序是在冒泡排序的基础上改进而来的，冒泡排序每次只能交换相邻的两个元素，而快速排序是跳跃式的交换，交换的距离很大，因此总的比较和交换次数少了很多，速度也快了不少。

但是快速排序在最坏情况下的时间复杂度和冒泡排序一样，是 O(n2)，实际上每次比较都需要交换，但是这种情况并不常见。我们可以思考一下如果每次比较都需要交换，那么数列的平均时间复杂度是 O(nlogn)，事实上在大多数时候，排序的速度要快于这个平均时间复杂度。这种算法实际上是一种分治法思想，也就是分而治之，把问题分为一个个的小部分来分别解决，再把结果组合起来。

快速排序只是使用数组原本的空间进行排序，所以所占用的空间应该是常量级的，但是由于每次划分之后是递归调用，所以递归调用在运行的过程中会消耗一定的空间，在一般情况下的空间复杂度为 O(logn)，在最差的情况下，若每次只完成了一个元素，那么空间复杂度为 O(n)。所以我们一般认为快速排序的空间复杂度为 O(logn)。

快速排序是一个不稳定的算法，在经过排序之后，可能会对相同值的元素的相对位置造成改变。

快速排序基本上被认为是相同数量级的所有排序算法中，平均性能最好的。