排序算法之快速排序

该方法的关键在于切分，这个过程使得数组满足下面三个条件：

对于某个 j，a[j] 已经排定；
a[lo] 到 a[j-1] 中的所有元素都不大于 a[j]；
a[j+1] 到 a[hi] 中的所有元素都不小于 a[j]。

package algorithm_01;

import java.util.Arrays;
import java.util.Random;


public class QuickSort {
    static int count = 0;

    public static void main(String[] args) {
        int[] arr = new int[20];
        Random rd = new Random();
        for (int i = 0; i < arr.length; i++) {
            int val = rd.nextInt(100);
            arr[i] = val;
        }
        System.out.println(Arrays.toString(arr));
        sort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    private static void sort(int[] a, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int j = partition(a, lo, hi);
        sort(a, lo, j - 1);
        sort(a, j + 1, hi);
    }

    private static int partition(int[] a, int lo, int hi) {
        int i = lo;//左右扫描指针
        int j = hi + 1;
        int v = a[lo]; //切分元素
        while (true) {
            // 扫描左右，检查扫描是否结束并交换元素
            while (a[++i] < v) {
                if (i == hi) {
                    break;
                }
            }
            while (a[--j] > v) {
                if (j == lo) {
                    break;
                }
            }
            if (i >= j) {
                break;
            }
            swap(a, i, j);
        }
        System.out.println(j);
        swap(a, lo, j);
        return j;
    }

    private static void swap(int[] a, int i, int j) {
        System.out.println("第" + (count++) + "轮：");
        int temp = a[j];
        a[j] = a[i];
        a[i] = temp;
        System.out.println(Arrays.toString(a));
    }
}

另一种写法:

package algorithm_01;

import java.util.Arrays;
import java.util.Random;

public class QuickSort2 {
    static int count=0;
    public static void main(String[] args) {
        int[] arr = new int[20];
        Random rd = new Random();
        for (int i = 0; i < arr.length; i++) {
            int val = rd.nextInt(100);
            arr[i] = val;
        }
        System.out.println(Arrays.toString(arr));
        sort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    private static void sort(int[] a, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int j = partition(a, lo, hi);
        sort(a, lo, j - 1);
        sort(a, j + 1, hi);
    }

    private static int partition(int[] a, int lo, int hi) {
        int pivot=lo;
        int index=pivot+1;
        for(int i=index;i<=hi;i++){
            if (a[i]