快速排序——实现代码

package com.test.sort;

import lombok.extern.slf4j.Slf4j;
import org.springframework.util.StopWatch;

import java.util.Random;

@Slf4j
public class QuickSort {

    public static void main(String[] args) {
        int count = 10000000;
        Random random = new Random();
        int[] nums = new int[count];
        for (int i = 0; i < count; i++) {
            nums[i] = random.nextInt(999);
        }
        log.info("数组初始化中...");
        printArray(nums);

        StopWatch watch = new StopWatch();
        watch.start();

        log.info("数组开始排序...");
        sort(nums, 0, nums.length - 1);
        watch.stop();
        log.info("数组排序结果...");
        printArray(nums);

        log.info("排序耗时：{} 毫秒！", watch.getTotalTimeMillis());
    }

    private static void sort(int[] nums, int start, int end) {
        if (start > end) {
            return;
        }
        int temp = nums[start];
        int i = start;
        int j = end;

        // 保证从两头开始遍历，遍历完整个数组区间
        while (i < j) {
            // 从右往左，一直堵到比基准值小的数n1
            while (temp < nums[j] && i < j) {
                j --;
            }
            // 从左往右，一直堵到比基准值大的数n2
            while (temp >= nums[i] && i < j) {
                i ++;
            }
            // 交换n1和n2
            if (i < j) {
                int t = nums[j];
                nums[j] = nums[i];
                nums[i] = t;
            }
        }
        // 复位初始位置
        nums[start] = nums[i];
        nums[i] = temp;
        // 左右两边的数组各自排序
        sort(nums, start, j - 1);
        sort(nums, j + 1, end);
    }

    private static void printArray(int[] nums) {
        log.info("执行 - printArray 方法...");
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < nums.length; i++) {
            builder.append(nums[i]);
            if (i != nums.length - 1) {
                builder.append(", ");
            }
        }
        log.info("结果：{}", builder.toString());
    }

}