穩(wěn)定性：指的是排序的過程中是否會改變多個相同的值的相對次序，如果會改變則是不穩(wěn)定的。

1、冒泡排序/選擇排序/插入排序

冒泡排序，選擇排序，插入排序是最簡單的排序方法。

冒泡排序(Bubble Sort)

排序方法：掃描的過程中，比較相鄰兩個數(shù)的大小關系，如果存在逆序就交換這兩個數(shù)，這樣每趟可以保證最后一個數(shù)，也就是最大的數(shù)，一步步交換上去，如氣泡上浮一樣，回歸到正確的位置。

時間復雜度：$O(n^2)$

穩(wěn)定性：穩(wěn)定。對于兩個相同的值，不會發(fā)生交換。

代碼實現(xiàn)：文章來源地址http://www.zghlxwxcb.cn/news/detail-638668.html

int arr[] = {0, 2, 9, 3, 5, 7, 8, 1, 4, 6};

//arr是被排序數(shù)組，start是起點坐標，end是終點坐標（閉區(qū)間）

void sort(int* arr, int start, int end) {
    int n = end - start + 1;
    //只需要排序n - 1次
    for (int i = 1; i < n; i++) {
        //倒數(shù)i - 1個數(shù)已經(jīng)歸位不必交換
        for (int j = start; j <= end - i; j++) {
            //出現(xiàn)逆序
            if (arr[j + 1] < arr[j]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}

選擇排序(Selection Sort)

排序方法：掃描的過程中，每次選擇剩余未排序的數(shù)組中選擇最小值與未排序部分第一個值進行交換，從而使得未排序部分的第一個位置得到正確的值。

時間復雜度：$O(n^2)$

穩(wěn)定性：不穩(wěn)定。例如，3 3 2 $\stackrel{一次交換}{\to }$ 2 3 3 可以發(fā)現(xiàn)兩個3的位置改變了。

代碼實現(xiàn)：

int arr[] = {0, 2, 9, 3, 5, 7, 8, 1, 4, 6};

//arr是被排序數(shù)組，start是起點坐標，end是終點坐標（閉區(qū)間）

void sort(int* arr, int start, int end) {
    int n = end - start + 1;
    //只需要排序n - 1次
    for (int i = 1; i < n; i++) {
        int min_element_positon = start + i - 1;
        for (int j = start + i - 1; j <= end; j++) {
            if (arr[j] < arr[min_element_positon]) {
                min_element_positon = j;
            }
        }
        int tmp = arr[min_element_positon];
        arr[min_element_positon] = arr[start + i - 1];
        arr[start + i - 1] = tmp;
    }
}

插入排序(Insertion Sort)

排序方法：每次取未排序部分的數(shù)組，將其插入到前半已經(jīng)排序后的數(shù)組內(nèi)，類似打牌時整理牌序的方法，插入到前面整理好的數(shù)組內(nèi)的合適的位置。

時間復雜度：$O(n^2)$

穩(wěn)定性：穩(wěn)定。相同的值符合大于等于關系，并不會插入到相同值的前面。

代碼實現(xiàn)：

int arr[] = {0, 2, 9, 3, 5, 7, 8, 1, 4, 6};

//arr是被排序數(shù)組，start是起點坐標，end是終點坐標（閉區(qū)間）

void sort(int* arr, int start, int end) {
    int n = end - start + 1;
    //只需要排序n - 1次
    for (int i = 1; i < n; i++) {
        int key = arr[start + i];
        int j = start + i;
        while (j >= start) {
            if (j == start) break; // 如果是最小值，會一直到開頭
            if (j == start + i && key >= arr[j - 1]) break; //如果是最大值
            if (key >= arr[j - 1] && key <= arr[j + 1]) break;//在中間合適的值
            arr[j] = arr[j - 1];
            j--;
        }
        arr[j] = key;
    }
}

2、希爾排序(Shell’s Sort)

排序方法：每次選擇特定的增量，對這個增量下的子序列進行直接插入排序。

最好時間復雜度：$O(n\log n)$

最壞時間復雜度：$O(n\sqrt{n})$【選取d={1, 2, 4, 8, …2^{k}大到小】，$O(n\log{n}\log{n})$【選取2}m*2^n次大到小的集合】

關于時間復雜度的證明：主要考慮對于兩個不同增量的序列的插入排序，兩者的結(jié)果都是可以互相繼承的；以及相關其他復雜度的 分析

穩(wěn)定性：不穩(wěn)定，因為不同序列相同的值的位置可能改變。

代碼實現(xiàn)：

int arr[] = {0, 2, 9, 55, 54, 7, 8, 1, 40, 600};

void sort(int* arr, int start, int end) {
    int n = end - start + 1;
    for (int d = n / 2; d >= 1; d /= 2) {
        //倍減
        for (int i = d; i < n; i++) {//一共進行n - d次插入
            int tmp = arr[start + i];//取無序部分第一個數(shù)進行插排
            int j = i - d;
            for (; j >= 0 && tmp < arr[j + start]; j -= d) {
                arr[j + d + start] = arr[j + start];
            }
            //如果前面有比最后一個數(shù)小的，就騰出一位
            //實際上會多減一次，要補回d
            arr[j + d + start] = tmp;
            
        }
    }
}

3、快速排序(Quick Sort)

排序方法：“挖坑填數(shù)”，取出需要排序區(qū)間的第一個數(shù)作為基數(shù)，利用雙指針方法，整理當前數(shù)組，使得這個數(shù)組成為坑左邊均為小于等于基數(shù)的數(shù)，坑右邊都是大于等于基數(shù)的數(shù)，最后把基數(shù)填入這個位置，此處基數(shù)回到正確的位置。然后分成兩個區(qū)間，遞歸分治，重復上述操作。

一般時間復雜度：$O(n\log (n))$

最壞時間復雜度（例如數(shù)組已經(jīng)有序的時候）：$O(n^2)$

穩(wěn)定性：不穩(wěn)定。例如 6 3 3 經(jīng)過一次的填坑得到 3 3 _ 3的次序發(fā)生了改變。

代碼實現(xiàn)：

int arr[] = {0, 2, 9, 3, 5, 7, 8, 1, 4, 6};

//arr是被排序數(shù)組，start是起點坐標，end是終點坐標（閉區(qū)間）

void sort(int* arr, int start, int end) {
    if (start >= end) { //如果只有1個元素，或者沒有元素就不需要排序
        return;
    }//目的是把數(shù)組整理成一半小于等于基數(shù)，一半大于等于基數(shù)，中間是坑位的樣子
    int l = start, r = end, key = arr[l];//取第一個元素作為基數(shù)
    while (l < r) {
        while (l < r && arr[r] >= key) {
            r--;//從后往前找到第一個小于key的值
        }
        if (l < r) {//如果相遇則說坑位左右兩側(cè)都已經(jīng)整理完畢
            arr[l++] = arr[r];
        }
        while (l < r && arr[l] <= key) {
            l++;//從前往后找到第一個大于key的值
        }
        if (l < r) {
            arr[r--] = arr[l];
        }
    }
    arr[l] = key;
    sort(arr, start, l - 1);
    sort(arr, l + 1, end);
}

4、堆排序(Heap Sort)

排序方法：利用標號關系構(gòu)造一個無序堆，通過堆調(diào)整，形成一個有序的大頂堆。每次取堆頂?shù)臄?shù)和未排序數(shù)的最大標號，即堆底最后一個葉子交換位置，此時，最后一個葉子是當前未排序的數(shù)中最大的數(shù)，已經(jīng)回到正確的位置，離開堆。之后，調(diào)整堆，維護大頂堆的性質(zhì)，等待下一次交換。

關于堆調(diào)整：如果父節(jié)點最大不交換，如果父節(jié)點不是最大，則要交換左右兒子中較大的一個，交換后，可以使得原來那個較小兒子所在的子樹的父節(jié)點變成較大兒子，這樣保證較小兒子的子樹符合二叉堆的性質(zhì)，并且根節(jié)點也符合條件，但是，可能會影響較另外子數(shù)成堆，所以，為了維護堆的性質(zhì)，要一直交換下去，直到符合性質(zhì)，最壞可能要交換到葉子，但是這樣的交換不超過$\log n$次，因為每次交換都可以使得近似大小的另一子樹符合堆的性質(zhì)，需要維護的堆的性質(zhì)的節(jié)點數(shù)倍減，直至單個節(jié)點，單個節(jié)點符合堆的性質(zhì)。

時間復雜度：$O(n\log n)$

時間復雜度分析：開始的堆調(diào)整$n$次，之后每個數(shù)取出后的堆調(diào)整的交換次數(shù)取決于二叉堆的深度，由于二叉堆是一個完全二叉樹，所以深度不超過$\log n$所以一趟的交換次數(shù)不超過$\log n$次。

穩(wěn)定性：不穩(wěn)定。如果是全相等的堆，仍然會進行交換。

代碼實現(xiàn)：

int arr[] = {0, 2, 9, 3, 5, 7, 8, 1, 4, 6};

//arr是被排序數(shù)組，start是起點坐標，end是終點坐標（閉區(qū)間）
//堆調(diào)整函數(shù)，維護當前子樹堆的性質(zhì)
void heap_modify(int* arr, int root_id, int last_id, int start) {
    int tmp = arr[root_id + start];
    for (int i = 2 * root_id + 1; i <= last_id; i = i * 2 + 1) {
        //枚舉左兒子
        if (i < last_id && arr[i + start] < arr[i + 1 + start]) {
            //如果有右兒子，并且右兒子更大，取右兒子進行比較
            //否則取左兒子
            i++;
        }
        //較大的兒子和根節(jié)點進行比較，都是和原來根節(jié)點交換的數(shù)進行比較
        if (arr[i + start] > tmp) {
            arr[root_id + start] = arr[i + start];
            root_id = i;//較大的兒子的id是根節(jié)點的下一個id
        }
        else {//如果較大的兒子不大于根節(jié)點，不必調(diào)整下去
            break;
        }
    }
    arr[root_id + start] = tmp;//填坑
}
void sort(int* arr, int start, int end) {
    //構(gòu)造有序堆
    for (int i = end; i >= start; i--) {
        //映射成0~n的標號,倒著整理
        heap_modify(arr, i - start, end - start, start);
    }
    int n = end - start + 1;
    for (int i = 1; i < n; i++) {//n - 1趟
        int tmp = arr[start];
        arr[start] = arr[end - i + 1];//與當前無序數(shù)組最大下標交換
        arr[end - i + 1] = tmp;
        heap_modify(arr, 0, end - i - start, start);//維護堆的性質(zhì)
    }
}

5、歸并排序(Merge Sort)

排序方法：利用分治的思想，將數(shù)組不斷劃分，到單個數(shù)，然后遞歸合并起來，利用雙指針的手法，將兩個有序數(shù)組合并成一個有序的數(shù)組。

時間復雜度：$O(n\log n)$

穩(wěn)定性：穩(wěn)定，合并的數(shù)組的時候，如果兩個值相同的話會按照原先的順序依次放入到臨時數(shù)組當中。

代碼實現(xiàn)：

int arr[] = {0, 2, 9, 55, 54, 7, 8, 1, 40, 600};
int tmp[1000];
void merge_arr(int* arr, int* tmp, int start, int end, int mid) {
    int i = start, j = mid + 1, p = 0;
    //要保證歸并排序的穩(wěn)定性，<=的時候優(yōu)先取左側(cè)
    while (i <= mid && j <= end) {
        if (arr[i] <= arr[j]) {
            tmp[p++] = arr[i++];
        } else {
            tmp[p++] = arr[j++];
        }
    }
    //當一個數(shù)組填完了，剩余的部分要填完，也就是另一個數(shù)組內(nèi)不存在小于等于這個數(shù)的數(shù)據(jù)了
    while (i <= mid) {
        tmp[p++] = arr[i++];
    }
    while (j <= end) {
        tmp[p++] = arr[j++];
    }
    //回填入數(shù)組
    for (int k = start; k <= end; k++) {
        arr[k] = tmp[k - start];
    }
}
void sort(int* arr, int start, int end) {
    //二分區(qū)間
    if (start < end) {//這個條件需要否則會無限遞歸
        int  mid = (start + end) >> 1;
        sort(arr, start, mid);//分成start~mid mid+1~end兩個區(qū)間
        sort(arr, mid + 1, end);
        merge_arr(arr, tmp, start, end, mid);
    }
}

6、桶排序/計數(shù)排序/基數(shù)排序

桶排序(Bucket sort)

排序方法：將輸入值的值域劃分成若干個區(qū)間，分別放入到桶中，再用其他排序方法對桶內(nèi)的元素進行排序，類似分塊，分治。

時間復雜度：取決于桶內(nèi)排序算法的時間復雜度以及分類后所在的桶的數(shù)目，如果使用堆排序來進行桶內(nèi)排序的話，并且最后均勻地分入到k個桶內(nèi)，那么時間復雜度是$O(n+n\log \frac{n}{k})$，當桶足夠多時，覆蓋了值域的時候，便是$O(n)$的計數(shù)排序。

穩(wěn)定性：取決于給桶內(nèi)排序的算法的穩(wěn)定性，如果是插入排序就是穩(wěn)定的，如果是堆排序或者快速排序就是不穩(wěn)定的。

代碼實現(xiàn)：

int arr[] = {0, 2, 9, 3, 5, 7, 8, 1, 4, 6};

//arr是被排序數(shù)組，start是起點坐標，end是終點坐標（閉區(qū)間）

void sort(int* arr, int start, int end, int bucket_size) {
    int min_value = arr[start];
    int max_value = arr[start];
    //獲得值域
    for (int i = start; i <= end; i++) {
        if (arr[i] < min_value) {
            min_value = arr[i];
        }
        if (arr[i] > max_value) {
            max_value = arr[i];
        }
    }
    int val_area = max_value - min_value + 1;
    int bucket_nums = (val_area + bucket_size - 1) / bucket_size;
    //獲得向上取整的桶的數(shù)目
    //如果此處size為4，分成 0~3, 4~7, 8~9三個桶，標號分別是0 1 2
    for (int i = start; i <= end; i++) {
        int x = arr[i];
        int id = (x - min_value) / bucket_size;
        buckets[id][elements_in_bukect[id]++] = x;//填入一個數(shù)字
    }

    for (int i = 0; i < bucket_nums; i++) {
        if (elements_in_bukect[i] == 0) continue;
        int len = elements_in_bukect[i];
        heap_sort(buckets[i], 0, len - 1);
    }

    //回收排序好的數(shù)字
    int p = 0;
    for (int i = 0; i < bucket_nums; i++) {
        if (elements_in_bukect[i] == 0) continue;
        int len = elements_in_bukect[i];
        for (int j = 0; j < len; j++) {
            arr[p + start] = buckets[i][j];
            p++;
        }
    }
}

計數(shù)排序(Counting Sort)

排序方法：計數(shù)排序是桶排序中桶的數(shù)量和值域長度相同的時候，就是一次讀入數(shù)據(jù)，放入到對應值的桶內(nèi)，最后遍歷值域輸出排序好的數(shù)組。

時間復雜度：$O(n+k)$其中k是值域長度，n是元素數(shù)目。

穩(wěn)定性：穩(wěn)定。按序讀入相同值，按序拷貝出來。筆者想了想，直接用一維數(shù)組有點難以體現(xiàn)穩(wěn)定性，如果用可變長數(shù)組或者鏈表來實現(xiàn)的話就能維護相同值的相對次序，每個鏈表存入該值的id?；蛘哂枚S數(shù)組。

代碼實現(xiàn)：

int arr[] = {0, 2, 9, 3, 5, 7, 8, 1, 4, 6};

//這里沒有用鏈表
int cnt[100];
void sort(int* arr, int start, int end) {
    int min_value = arr[start];
    int max_value = arr[start];
    for (int i = start; i <= end; i++) {
        if (arr[i] < min_value) {
            min_value = arr[i];
        }
        if (arr[i] > max_value) {
            max_value = arr[i];
        }
    }
    for (int i = start; i <= end; i++) {
        cnt[arr[i] - min_value]++;
    }
    int p = start;
    for (int i = 0; i <= max_value - min_value; i++) {
        for (int j = 0; j < cnt[i]; j++) {
            arr[p++] = i + min_value;
        }
    }
}

基數(shù)排序(Radix Sort)

排序方法：基數(shù)排序相當于對每一位作計數(shù)排序。

時間復雜度：$O(k?n)$其中k是最大數(shù)的某進制形式下的數(shù)碼長度（通常是十進制）

原理說明：手寫高位到低位分別是主要關鍵字，次要關鍵字，，，次次關鍵字，最次關鍵字。首先我們根據(jù)最低位排序，如果后面高位不相同，會按照高位排序，如果高位相同的話，但是低位不相同，計數(shù)排序具有穩(wěn)定性，不會改變低位已經(jīng)排好的順序。

穩(wěn)定性：穩(wěn)定。同上。

注意：基數(shù)排序的需要非負整數(shù)，如果有負數(shù)的話需要調(diào)整為非負整數(shù)。

代碼實現(xiàn)：

int arr[] = {0, 2, 9, 3, 5, 7, 8, 1, 40, 600};

//這里沒有用鏈表
int buckets[10][10000];//數(shù)碼桶，一個桶里可以裝10000個數(shù)
int elements_in_bucket[10];//數(shù)碼桶內(nèi)數(shù)有多少
void sort(int* arr, int start, int end) {
    int max_value = arr[start];
    for (int i = start; i <= end; i++) {
        if (arr[i] > max_value) {
            max_value = arr[i];
        }
    }
    int max_length = 0;
    while (max_value > 0) {
        max_length++;
        max_value /= 10;
    }
    if (max_length == 0) return;//如果都是0
    for (int i = 0, base = 1; i < max_length; i++, base *= 10) {
        //對每一位進行排序
        for (int j = start; j <= end; j++) {
            int digit = arr[j] / base % 10;
            //存入某位數(shù)碼為digit的桶
            buckets[digit][elements_in_bucket[digit]] = arr[j];
            //桶內(nèi)數(shù)目
            elements_in_bucket[digit]++;
        }
        int index = start;
        for (int j = 0; j < 10; j++) {//遍歷數(shù)碼桶
            if (elements_in_bucket[j] != 0) {
                for (int k = 0; k < elements_in_bucket[j]; k++) {
                    arr[index++] = buckets[j][k];
                }
            }
            elements_in_bucket[j] = 0;//
        }
    }
}

到了這里，關于【排序算法略解】（十種排序的穩(wěn)定性，時間復雜度以及實現(xiàn)思想）（含代碼）（完工于2023.8.3）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！