quickSort.java

package com.company;

public class QuickSort {
    public void quickSort(int[] nums) {
        sort(nums, 0, nums.length - 1);
    }

    public void sort(int[] nums, int left, int right) {
        int pivotIndex;

        if (left < right) {
            pivotIndex = partition(nums, left, right);

            sort(nums, left, pivotIndex - 1);
            sort(nums, pivotIndex + 1, right);
        }
    }

    public int partition(int[] nums, int left, int right) {
        // 第一个元素作为枢轴
        int pivot = nums[left];

        // 退出循环时有 left == right
        while (left < right) {
            while (left < right && nums[right] >= pivot) {
                // 右指针遇到第一个小于 pivot 的值时停下
                right--;
            }
            if (left < right) {
                // 将右指针找到的小于 pivot 的值放到左空位，此时形成新的右空位
                nums[left] = nums[right];
                // 左空位上的元素位置确定则往右前进
                left++;
            }

            while (left < right && nums[left] <= pivot) {
                // 左指针遇到第一个大于 pivot 的值时停下
                left++;
            }
            if (left < right) {
                // 将左指针找到的大于 pivot 的值放到右空位，此时形成新的左空位
                nums[right] = nums[left];
                // 右空位上的元素位置确定则往左前进
                right--;
            }

        }

        // 退出循环时有 left == right，将 pivot 放在中间。
        nums[left] = pivot;

        return left;
    }
}