package cn.nwsuaf.quick;/** * 隨機產生20個數，并對其進行快速排序 * * @author 劉永浪 * */public class Quick {  /**   * 交換函數，實現數組中兩個數的交換操作   *   * @param array   *      待操作數組   * @param i   *      交換數組的第一個下標   * @param j   *      交換數組的第二個下標   */  public static void swap(int[] array, int i, int j) {    int temp = array[i];    array[i] = array[j];    array[j] = temp;  }  /**   * 分治法劃分算法   *   * @param array   *      待操作數組   * @param low   *      劃分中模塊的起始地址   * @param height   *      劃分中模塊的結束地址   * @return 基準元素的位置下標   */  public static int quick(int[] array, int low, int height) {    // 設置第一個數為基準元素    int pivot = array[low];    // 從右向左掃描，查找第1個小于pivot的元素    while (low < height) {      while (low < height && array[height] >= pivot)        height--;      // 表示找到了小于pivot的元素      if (low < height)        // 交換后low執行+1操作        swap(array, low++, height);      // 從左向右掃描，查找第1個大于pivot的元素      while (low < height && array[low] <= pivot)        low++;      // 表示找到了大于pivot的元素      if (low < height)        // 交換后heigh執行-1操作        swap(array, low, height--);    }    // 返回基準元素最終位置下標    return height;  }  /**   * 對array快速排序   *   * @param array   *      待操作數組   * @param low   *      低位   * @param height   *      高位   */  public static void sort(int[] array, int low, int height) {    // 記錄劃分后的基準元素所對應的位置    int temp;    // 僅當區間長度大于1時才須排序    if (low < height) {      // 對array做劃分      temp = quick(array, low, height);      // 對左區間遞歸排序      sort(array, low, temp - 1);      // 對右區間遞歸排序      sort(array, temp + 1, height);    }  }  public static void main(String[] args) {    int[] array = new int[20];    System.out.println("VeVb武林網測試結果:");    System.out.print("排序前序列:");    for (int i = 0; i < array.length; i++) {      // 隨機產生20個0-99的整數      array[i] = (int) (Math.random() * 100);      System.out.print(array[i] + " ");    }    System.out.print("/n排序后序列:");    sort(array, 0, array.length - 1);    for (int i = 0; i < array.length; i++)      System.out.print(array[i] + " ");  }}