經典排序演算法(C語言版)

来源:https://www.cnblogs.com/sprinining/archive/2022/05/06/16228485.html
-Advertisement-
Play Games

排序 比較 分類 比較排序的時間複雜度的下界O(nlogn) 對於n個待排序元素，在未比較時，可能的正確結果有n!種。在經過一次比較後，其中兩個元素的順序被確定，所以可能的正確結果剩餘n!/2種（確定之前兩個元素的前後位置的情況是相同，確定之後相當於少了一半的可能性）。依次類推，直到經過m次比較，剩 ...


排序

比較

分類

  • 比較排序的時間複雜度的下界O(nlogn)

    對於n個待排序元素，在未比較時，可能的正確結果有n!種。在經過一次比較後，其中兩個元素的順序被確定，所以可能的正確結果剩餘n!/2種（確定之前兩個元素的前後位置的情況是相同，確定之後相當於少了一半的可能性）。依次類推，直到經過m次比較，剩餘可能性n!/(2m)種。直到n!/(2m)<=1時，結果只剩餘一種。根據斯特靈公式，此時的比較次數m為o(nlogn)次。所以基於排序的比較演算法，最優情況下，複雜度是O(nlogn)的。

源碼

  • Sort.cpp
/**
 * @file Sort.cpp
 * @author Sprinining ([email protected])
 * @brief   交換排序：冒泡排序、快速排序
 *          選擇排序：普通選擇排序、堆排序
 *          插入排序：直接插入排序、二分插入排序、希爾排序
 *          歸併排序：普通歸併排序
 *          分佈排序：計數排序、桶排序、基數排序
 * @version 0.1
 * @date 2022-05-06
 *
 * @copyright Copyright (c) 2022
 *
 */

#include <math.h>
#include <stdio.h>
#include <stdlib.h>

int cmp(const void* a, const void* b) { return *(int*)(a) - *(int*)b; }

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// a, b不能是同一個地址的東西，否則會把該地址清零
void swap2(int* a, int* b) {
    *a = *a ^ *b;
    *b = *a ^ *b;
    *a = *a ^ *b;
}

void display(int* ary, int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", ary[i]);
    }
    puts("");
}

// 1.冒泡排序
void bubbleSort(int* array, int size) {
    // 比較size-1輪
    for (int i = 0; i < size - 1; i++) {
        // 是否已經有序了
        bool isSorted = true;
        // 每一輪都會有個大元素移到後面
        for (int j = 0; j < size - 1 - i; j++) {
            // 將相鄰的兩個比較，大的移到後面
            if (array[j] > array[j + 1]) {
                // 有交換的說明沒排好
                isSorted = false;
                swap(&array[j], &array[j + 1]);
            }
        }
        if (isSorted == true) break;
    }
    display(array, size);
}

void quickSortRecursive(int* array, int left, int right) {
    if (left >= right) return;
    int i = left;
    int j = right;
    // 基準元素
    int key = array[left];
    // 分成兩半，左邊小於基準元素，右邊大於基準元素
    while (i < j) {
        // 從右往左找第一個小於key的
        while (i < j && array[j] >= key) {
            j--;
        }
        // 與key交換
        if (i < j) {
            array[i] = array[j];
            // array[j]不用立刻放入key，後面可能會有比key大的元素防止這
            i++;
        }
        // 從左往右找第一個大於key的
        while (i < j && array[i] <= key) {
            i++;
        }
        // 與key交換
        if (i < j) {
            array[j] = array[i];
            j--;
        }
    }
    // 迴圈退出時i=j
    array[i] = key;
    quickSortRecursive(array, left, i - 1);
    quickSortRecursive(array, i + 1, right);
}

// 2.快速排序
void quickSort(int* array, int size) {
    quickSortRecursive(array, 0, size - 1);
    display(array, size);
}

// 3.普通選擇排序
void selectionSort(int* array, int size) {
    // size-1輪
    for (int i = 0; i < size - 1; i++) {
        int minIndex = i;
        // 從後面找更小的
        for (int j = i + 1; j < size; j++) {
            if (array[j] < array[minIndex]) {
                minIndex = j;
            }
        }
        // 確實有更小的
        if (minIndex != i) {
            swap(&array[i], &array[minIndex]);
        }
    }
    display(array, size);
}

// 自頂向下調整堆頂（只有堆頂不符合堆的定義）
void adjustHeap(int* array, int currentIndex, int size) {
    int temp = array[currentIndex];
    int leftChildIndex = 2 * currentIndex + 1;

    while (leftChildIndex <= (size - 1)) {
        // 找更大點的子節點
        if (leftChildIndex < (size - 1) &&
            array[leftChildIndex] < array[leftChildIndex + 1]) {
            leftChildIndex++;
        }
        if (array[leftChildIndex] <= temp) break;
        // 與子節點交換
        array[currentIndex] = array[leftChildIndex];
        currentIndex = leftChildIndex;
        leftChildIndex = 2 * currentIndex + 1;
    }
    array[currentIndex] = temp;
}

// 4.堆排序
void heapSort(int* array, int size) {
    // 從第一個非葉子節點開始，自底向上
    for (int i = (size - 2) / 2; i >= 0; i--) {
        adjustHeap(array, i, size);
    }
    printf("建堆：");
    display(array, size);
    // size-1輪
    for (int i = 1; i < size; i++) {
        swap(&array[0], &array[size - i]);
        // 已經是堆了，在修改完堆頂後只需要對堆頂進行重定位
        adjustHeap(array, 0, size - i);
    }
    display(array, size);
}

// 5.直接插入排序
void insertionSort(int* array, int size) {
    // size-1輪
    // [0, i-1]是有序序列
    for (int i = 1; i < size; i++) {
        // 待插入的元素
        int temp = array[i];
        // 插入已經有序的序列
        // 從有序序列的末尾往前找第一個小於等於temp的
        int j = i - 1;
        while (j >= 0 && (array[j] > temp)) {
            // 邊找邊把不符合的元素後移
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = temp;
    }

    display(array, size);
}

// 6.二分插入排序
void binaryInsertionSort(int* array, int size) {
    for (int i = 1; i < size; i++) {
        int temp = array[i];
        // 二分查找插入位置
        int left = 0;
        int right = i - 1;
        int mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (array[mid] >= temp) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // 迴圈結束後left就是應該插入的下標
        // 把下標從left到i-1的都往後移動一位
        for (int j = i - 1; j >= left; j--) {
            array[j + 1] = array[j];
        }
        array[left] = temp;
    }
    display(array, size);
}

// 7.希爾排序
void shellSort(int* array, int size) {
    // 步長（讓一個元素可以一次性地朝最終位置前進一大步）
    int gap = size / 2;
    while (gap > 0) {
        // 間隔gap的分在同一組(共gap組，gap下標[0,
        // gap-1]是這gap組每組的首個已排序元素)，進行普通的插入排序
        for (int i = gap; i < size; i++) {
            int temp = array[i];
            int j = i - gap;
            while (j >= 0 && array[j] > temp) {
                array[j + gap] = array[j];
                j -= gap;
            }
            array[j + gap] = temp;
        }
        printf("gap:%d\n", gap);
        display(array, size);
        gap = gap / 2;
    }
}

// 分治-治
void mergeSort_conquer(int* array, int left, int mid, int right, int* temp) {
    // [left, mid]和[mid+1, right]兩個有序數組
    int i = left;
    int j = mid + 1;
    int index = 0;
    while (i <= mid && j <= right) {
        if (array[i] < array[j]) {
            temp[index++] = array[i++];
        } else {
            temp[index++] = array[j++];
        }
    }
    // 剩餘元素直接放入temp
    while (i <= mid) {
        temp[index++] = array[i++];
    }
    while (j <= right) {
        temp[index++] = array[j++];
    }
    // 放回原數組
    index = 0;
    while (left <= right) {
        array[left++] = temp[index++];
    }
}

// 分治-分
void mergeSort_divide(int* array, int left, int right, int* temp) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    // 左邊歸併排序
    mergeSort_divide(array, left, mid, temp);
    // 右邊歸併排序
    mergeSort_divide(array, mid + 1, right, temp);
    // 合併兩個有序序列
    mergeSort_conquer(array, left, mid, right, temp);
}

// 8.普通歸併排序
void mergeSort(int* array, int size) {
    int* temp = (int*)malloc(sizeof(int) * size);
    mergeSort_divide(array, 0, size - 1, temp);
    display(array, size);
}

// TODO: 迭代版歸併排序

// 9.計數排序(每個桶只存儲單一鍵值) 0~10
void countingSort(int* array, int size) {
    int* frequency = (int*)calloc(11, sizeof(int));
    // frequency[i]表示統計i出現的次數
    for (int i = 0; i < size; i++) {
        frequency[array[i]]++;
    }
    display(frequency, 11);
    // frequency[i]表示小於等於i的個數
    for (int i = 1; i < 11; i++) {
        frequency[i] += frequency[i - 1];
    }
    display(frequency, 11);

    int* sorted = (int*)calloc(size, sizeof(int));
    // 倒著遍歷原數組，把原數組放在新數組正確的位置上
    for (int i = size - 1; i >= 0; i--) {
        // 有frequency[array[i]]個小於等於array[i]個元素
        // 說明array[i]排在第frequency[array[i]]個位置，下標就是frequency[array[i]]-1
        // 放好後frequency[array[i]]要自減
        sorted[--frequency[array[i]]] = array[i];
        printf("frequency:\t");
        display(frequency, 11);
        printf("sorted:\t\t");
        display(sorted, size);
    }
}

typedef struct {
    int** bucket;
    int row;
    int column;
    int* index;
} Bucket;

// 10.桶排序(每個桶存儲一定範圍的數值)
// 數要相對均勻分佈，桶的個數也要合理設計(需要知道輸入數據的上界和下界和分佈情況)，桶排序是一種用空間換取時間的排序
void bucketSort(int* array, int size) {
    Bucket* b = (Bucket*)malloc(sizeof(Bucket));
    b->row = 5;
    b->column = 3;
    b->index = (int*)calloc(b->row, sizeof(int));
    b->bucket = (int**)malloc(sizeof(int) * b->row);
    for (int i = 0; i < b->row; i++) {
        b->bucket[i] = (int*)malloc(sizeof(int) * b->column);
    }
    // 放入桶
    for (int i = 0; i < size; i++) {
        int index = array[i] / 10;
        b->bucket[index][b->index[index]++] = array[i];
    }
    size = 0;
    // 對每個桶進行排序（可用其他演算法）
    for (int i = 0; i < b->row; i++) {
        qsort(b->bucket[i], b->column, sizeof(int), cmp);
        for (int j = 0; j < b->column; j++) {
            array[size++] = b->bucket[i][j];
        }
    }
    display(array, size);
}

// 11.基數排序(根據鍵值的每位數字來分配桶)
void radixSort(int* array, int size) {
    Bucket* b = (Bucket*)malloc(sizeof(Bucket));
    b->row = 10;
    b->column = 10;
    b->index = (int*)calloc(b->row, sizeof(int));
    // 臨時存放按某一位排好序的序列
    b->bucket = (int**)malloc(sizeof(int) * b->row);
    for (int i = 0; i < b->row; i++) {
        b->bucket[i] = (int*)malloc(sizeof(int) * b->column);
    }

    // 最大的數的位數為3
    for (int i = 0; i < 3; i++) {
        // 按某一位重新排序
        for (int j = 0; j < size; j++) {
            int index = (array[j] / (int)pow(10, i)) % 10;
            b->bucket[index][b->index[index]++] = array[j];
        }
        // 放回原數組
        int returnSize = 0;
        for (int j = 0; j < b->row; j++) {
            for (int k = 0; k < b->index[j]; k++) {
                array[returnSize++] = b->bucket[j][k];
            }
            // 重置下標數組
            b->index[j] = 0;
        }
    }

    display(array, size);
}

void testSort() {
    // int a[] = {1, 0, 7, 2, 10, 5, 2, 8, 6, 0};
    // display(a, 10);
    // bubbleSort(a, 10);
    // quickSort(a, 10);
    // selectionSort(a, 10);
    // heapSort(a, 10);
    // insertionSort(a, 10);
    // binaryInsertionSort(a, 10);
    // shellSort(a, 10);
    // mergeSort(a, 10);
    // countingSort(a, 10);

    // int b[] = {1, 8, 7, 44, 42, 46, 38, 34, 33, 17, 15, 16, 27, 28, 24};
    // display(b, 15);
    // bucketSort(b, 15);

    int c[] = {53, 3, 542, 748, 14, 77, 214, 154, 63, 616};
    radixSort(c, 10);
}

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • ReentrantLock學習
    ReentrantLock ReentrantLock功能 ReentrantLock和synchronized一樣是可重入的 可重入即當線程擁有了鎖時，當該線程再次請求鎖資源的時候，線程是可以再次成功獲得的。 static ReentrantLock lock = new ReentrantLoc ...
  • PageObject（PO）設計模式在 UI 自動化中的實踐總結（以 QQ 郵箱登陸為例）
    Spring Ioc源碼分析系列--Ioc的基礎知識準備 本系列文章代碼基於Spring Framework 5.2.x Ioc的概念 在Spring里，Ioc的定義為The IoC Container，翻譯過來也就是Ioc容器。為什麼會被叫做容器呢？我們來比對一下日常生活中的容器，也就是那些瓶瓶罐 ...
  • Spring 源碼（8）Spring BeanPostProcessor的註冊、國際化及事件發佈機制
    上一篇文章https://www.cnblogs.com/redwinter/p/16198942.html介紹了Spring的註解的解析過程以及Spring Boot自動裝配的原理，大概回顧下：Spring 解析註解是通過BeanFactoryPostProcessor的子介面BeanDefini ...
  • 完了，我的小網站圖片掛了！
    大家好，我是二哥！ 很早之前，就有小伙伴給我反饋說《Java 程式員進階之路》經常有圖片不顯示或者載入緩慢。 但由於白嫖（GitHub圖床+jsdelivr CDN）的力量實在是太過強大了（狗頭），再加上我本人沒有遇到過這個問題，所以就一直拖延著，遲遲沒有行動。 直到某一天，我神秘的流量用光了，上不 ...
  • 【面試普通人VS高手系列】講一下wait和notify這個為什麼要在synchronized代碼塊中？
    一個工作七年的小伙伴，竟然不知道”wait”和“notify”為什麼要在Synchronized代碼塊裡面。 好吧，如果屏幕前的你也不知道，請在評論區打上”不知道“。 對於這個問題，我們來看看普通人和高手的回答。 普通人： 額。。。。。。。。。。。。 高手： wait和notify用來實現多線程之間 ...
  • Python 源代碼縮進格式化工具
    前言 昨天在跟小伙伴聊天，當他談起自己正在做的項目時，一臉愁容。 他吐槽道：“該項目的 Python 代碼庫由多個人共同維護。由於每個人使用的編輯器不同，每個人的編碼風格也不同，最終導致了 代碼的縮進千奇百怪：有縮進 2 個空格的，有縮進 4 個空格的，有縮進 8 個空格，有縮進一個 Tab 的，更 ...
  • Java 中 equals 的這些坑，千萬別踩。。。
    來源：cnblogs.com/juncaoit/p/12422752.html 一直以為這個方法是java8的，今天才知道是是1.7的時候，然後翻了一下源碼。 這篇文章中會總結一下與a.equals(b)的區別，然後對源碼做一個小分析。 值是null的情況 1、a.equals(b), a 是nul ...
  • 詳解 Java 17 中新推出的密封類
    Java 17推出的新特性Sealed Classes經歷了2個Preview版本（JDK 15中的JEP 360、JDK 16中的JEP 397），最終定稿於JDK 17中的JEP 409。Sealed Classes有兩種主流翻譯：密封類、封閉類。個人喜歡前者多一些，所以在本文中都稱為密封類。其 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類