資料結構與算法（27）——排序（二）

希爾排序(Shell Sort)又稱為縮小增量排序(diminishing increment sort)
該算法是一種泛化的插入排序。
希爾排序也稱為n間距(n-gap)插入排序。希爾排序分多路并使用不同的間距來比較元素，通過逐漸減少間距，最終以1為間距進行排序。
           

public static void shellSort(int[] array) {
    // 先擷取數組元素的個數
    int length = array.length;
    // 數組元素
    int temp;
    // 内循環的循環變量，在外部聲明，避免重複建立
    int i, j;

    // 控制增量序列
    for (int gap = length / ; gap > ; gap /= ) {
        // 在固定的增量序列下分組比較數組元素
        for (i = gap; i < length; i++) {
            temp = array[i];
            j = i;
            // 資料交換，此處的while循環是為了處理gap=1的情況
            while ((j >= gap) && (array[j - gap] > temp)) {
                array[j] = array[j - gap];
                j -= gap;
            }
            array[j] = temp;
        }
    }
}
           

歸并排序(Merge Sort)
參考：http://blog.csdn.net/yinjiabin/article/details/8265827/
           

public static void mergeSort(int[] array, int left, int right) {
    if (right > left) {
        int mid = (left + right) / ;
        mergeSort(array, left, mid);
        mergeSort(array, mid + , right);
        merge(array, left, mid + , right);
    }
}

/**
 * 合并資料塊
 * @param array 原始數組
 * @param left 資料塊的起始位置
 * @param mid 資料塊的中間位置
 * @param right 資料塊的最後位置
 */
public static void merge(int[] array, int left, int mid, int right) {
    // 左側資料塊的結束位置
    int left_end = mid - ;
    // 左右兩側資料塊元素的個數
    int size = right - left + ;
    // 臨時數組用來存儲排好序的資料
    int[] temp = new int[array.length];
    // 臨時數組的下标
    int temp_pos = left;

    // 確定資料在合法的資料塊範圍内
    while ((left <= left_end) && (mid <= right)) {
        if (array[left] <= array[mid]) {
            temp[temp_pos] = array[left];
            temp_pos++;
            left++;
        } else {
            temp[temp_pos] = array[mid];
            temp_pos++;
            mid++;
        }
    }

    // 處理左側的資料塊
    while (left <= left_end) {
        temp[temp_pos] = array[left];
        temp_pos++;
        left++;
    }

    // 處理右側的資料塊
    while (mid <= right) {
        temp[temp_pos] = array[mid];
        temp_pos++;
        mid++;
    }

    // 将臨時數組中的元素指派給原數組
    for (int i = ; i < size; i++) {
        array[right] = temp[right];
        right--;
    }
}
           

快速排序(Quick Sort)也稱為分區交換排序
思路：
1.如果數組中隻有一個元素或者沒有資料需要排序則直接傳回
2.選擇數組中的一個元素作為中心點(pivot)，通常選擇數組最右側的元素
3.把數組分為兩部分，一部分是元素大于中心點，一部分是元素小于中心點
4.遞歸處理兩部分數組
           

public static void quickSort(int[] array, int low, int high) {
    if (high > low) {
        int pivot = partition(array, low, high);
        quickSort(array, low, pivot - );
        quickSort(array, pivot + , high);
    }
}

/**
 * 查找中心點位置，并根據中心點分組
 * @param array 原始數組
 * @param low 數組的起始位置
 * @param high 數組的結束位置
 * @return 中心點位置
 */
public static int partition(int[] array, int low, int high) {
    // 預設選取數組最左邊元素為中心點
    int pivot_item = array[low];
    // 數組的起始位置
    int left = low;
    // 數組的結束為止
    int right = high;

    while (left < right) {
        // 從數組左側開始找大于中心點的位置
        while (left <= high && (array[left] <= pivot_item)) {
            left++;
        }
        // 從數組右側開始找小于中心點的位置
        while (right >= low && (array[right] > pivot_item)) {
            right--;
        }
        // 交換左側找到的大于中心點值和右側找到的小于中心點值
        if (left < right) {
            int temp = array[left];
            array[left] = array[right];
            array[right] = temp;
        }
    }
    // rught就是中心點的最終位置
    array[low] = array[right];
    array[right] = pivot_item;
    return right;
}