분치의 빠른 정렬

분치의 기본 사상은 문제를 자문제로 나누어 점차적으로 자문제를 풀고 마지막에 조합하는 것이다.
세트 공식:

Divide 분자 문제: 기준을 선택하여 기준의 정확한 위치를 찾습니다. left<=pivot right>=pivot,

Conquer 기준은 좌우 두 개의 서브 문제를 구분하고 두 개의 서브 문제는 Quicksort, (left,pivot)(pivot+1,right)로 귀속한다

Composite: Composite

public class Sort {
  public static void quickSort(int[] arr, int left , int right){
      if(left < right) {
        int pivotNewIndex = quickSortPartition(arr, left, right, arr[left]);
        // pivotNewIndex  ， 
        //   < pivotNewIndex
        quickSort(arr, left, pivotNewIndex);
        //   >= pivotNewIndex + 1
        quickSort(arr, pivotNewIndex + 1, right);
      }
  }

  public static int quickSortPartition(int[] arr, int p, int q, int pivot){
    // j   <= pivot  
    //  ，j   pivot  ， 
    //   j  ？
    //   +1，   j   <= pivot  
    int j = p;
    for (int i = p+1; i < q; i++) {
      // swap
      if (arr[i] < pivot && i!= j) {
        j++;
        swap(arr, i, j);
      }
    }
    swap(arr, p, j);
    return j;
  }

  public static void swap(int[] arr, int index1, int index2){
    int j = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = j;
  }
}