算法——初级排序算法之快速排序

介绍

快速排序可以说是应用最广泛的排序算法了，主要是因为实现简单、适用于各种不同的输入数据且在一般应用中比其他排序算法都要快得多。

快速排序是一种基于分治思想的排序算法。它将一个数组分成两个子数组，将两部分独立地排序。

原理

• 设置两个变量 low、high，排序开始时：low=0，high=size-1。

• 整个数组找基准正确位置，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面

特点

优点：原地排序(只需要一个很小的辅助栈)，且将长度为N的数组排序所需的时间和NlgN成正比

缺点：非常脆弱，实践中需要非常小心才能避免低劣的性能

代码

package algorithm.sort;

import javax.crypto.interfaces.PBEKey;
import java.util.Arrays;
import java.util.Random;
import java.util.stream.Stream;

/**
 * 描述：快速排序
 * Created by zjw on 2021/7/4 15:38
 */
public class QuickSort {

    public static void main(String[] args) {
        Integer[] arr = Stream.generate(() -> new Random().nextInt(12))
                .limit(10).toArray(Integer[]::new);

        System.out.println("排序前 " + Arrays.toString(arr));
        sort(arr);
        System.out.println("排序后 " + Arrays.toString(arr));
    }

    public static void sort(Comparable[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    /**
     * 该方法使得数组满足下面三个条件
     * - 对于某个j, a[j]已经排定
     * - a[lo]到a[j-1]中的所有元素都不大于a[j]
     * - a[j+1]到a[hi]中的所有元素都不小于a[j]
     *
     * @param a
     * @param lo
     * @param hi
     */
    public static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) return;
        // if (hi <= lo + 10) { insertionSort(a, lo, hi);return; }
        int j = partition(a, lo, hi);// 切分
        sort(a, lo, j - 1); // 排序左边
        sort(a, j + 1, hi); // 排序右边
        // Quick3waySort(a, lo, hi);
    }

    /**
     * 切分
     *
     * @param a
     * @param lo
     * @param hi
     * @return
     */
    private static int partition(Comparable[] a, int lo, int hi) {
        // 将数组切分为a[lo..i-1]，a[i]，a[i+1..hi]
        int i = lo, j = hi + 1; // 左右指针
        Comparable v = a[lo]; // 切分元素
        while (true) {
            //检查左右是否结束并交换元素
            while (less(a[++i], v)) if (i == hi) break;
            while (less(v, a[--j])) if (j == lo) break;
            if (i >= j) break;
            exchange(a, i, j);
        }
        exchange(a, lo, j);// 将v = a[j]放入正确的位置
        return j;//a[lo..j-1]<=a[j]<=a[j+1..hi]达成
    }

    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    private static void exchange(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    /**
     * @param a
     * @param lo
     * @param hi
     */
    public static void insertionSort(Comparable[] a, int lo, int hi) {
        int N = a.length;
        for (int i = 0; i < N; i++) {
            // 将 a[i] 插入到 a[i-1]、a[i-2]、a[i-3]...之中
            for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
                exchange(a, j, j - 1);
            }
        }
    }

    /**
     * 三取样切分
     * @param a
     * @param lo
     * @param hi
     */
    public static void Quick3waySort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) return;
        int lt = lo, i = lo + 1, gt = hi;
        Comparable v = a[lo];
        while (i <= gt) {
            int cmp = a[i].compareTo(v);
            if (cmp < 0) exchange(a, lt++, i++);
            else if (cmp > 0) exchange(a, i, gt--);
            else i++;
        }
        // //a[lo..lt-1] < v=a[lt..gt] < a[gt+1..hi]成立
        sort(a, lo, lt - 1);
        sort(a, gt + 1, hi);
    }
}

改进

• 小数组使用插入排序
  • 对于小数组，快速排序比插入排序慢；
  • 因为递归，快速排序的sort()方法在小数组中也会调用自己；
  • 将sort()中的语句if(hi <= lo) return;替换成if(hi <= lo + M){Insertion.sort(a, lo, hi);return;}小数组使用插入排序
  • 转换参数M的最佳值是和系统相关的，但是通常5~15之间的任意值在大多数情况下才能令人满意
• 三取样切分
  • 使用小数组的一部分元素的中位数来切分数组，代价是需要计算中位数

Donate