java快速排序算法

/**


快速排序
*
在當前無序區R[1..H]中任取一個數據元素作為比較的"基準"(不妨記為X)，用此基準將當前無序區劃分為左右兩個較小的無序區：
R[1..I-1]和R[I+1..H]，且左邊的無序子區中數據元素均小于等于基準元素，右邊的無序子區中數據元素均大于等于基準元素，
而基準X則位于最終排序的位置上，即R[1..I-1]≤ X.Key≤RI+1..H，當R[1..I-1]和R[I+1..H]均非空時，
分別對它們進行上述的劃分過程，直至所有無序子區中的數據元素均已排序為止。
*/

public class QuickSort {

/**
 * 排序算法的實現，對數組中指定的元素進行排序
 *
 * @param array
 *            待排序的數組
 * @param from
 *            從哪里開始排序
 * @param end
 *            排到哪里
 * @param c
 *            比較器
 */
// 定義了一個這樣的公有方法sort，在這個方法體里面執行私有方法quckSort（這種方式值得借鑒）。
public void sort(Integer[] array, int from, int end) {
    quickSort(array, from, end);
}

/**
 * 遞歸快速排序實現
 *
 * @param array
 *            待排序數組
 * @param low
 *            低指針
 * @param high
 *            高指針
 * @param c
 *            比較器
 */
private void quickSort(Integer[] array, int low, int high) {
    /*
     * 如果分區中的低指針小于高指針時循環；如果low=higth說明數組只有一個元素，無需再處理； 如果low >
     * higth，則說明上次樞紐元素的位置pivot就是low或者是higth，此種情況 下分區不存，也不需處理
     */
    if (low < high) {
        // 對分區進行排序整理

        // int pivot = partition1(array, low, high);
        int pivot = partition2(array, low, high);
        // int pivot = partition3(array, low, high);

        /*
         * 以pivot為邊界，把數組分成三部分[low, pivot - 1]、[pivot]、[pivot + 1, high]
         * 其中[pivot]為樞紐元素，不需處理，再對[low, pivot - 1]與[pivot + 1, high]
         * 各自進行分區排序整理與進一步分區
         */
        quickSort(array, low, pivot - 1);
        quickSort(array, pivot + 1, high);
    }

}

/**
 * 實現一
 *
 * @param array
 *            待排序數組
 * @param low
 *            低指針
 * @param high
 *            高指針
 * @param c
 *            比較器
 * @return int 調整后中樞位置
 */
private int partition1(Integer[] array, int low, int high) {
    Integer pivotElem = array[low];// 以第一個元素為中樞元素
    // 從前向后依次指向比中樞元素小的元素，剛開始時指向中樞，也是小于與大小中樞的元素的分界點
    int border = low;

    /*
     * 在中樞元素后面的元素中查找小于中樞元素的所有元素，并依次從第二個位置從前往后存放
     * 注，這里最好使用i來移動，如果直接移動low的話，最后不知道數組的邊界了，但后面需要 知道數組的邊界
     */
    for (int i = low + 1; i <= high; i++) {
        // 如果找到一個比中樞元素小的元素
        if ((array[i].compareTo(pivotElem)) < 0) {
            swap(array, ++border, i);// border前移，表示有小于中樞元素的元素
        }
    }
    /*
     * 如果border沒有移動時說明說明后面的元素都比中樞元素要大，border與low相等，此時是
     * 同一位置交換，是否交換都沒關系；當border移到了high時說明所有元素都小于中樞元素，此
     * 時將中樞元素與最后一個元素交換即可，即low與high進行交換，大的中樞元素移到了 序列最 后；如果 low <minIndex<
     * high，表 明中樞后面的元素前部分小于中樞元素，而后部分大于
     * 中樞元素，此時中樞元素與前部分數組中最后一個小于它的元素交換位置，使得中樞元素放置在 正確的位置
     */
    swap(array, border, low);
    return border;
}

/**
 * 實現二
 *
 * @param array
 *            待排序數組
 * @param low
 *            待排序區低指針
 * @param high
 *            待排序區高指針
 * @param c
 *            比較器
 * @return int 調整后中樞位置
 */
private int partition2(Integer[] array, int low, int high) {
    int pivot = low;// 中樞元素位置，我們以第一個元素為中樞元素
    // 退出條件這里只可能是 low = high
    while (true) {
        if (pivot != high) {// 如果中樞元素在低指針位置時，我們移動高指針
            // 如果高指針元素小于中樞元素時，則與中樞元素交換
            if ((array[high].compareTo(array[pivot])) < 0) {
                swap(array, high, pivot);
                // 交換后中樞元素在高指針位置了
                pivot = high;
            } else {// 如果未找到小于中樞元素，則高指針前移繼續找
                high--;
            }
        } else {// 否則中樞元素在高指針位置
            // 如果低指針元素大于中樞元素時，則與中樞元素交換
            if ((array[low].compareTo(array[pivot])) > 0) {
                swap(array, low, pivot);
                // 交換后中樞元素在低指針位置了
                pivot = low;
            } else {// 如果未找到大于中樞元素，則低指針后移繼續找
                low++;
            }
        }
        if (low == high) {
            break;
        }
    }
    // 返回中樞元素所在位置，以便下次分區
    return pivot;
}

/**
 * 實現三
 *
 * @param array
 *            待排序數組
 * @param low
 *            待排序區低指針
 * @param high
 *            待排序區高指針
 * @param c
 *            比較器
 * @return int 調整后中樞位置
 */
private int partition3(Integer[] array, int low, int high) {
    int pivot = low;// 中樞元素位置，我們以第一個元素為中樞元素
    low++;
    // ----調整高低指針所指向的元素順序，把小于中樞元素的移到前部分，大于中樞元素的移到后面部分
    // 退出條件這里只可能是 low = high

    while (true) {
        // 如果高指針未超出低指針
        while (low < high) {
            // 如果低指針指向的元素大于或等于中樞元素時表示找到了，退出，注：等于時也要后移
            if ((array[low].compareTo(array[pivot])) >= 0) {
                break;
            } else {// 如果低指針指向的元素小于中樞元素時繼續找
                low++;
            }
        }

        while (high > low) {
            // 如果高指針指向的元素小于中樞元素時表示找到，退出
            if ((array[high].compareTo(array[pivot])) < 0) {
                break;
            } else {// 如果高指針指向的元素大于中樞元素時繼續找
                high--;
            }
        }
        // 退出上面循環時 low = high
        if (low == high) {
            break;
        }

        swap(array, low, high);
    }

    // ----高低指針所指向的元素排序完成后，還得要把中樞元素放到適當的位置
    if ((array[pivot].compareTo(array[low])) > 0) {
        // 如果退出循環時中樞元素大于了低指針或高指針元素時，中樞元素需與low元素交換
        swap(array, low, pivot);
        pivot = low;
    } else if ((array[pivot].compareTo(array[low])) <= 0) {
        swap(array, low - 1, pivot);
        pivot = low - 1;
    }

    // 返回中樞元素所在位置，以便下次分區
    return pivot;
}

/**
 * 交換數組中的兩個元素的位置
 *
 * @param array
 *            待交換的數組
 * @param i
 *            第一個元素
 * @param j
 *            第二個元素
 */
public void swap(Integer[] array, int i, int j) {
    if (i != j) {// 只有不是同一位置時才需交換
        Integer tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}

/**
 * 測試
 *
 * @param args
 */
public static void main(String[] args) {
    Integer[] intgArr = { 5, 9, 1, 4, 2, 6, 3, 8, 0, 7 };
    QuickSort quicksort = new QuickSort();
    quicksort.sort(intgArr, 0, intgArr.length - 1);
    for (Integer intObj : intgArr) {
        System.out.print(intObj + " ");
    }
}

}</pre>