题解 | JAVA QuickSort#排序# [P0]

时间O(NlogN)
空间 avg O(logN), worst O(N), 栈高

import java.util.*;

public class Solution {
    public int[] MySort (int[] arr) {
      quickSort(0, arr.length-1, arr);
      return arr;
    }
  
    void quickSort(int start, int end, int[] arr) {
      if (start < end) {
        int pivot = partition(start, end, arr);
        quickSort(start, pivot-1, arr);
        quickSort(pivot+1, end, arr);
      }
    }
  
    int partition(int start, int end, int[] arr) {
      int pV = arr[start];
      int i = start, j = end;
      while (i < j) {
        while (i < end && arr[i] <= pV) i++;
        while (j > start && arr[j] >= pV) j--;
        if (i < j) swap(i, j, arr);
      }
      swap(start, j, arr);
      return j;
    }
  
    void swap(int i, int j, int[] arr) {
      int tmp = arr[i];
      arr[i] = arr[j];
      arr[j] = tmp;
    }
}