排序算法-快速排序

算法简介

快速排序（Quick Sort）是由冒泡排序改进而来的，冒泡排序对相邻数据进行比较，快速排序则是直接对两个不相邻的数据进行交换，消除多个逆序，快速排序中一次交换可能消除多个逆序

快速排序是由 C.A.R.Hoare 在1962 年提出，大致思想就是把排序的数据分割成独立的两部分，让其中一部分所有的数据总比另一部分所有的数据小，然后再按照此方法对两部分进行分割，这个排序过程可以用递归实现

快速排序是不稳定的排序算法，时间复杂度 O(nlongn)，空间复杂度 O(1)

Java 实现

逻辑思路：

1. 最开始 left 为 0，right 为数组最后一个数的下标，并让数组中最后一个数字作为中轴

2. 从左往右找数字，在 left <= right 的前提下，找到一个比中轴大的数字时，left 光标就移到这里，并且把这个数字直接赋给 right 光标所在的位置

3. 再从右往左找数字，在 left <= right 的前提下，找到一个比中轴小的数字时，right 光标就移动到这里，并且把这个数字直接赋给 left 光标所在的位置

4. 将 2 + 3 的操作作为一个循环，循环几次 2 + 3之后，都会让 left 和 right 都移到同一位置，并将中轴赋在这个位置上，最终使得当前数组以最后一个数作为中轴时，所有比中轴小的数字都在中轴的左边，所有比中轴大的数字都在中轴的右边

5. 中轴左边的数字串用上面的方式递归

6. 中轴右边的数字串用上面的方式递归

算法图解：

下面代码相当于是把 j 所指的数代表了中轴，而不是 i 指向的数代表中轴，但是原理是一致的

代码实现：

// 快速排序
public static int[] quickSort(int[] arr, int leftIndex, int rightIndex) {
    if(leftIndex > rightIndex) {
        throw new Exception("左下标不允许比右下标大！");
    }
    int left = leftIndex;
    int right = rightIndex;
    // 我们让最后一个元素作为中轴
    int pivot = arr[right];
    // 第一层循环表示 left 向右移动到停止 + right 向左移动到停止一共经历多少轮
    while(left < right) {
        // 第二层循环表示 left 光标向右移动的次数
        while(left < right && arr[left] <= pivot) left++;
        arr[right] = arr[left];
        // 第二层循环表示 right 光标向左移动的次数
        while(left < right && pivot <= arr[right]) right--;
        arr[left] = arr[right];
        // 当 left 和 right 都指向一个元素时候
        if(left == right) {
            arr[left] = pivot;
        }
        // 中轴左边快排递归
        quickSort(arr, leftIndex, left-1);
        // 中轴右边快排递归
        quickSort(arr, right+1, rightIndex);
    }
    return arr;
}

时间复杂度

O(nlongn)

空间复杂度

O(1)

算法稳定性

一般来说快排是不稳定的排序算法