Java经典排序算法：快速排序，动图演示排序过程

 

示意动图：

 

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        new Main().test(5);
    }

    private void test(int size) {
        int[] array = new int[size];

        //随机制造size个整数装入array数组。
        makeData(array);
        //array = new int[]{3, 4, 1, 2, 0};

        //打印原始的未排序前数组数据。
        printer(array);
        System.out.println("###########");

        //对数组array排序。
        sort(array);

        //打印最终经过排序排出的结果。
        System.out.println("排序结果：");
        printer(array);
    }

    //对一个数组进行排序。数组最左边是最小值，最右边是最大值。自然升序。
    private void sort(int[] array) {
        quickSort(array, 0, array.length - 1);
    }

    private void quickSort(int[] array, int low, int high) {
        if (low > high) {
            return;
        }

        int left = low;
        int right = high;

        int key = array[left];//相当于挖坑操作，选定一个基准值
        System.out.println("key=" + key);

        while (left < right) {
            //从右往左找，寻找小于key值的下标索引。
            while ((left < right) && (array[right] >= key)) {
                right--;
            }
            System.out.println("R" + right + "=" + array[right]);

            //从左往右找，寻找大于key值的下标索引。
            while ((left < right) && (array[left] <= key)) {
                left++;
            }
            System.out.println("L" + left + "=" + array[left]);

            swap(array, left, right);//交换数组下标和达到交换数组元素，填坑。

            printer(array);
            System.out.println("-");
        }

        swap(array, low, left);

        printer(array);
        System.out.println("--");

        quickSort(array, low, left - 1);

        printer(array);
        System.out.println("---");

        quickSort(array, left + 1, high);

        printer(array);
        System.out.println("----");

        //打印每一趟排序后的结果，观察排序过程细节。
        printer(array);
        System.out.println("================");
    }

    /**
     * 交换数组中索引下标为i，j的两个元素。
     * 即把array[i]和array[j]互相交换值。
     *
     * @param array
     * @param i
     * @param j
     */
    private void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    //数组结果打印器。
    private void printer(int[] array) {
        System.out.println(Arrays.toString(array));
    }

    //随机制造样本数据。
    private void makeData(int[] array) {
        for (int i = 0; i < array.length; i++) {
            array[i] = (int) (Math.random() * 10);
        }
    }
}

 

输出：

[2, 6, 4, 8, 5]
###########
key=2
R0=2
L0=2
[2, 6, 4, 8, 5]
-
[2, 6, 4, 8, 5]
--
[2, 6, 4, 8, 5]
---
key=6
R4=5
L3=8
[2, 6, 4, 5, 8]
-
R3=5
L3=5
[2, 6, 4, 5, 8]
-
[2, 5, 4, 6, 8]
--
key=5
R2=4
L2=4
[2, 5, 4, 6, 8]
-
[2, 4, 5, 6, 8]
--
key=4
[2, 4, 5, 6, 8]
--
[2, 4, 5, 6, 8]
---
[2, 4, 5, 6, 8]
----
[2, 4, 5, 6, 8]
================
[2, 4, 5, 6, 8]
---
[2, 4, 5, 6, 8]
----
[2, 4, 5, 6, 8]
================
[2, 4, 5, 6, 8]
---
key=8
[2, 4, 5, 6, 8]
--
[2, 4, 5, 6, 8]
---
[2, 4, 5, 6, 8]
----
[2, 4, 5, 6, 8]
================
[2, 4, 5, 6, 8]
----
[2, 4, 5, 6, 8]
================
[2, 4, 5, 6, 8]
----
[2, 4, 5, 6, 8]
================
排序结果：
[2, 4, 5, 6, 8]