package quick_sort;

/**
 * @author amory
 * */

/*
 * quick_sort 快速排序
 * */

public class Quick_sort {
 /*
  * swap : 交换两个数组中的两个index的值
  * */
 
 public static void swap(int[] arr, int index_x, int index_y){
  int temp = arr[index_x];
  arr[index_x] = arr[index_y];
  arr[index_y] = temp;
 }
 
 public static void quickySort(int[] a, int start, int end){
  int p = 0;
  if(start > end) return;
  while(start <= end){
   p = partition(a,start, end);
   //System.out.println(p);
   quickySort(a,start,p-1);//n/2
   //quickySort(a,p+1,end);
   start = p+1;
  }
 }
 
 /*
  *  partition : 得到数组的分水岭
  * */
 
 public static int partition(int[] arr, int start, int end){
  int parti = 0;
  // step 1 : 赋值(数组中的两个指针来确定分水岭的位置)
  int i = start;
  int j = end;
  
  // step 2 : 从左到右得到比基数大的值，从右到zuo得到比基数小的值,默认升序
  while(i<j){
   while(arr[i] <= arr[start] && i<end){
    i++;
   }
   while(arr[j] > arr[start] && j >= start){
    j--;
   }
   if(i<j){
    swap(arr, i, j);
   }
  }
  
  swap(arr, start, j);
  parti = j;
  return parti;
 }
 
 
 
 public static void main(String[] args) {
  int[] arr = {54, 2, 65, 8, 45, 3, 0, 79};
  for(int i = 0; i<arr.length; ++i){
   System.out.print(arr[i]+" ");
  }
  quickySort(arr, 0, arr.length-1);
  System.out.println();
  for(int i = 0; i<arr.length; ++i){
   
   System.out.print(arr[i]+" ");
  }
 }
}

快速排序