package exp_sort;
public class QuickSort {
  public static void Qsort(int array[], int left, int right) {
    int pos;
    if (left < right) {
      pos = quickSort(array, left, right);
      //遞歸排序
      Qsort(array, left, pos - 1);
      Qsort(array, pos + 1, right);
    }
  }
  /**
   * 一趟快速排序
   *
   * @param array
   * @param left
   * @param right
   * @return
   */
  public static int quickSort(int array[], int left, int right) {
    int low, high;
    int temp = array[left]; // 選擇基準記錄（樞紐元）
    low = left;
    high = right;
    while (low < high) {
      // high從右到左找小于temp的記錄
      while (low < high && array[high] >= temp) {
        high--;
      }
      // 找到小于temp的記錄則交換
      if (low < high) {
        array[low] = array[high];
        low++;
      }
      // low從左到右找到大于temp的記錄
      while (low < high && array[low] < temp) {
        low++;
      }
      // 找到大于temp的記錄，則交換
      if (low < high) {
        array[high] = array[low];
        high--;
      }
    }
    //將游標放在當前位置，此時low=high
    array[low] = temp;
    return low;
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
    Qsort(array, 0, 7);
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("\n");
  }
}