18、数据结构和算法 - 实战：快速排序算法

1.1 什么是快速排序

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

1.2 算法基本思想

快速排序需要如下三步骤完成：

1、 从数列中挑出一个元素作为基准；
2、 重新排列数列，把所有的比基准小的放在基准前面，反之放在后面（一样大可任意一边）完成后基准处在分区的中间位置；
3、 通过递归调用把小于基准元素和大雨基准元素的子序列进行排序；

1.3 快速排序复杂度分析

快速排序的空间复杂度：快速排序使用递归，递归使用栈，因此它的空间复杂度为O(logn)。

稳定性：快速排序无法保证相等的元素的相对位置不变，因此它是不稳定的排序算法

1.4 快速排序代码实现

package com.yuanxw.datastructure.chapter18;

import java.util.Arrays;

/**
 * 快速排序
 * 简称快排：时间复杂度并不固定，如果在最坏情况下（元素刚好是反向的）速度比较慢，达到 O(n^2)（和选择排序一个效率），但是如果在比较理想的情况下时间复杂度 O(nlogn)。
 * 快排也是一个分治的算法，快排算法每次选择一个元素并且将整个数组以那个元素分为两部分，
 * <p>
 * - 根据实现算法的不同，元素的选择一般有如下几种：
 * + 永远选择第一个元素永远选择最后一个元素随机选择元素取中间值整个快速排序的核心是分区（partition），
 * + 分区的目的是传入一个数组和选定的一个元素，把所有小于那个元素的其他元素放在左边，大于的放在右边。
 */
public class QuickSort {
   
     
    public static void main(String[] args) {
   
     
        int[] array = new int[]{
   
     10, -7, 8, -2, 5, -4, 6};
        System.out.println("【快速排序】前的结果：" + Arrays.toString(array));
        quickSort(array, 0, array.length - 1);
        System.out.println("【快速排序】后的结果：" + Arrays.toString(array));
    }

    /**
     * 快速排序
     *
     * @param arry  数组
     * @param left  左边索引
     * @param right 右边索引
     */
    public static void quickSort(int[] arry, int left, int right) {
   
     
        // 得到左侧索引(下标)
        int leftIndex = left;
        // 得到右侧索引(下标)
        int rightIndex = right;

        // 获得中间数
        int pivot = arry[(left + right) / 2];
        // 临时交换变量
        int temp;

        // 从两端开始比对数据大小，【left < right】表示没有全部找完就需要一直找下去
        while (leftIndex < rightIndex) {
   
     
            // 从左侧开始找，找到比pivot大的位置，每次找一次索引(下标右移一次)
            while (arry[leftIndex] < pivot) {
   
     
                leftIndex++;
            }

            // 从右侧开始找，找到比pivot小的位置，每次找一次索引(下标左移一次)
            while (arry[rightIndex] > pivot) {
   
     
                rightIndex--;
            }

            // 如果leftIndex >= rightIndex说明已经找完了
            if (leftIndex >= rightIndex) {
   
     
                break;
            }

            // 如果 左侧找到数据比右侧大，则需要进行交换
            if (arry[leftIndex] > arry[rightIndex]) {
   
     
                temp = arry[rightIndex];
                arry[rightIndex] = arry[leftIndex];
                arry[leftIndex] = temp;
            }
        }

        // 如果leftIndex == pivot，说明找到了中间数索引.
        // 需要对leftIndex加1操作，rightIndex减1操作。1.防止出现死循环。2。方便归递操作。
        if (leftIndex == rightIndex) {
   
     
            leftIndex++;
            rightIndex--;
        }
        // 向左递归
        if (left < rightIndex) {
   
     
            quickSort(arry, left, rightIndex);
        }

        // 向右递归
        if (right > leftIndex) {
   
     
            quickSort(arry, leftIndex, right);
        }
    }
}

执行结果：

【快速排序】前的结果：[10, -7, 8, -2, 5, -4, 6]
【快速排序】后的结果：[-7, -4, -2, 5, 6, 8, 10]