题解 | #NC140 排序 快速排序#

import java.util.*;

public class Solution {
    public int[] MySort (int[] arr) {
        // 预处理
        if (arr == null || arr.length == 0) return arr;

        // 对数组进行快速排序
        quickSort(arr, 0, arr.length-1);
        return arr;
    }

    // 快速排序
    public static void quickSort(int[] arr, int start, int end) {
        // 预处理
        if (start >= end) return;

        // 划分
        int pivotPos = partition(arr, start, end);
        // 递归处理左右子数组
        quickSort(arr, start, pivotPos-1); // 划分左子数组
        quickSort(arr, pivotPos+1, end);   // 划分右子数组
    }

    // 用首元素将序列划分成左右两个部分
    public static int partition(int[] arr, int start, int end) {
        // 取首元素作为中枢
        int pivot = arr[start];
        // 确定中枢的最终位置
        while (start < end) {
            // 小于中枢的移动到左侧
            while (start < end && arr[end] >= pivot) end--;
            arr[start] = arr[end];
            // 大于中枢的移动到右侧
            while (start < end && arr[start] <= pivot) start++;
            arr[end] = arr[start];
        }
        // 循环结束，此时start == end，此位置即为中枢的最终位置
        arr[start] = pivot;
        // 返回中枢的最终位置
        return start;
    }
}