[数据结构与算法]快速排序（Java）

/**
 * 快速排序——双向循环/双指针
 */
public class QuickSort03 {
    /**
     * 主程序
     */
    public static void main(String[] args) {
        int[] arr = new int[] {4, 4, 6, 5, 3, 2, 8, 1};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    private static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    /**
     * 快排 
     * @param arr           待交换的数组
     * @param startIndex    起始下标
     * @param endIndex      结束下标
     */
    private static void quickSort(int[] arr, int startIndex, int endIndex) {
        //递归终止条件
        if (startIndex >= endIndex) return;
        //得到基准元素应该待的正确下标
        int pivotIndex = partition(arr, startIndex, endIndex);
        //根据基准元素，将数组分成两部分进行递归排序
        quickSort(arr, startIndex, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, endIndex);
    }

    /**
     * 分治
     * @param arr          待交换的数组
     * @param startIndex   起始下标
     * @param endIndex     结束下标
     * @return             基准元素的正确索引
     */
    private static int partition(int[] arr, int startIndex, int endIndex) {
        //这里取第一个元素作为基准元素，但也可以随机选择
        int pivot = arr[startIndex];
        //定义左指针和右指针
        int left = startIndex; int right = endIndex;
        while (left < right) {
            while (left < right && arr[right] > pivot)  right--;
            while (left < right && arr[left] <= pivot)  left++;
            if (left < right) {
                //交换left和right所指向的元素
                exchange(arr, left, right);
            }
        }
        //让基准元素去它该去的地方，pivot和左右指针重合点交换
        arr[startIndex] = arr[left];
        arr[left] = pivot;
        return left;
    }

    /**
     * 根据所给下标，交换数组中的元素
     */
    private static void exchange(int[] nums, int i,int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}