排序算法-選擇排序技术頭條網

2020-04-02 21:48:03 醉人Ryu

選擇排序

直接選擇排序

思想：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後每次從剩餘未排序元素中繼續尋找最小（大）元素放到已排序序列的末尾。以此類推，直到所有元素均排序完畢.
時間複雜度：最壞:O(n^2) 最好: O(n^2) 平均: O(n^2)
空間複雜度：O(1)
穩定性：不穩定例如數組 2 2 1 3 第一次選擇的時候把第一個2與1交換使得兩個2的相對次序發生了改變。

<code>public static void selectSort(int[] array) {
    for (int i = 0; i < array.length; i++) {
        int minIdx = i;
        for (int j = i + 1; j < array.length; j++) {
            if (array[j] < array[minIdx]) {
                minIdx = j;
            }
        }
        exch(array, i, minIdx);
    }
}
/<code>

堆排序

思想：堆排序是利用堆的性質進行的一種選擇排序，先將排序元素構建一個最大堆,每次堆中取出最大的元素並調整堆。將該取出的最大元素放到已排好序的序列前面。這種方法相對選擇排序，時間複雜度更低，效率更高。時間複雜度：最壞:O(nlog2n) 最好: O(nlog2n) 平均: O(nlog2n)空間複雜度：O(1)穩定性：不穩定例如 5 10 15 10。如果堆頂5先輸出，則第三層的10(最後一個10)的跑到堆頂，然後堆穩定，繼續輸出堆頂，則剛才那個10跑到前面了，所以兩個10排序前後的次序發生改變。

<code>// 第一個元素沒有利用
public static void heapSort(int[] array) {
    int N = array.length -1;
    for (int k = N / 2; k >= 1; k--) { // k >= 1
        sink(array, k, N);
    }
    while (N > 1) {
        // 最大堆, 選擇最大值放在最後
        exch(array, 1, N --);
        sink(array, 1, N); 

    }
}

private static void sink(int[] array, int k, int N){
    while (2 * k <= N) {
        int j = 2 * k;
        if (j < N && array[j] < array[j+1]) { // <
            j++;
        }
        if (array[j] < array[k]) break;  // <
        exch(array, k, j);
        k = j;
    }
}
/<code>

歸併排序

思想：歸併排序採用了分治算法，首先遞歸將原始數組劃分為兩個子數組，直到數組元素個數為1，對每個子數組進行排序。然後將排好序的子數組遞歸合併成一個有序的數組。
時間複雜度：最壞:O(nlog2n) 最好: O(nlog2n) 平均: O(nlog2n)
空間複雜度：O(n)
穩定性：穩定

代碼：

<code>public static void mergeSort(int[] array) {
    sort(array, 0, array.length - 1);
}
private static void sort(int[] array, int left, int right) {
    if (left < right) {
        int middle = (left + right) >> 1;
        //遞歸處理相關的合併事項
        sort(array, left, middle);
        sort(array, middle + 1, right);
        merge(array, left, middle, right);
    }
}
private static void merge(int[] array, int lo, int mid, int hi) { 

    //創建一個臨時數組用來存儲合併後的數據
    int[] temp = new int[array.length];
    int left = lo;
    int right = mid + 1;
    int k = lo;
    while (left <= mid && right <= hi) {
        if (array[left] < array[right])
            temp[k++] = array[left++];
        else
            temp[k++] = array[right++];
    }
    //處理剩餘未合併的部分
    while (left <= mid)  temp[k++] = array[left++];
    while (right <= hi)  temp[k++] = array[right++];
    //將臨時數組中的內容存儲到原數組中
    while (lo <= hi) array[lo] = temp[lo++];
}
/<code>

基數排序算法

思想：基數排序是通過“分配”和“收集”過程來實現排序，首先根據數字的個位的數將數字放入0-9號桶中，然後將所有桶中所盛數據按照桶號由小到大，桶中由頂至底依次重新收集串起來，得到新的元素序列。然後遞歸對十位、百位這些高位採用同樣的方式分配收集，直到沒各位都完成分配收集得到一個有序的元素序列。
時間複雜度：最壞:O(d(r+n)) 最好:O(d(r+n)) 平均: O(d(r+n))