关键点：

    • 对于长度小于 7 的数组使用插入排序效率更高。
    • 分治的时候使用的是开区间。
    1. public class QuickSort {
    3.     private static final int THRESHOLD = 7;
    4.     private static final Random RANDOM = new Random();
    6.     public static void sort(int[] nums) {
    7.         int len = nums.length;
    8.         quickSort(nums, 0, len - 1);
    9.     }
    11.     private static void quickSort(int[] nums, int left, int right) {
    12.         if (right - left + 1 <= THRESHOLD) {
    13.             selectionSort(nums, left, right);
    14.             return;
    15.         }
    16.         if (left >= right) {
    17.             return;
    18.         }
    20.         int p = partition(nums, left, right);
    21.         quickSort(nums, left, p - 1);
    22.         quickSort(nums, p + 1, right);
    23.     }
    25.     private static int partition(int[] nums, int left, int right) {
    26.         int rand = RANDOM.nextInt(right - left + 1) + left;
    27.         swap(nums, left, rand);
    28.         int lt = left;
    29.         int pivot = nums[left];
    31.         for (int i = left + 1; i <= right; i++) {
    32.             if (nums[i] < pivot) {
    33.                 lt++;
    34.                 swap(nums, lt, i);
    35.             }
    36.         }
    38.         swap(nums, left, lt);
    39.         return lt;
    40.     }
    42.     private static void swap(int[] nums, int i, int j) {
    43.         int temp = nums[i];
    44.         nums[i] = nums[j];
    45.         nums[j] = temp;
    46.     }
    48.     private static void selectionSort(int[] nums, int left, int right) {
    49.         if (left >= right) {
    50.             return;
    51.         }
    53.         for (int i = left + 1; i <= right; i++) {
    54.             int temp = nums[i];
    55.             int j = i;
    56.             while (j > left && nums[j - 1] > temp) {
    57.                 nums[j] = nums[j - 1];
    58.                 j--;
    59.             }
    60.             nums[j] = temp;
    61.         }
    62.     }
    63. }