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

谁践踏了优雅 2024-04-20 09:57 3阅读 0赞

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

示意动图：

![20190920202035373.gif][]

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]

[20190920202035373.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/373aeb36ded14783b39bf4513592a873.gif