8種主要排序演算法的C#實現 （一）

来源:http://www.cnblogs.com/ldyblogs/archive/2017/11/17/sort.html
-Advertisement-
Play Games

簡介 排序演算法是我們編程中遇到的最多的演算法。目前主流的演算法有8種。 平均時間複雜度從高到低依次是： 冒泡排序（o(n2)），選擇排序（o(n2)），插入排序（o(n2)），堆排序（o(nlogn)）， 歸併排序（o(nlogn)），快速排序（o(nlogn)）， 希爾排序（o(n1.25)），基數排 ...


簡介

排序演算法是我們編程中遇到的最多的演算法。目前主流的演算法有8種。

  平均時間複雜度從高到低依次是：

     冒泡排序（o(n2)），選擇排序（o(n2)），插入排序（o(n2)），堆排序（o(nlogn)），

     歸併排序（o(nlogn)），快速排序（o(nlogn)）， 希爾排序（o(n1.25)），基數排序（o(n)）

這些平均時間複雜度是參照維基百科排序演算法羅列的。

是計算的理論平均值，並不意味著你的代碼實現能達到這樣的程度。

例如希爾排序，時間複雜度是由選擇的步長決定的。基數排序時間複雜度最小，

但我實現的基數排序的速度並不是最快的，後面的結果測試圖可以看到。

本文代碼實現使用的數據源類型為IList<int>，這樣可以相容int[]和List<int>(雖然int[]有ToList()，

List<int>有ToArray()，哈哈！)。

選擇排序

選擇排序是我覺得最簡單暴力的排序方式了。

以前剛接觸排序演算法的時候，感覺演算法太多搞不清，唯獨記得選擇排序的做法及實現。

原理：找出參與排序的數組最大值，放到末尾（或找到最小值放到開頭） 維基入口

實現如下：

public static void SelectSort(IList<int> data)
        {
            for (int i = 0; i < data.Count - 1; i++)
            {
                int min = i;
                int temp = data[i];
                for (int j = i + 1; j < data.Count; j++)
                {
                    if (data[j] < temp)
                    {
                        min = j;
                        temp = data[j];
                    }
                }
                if (min != i)
                    Swap(data, min, i);
            }
        }

過程解析：將剩餘數組的最小數交換到開頭。

冒泡排序

冒泡排序是筆試面試經常考的內容，雖然它是這些演算法里排序速度最慢的（汗），後面有測試為證。

原理：從頭開始，每一個元素和它的下一個元素比較，如果它大，就將它與比較的元素交換，否則不動。

這意味著，大的元素總是在向後慢慢移動直到遇到比它更大的元素。所以每一輪交換完成都能將最大值

冒到最後。  維基入口

實現如下：

public static void BubbleSort(IList<int> data)
        {
            for (int i = data.Count - 1; i > 0; i--)
            {
                for (int j = 0; j < i; j++)
                {
                    if (data[j] > data[j + 1])
                        Swap(data, j, j + 1);
                }
            }
        }

過程解析：中需要註意的是j<i，每輪冒完泡必然會將最大值排到數組末尾，所以需要排序的數應該是在減少的。

很多網上版本每輪冒完泡後依然還是將所有的數進行第二輪冒泡即j<data.Count-1，這樣會增加比較次數。

通過標識提升冒泡排序

在維基上看到，可以通過添加標識來分辨剩餘的數是否已經有序來減少比較次數。感覺很有意思，可以試試。

實現如下：

public static void BubbleSortImprovedWithFlag(IList<int> data)
        {
            bool flag;
            for (int i = data.Count - 1; i > 0; i--)
            {
                flag = true;
                for (int j = 0; j < i; j++)
                {
                    if (data[j] > data[j + 1])
                    {
                        Swap(data, j, j + 1);
                        flag = false;
                    }
                }
                if (flag) break;
            }
        }

過程解析：發現某輪冒泡沒有任何數進行交換（即已經有序），就跳出排序。

我起初也以為這個方法是應該有不錯效果的，可是實際測試結果並不如想的那樣。和未優化耗費時間一樣（對於隨機數列）。

由果推因，那麼應該是冒泡排序對於隨機數列，當剩餘數列有序的時候，也沒幾個數要排列了！？

不過如果已經是有序數列或者部分有序的話，這個冒泡方法將會提升很大速度。

雞尾酒排序（來回排序）

對冒泡排序進行更大的優化

冒泡排序只是單向冒泡，而雞尾酒來回反覆雙向冒泡。

原理：自左向右將大數冒到末尾，然後將剩餘數列再自右向左將小數冒到開頭，如此迴圈往複。維基入口

實現如下：

public static void BubbleCocktailSort(IList<int> data)
        {
            bool flag;
            int m = 0, n = 0;
            for (int i = data.Count - 1; i > 0; i--)
            {
                flag = true;
                if (i % 2 == 0)
                {
                    for (int j = n; j < data.Count - 1 - m; j++)
                    {
                        if (data[j] > data[j + 1])
                        {
                            Swap(data, j, j + 1);
                            flag = false;
                        }
                    }
                    if (flag) break;
                    m++;
                }
                else
                {
                    for (int k = data.Count - 1 - m; k > n; k--)
                    {
                        if (data[k] < data[k - 1])
                        {
                            Swap(data, k, k - 1);
                            flag = false;
                        }
                    }
                    if (flag) break;
                    n++;
                }
            }
        }

過程解析：分析第i輪冒泡，i是偶數則將剩餘數列最大值向右冒泡至末尾，是奇數則將剩餘數列最小值

向左冒泡至開頭。對於剩餘數列，n為始，data.Count-1-m為末。

來回冒泡比單向冒泡：對於隨機數列，更容易得到有序的剩餘數列。因此這裡使用標識將會提升的更加明顯。

插入排序

插入排序是一種對於有序數列高效的排序。非常聰明的排序。只是對於隨機數列，效率一般，交換的頻率高。

原理：通過構建有序數列，將未排序的數從後向前比較，找到合適位置並插入。維基入口

第一個數當作有序數列。

實現如下：

public static void InsertSort(IList<int> data)
        {
            int temp;
            for (int i = 1; i < data.Count; i++)
            {
                temp = data[i];
                for (int j = i - 1; j >= 0; j--)
                {
                    if (data[j] > temp)
                    {
                        data[j + 1] = data[j];
                        if (j == 0)
                        {
                            data[0] = temp;
                            break;
                        }
                    }
                    else
                    {
                        data[j + 1] = temp;
                        break;
                    }
                }
            }
        }

過程解析：將要排序的數（索引為i）存儲起來，向前查找合適位置j+1，將i-1到j+1的元素依次向後

移動一位，空出j+1，然後將之前存儲的值放在這個位置。

這個方法寫的不如維基上的簡潔清晰，由於合適位置是j+1所以多出了對j==0的判斷，但實際效率影響無差別。

建議比照維基和我寫的排序，自行選擇。

二分查找法優化插入排序

插入排序主要工作是在有序的數列中對要排序的數查找合適的位置，而查找裡面經典的二分查找法正可以適用。

原理：通過二分查找法的方式找到一個位置索引。當要排序的數插入這個位置時，大於前一個數，小於後一個數。

實現如下：

public static void InsertSortImprovedWithBinarySearch(IList<int> data)
        {
            int temp;
            int tempIndex;
            for (int i = 1; i < data.Count; i++)
            {
                temp = data[i];
                tempIndex = BinarySearchForInsertSort(data, 0, i, i);
                for (int j = i - 1; j >= tempIndex; j--)
                {
                    data[j + 1] = data[j];
                }
                data[tempIndex] = temp;
            }
        }

        public static int BinarySearchForInsertSort(IList<int> data, int low, int high, int key)
        {
            if (low >= data.Count - 1)
                return data.Count - 1;
            if (high <= 0)
                return 0;
            int mid = (low + high) / 2;
            if (mid == key) return mid;
            if (data[key] > data[mid])
            {
                if (data[key] < data[mid + 1])
                    return mid + 1;
                return BinarySearchForInsertSort(data, mid + 1, high, key);
            }
            else  // data[key] <= data[mid]
            {
                if (mid - 1 < 0) return 0;
                if (data[key] > data[mid - 1])
                    return mid;
                return BinarySearchForInsertSort(data, low, mid - 1, key);
            }
        }

過程解析：需要註意的是二分查找方法實現中high-low==1的時候mid==low，所以需要33行

mid-1<0即mid==0的判斷，否則下行會索引越界。

快速排序

快速排序是一種有效比較較多的高效排序。它包含了“分而治之”以及“哨兵”的思想。

原理：從數列中挑選一個數作為“哨兵”，使比它小的放在它的左側，比它大的放在它的右側。將要排序是數列遞歸地分割到

最小數列，每次都讓分割出的數列符合“哨兵”的規則，自然就將數列變得有序。 維基入口

實現如下：

public static void QuickSortStrict(IList<int> data)
        {
            QuickSortStrict(data, 0, data.Count - 1);
        }

        public static void QuickSortStrict(IList<int> data, int low, int high)
        {
            if (low >= high) return;
            int temp = data[low];
            int i = low + 1, j = high;
            while (true)
            {
                while (data[j] > temp) j--;
                while (data[i] < temp && i < j) i++;
                if (i >= j) break;
                Swap(data, i, j);
                i++; j--;
            }
            if (j != low)
                Swap(data, low, j);
            QuickSortStrict(data, j + 1, high);
            QuickSortStrict(data, low, j - 1);
        }

過程解析：取的哨兵是數列的第一個值，然後從第二個和末尾同時查找，左側要顯示的是小於哨兵的值，

所以要找到不小於的i，右側要顯示的是大於哨兵的值，所以要找到不大於的j。將找到的i和j的數交換，

這樣可以減少交換次數。i>=j時，數列全部查找了一遍，而不符合條件j必然是在小的那一邊，而哨兵

是第一個數，位置本應是小於自己的數。所以將哨兵與j交換，使符合“哨兵”的規則。

這個版本的缺點在於如果是有序數列排序的話，遞歸次數會很可怕的。

另一個版本

這是維基上的一個C#版本，我覺得很有意思。這個版本並沒有嚴格符合“哨兵”的規則。但卻將“分而治之”

以及“哨兵”思想融入其中，代碼簡潔。

實現如下：

public static void QuickSortRelax(IList<int> data)
        {
            QuickSortRelax(data, 0, data.Count - 1);
        }

        public static void QuickSortRelax(IList<int> data, int low, int high)
        {
            if (low >= high) return;
            int temp = data[(low + high) / 2];
            int i = low - 1, j = high + 1;
            while (true)
            {
                while (data[++i] < temp) ;
                while (data[--j] > temp) ;
                if (i >= j) break;
                Swap(data, i, j);
            }
            QuickSortRelax(data, j + 1, high);
            QuickSortRelax(data, low, i - 1);
        }

過程解析：取的哨兵是數列中間的數。將數列分成兩波，左側小於等於哨兵，右側大於等於哨兵。

也就是說，哨兵不一定處於兩波數的中間。雖然哨兵不在中間，但不妨礙“哨兵”的思想的實現。所以

這個實現也可以達到快速排序的效果。但卻造成了每次遞歸完成，要排序的數列數總和沒有減少（除非i==j）。

針對這個版本的缺點，我進行了優化

實現如下：

public static void QuickSortRelaxImproved(IList<int> data)
        {
            QuickSortRelaxImproved(data, 0, data.Count - 1);
        }

        public static void QuickSortRelaxImproved(IList<int> data, int low, int high)
        {
            if (low >= high) return;
            int temp = data[(low + high) / 2];
            int i = low - 1, j = high + 1;
            int index = (low + high) / 2;
            while (true)
            {
                while (data[++i] < temp) ;
                while (data[--j] > temp) ;
                if (i >= j) break;
                Swap(data, i, j);
                if (i == index) index = j;
                else if (j == index) index = i;
            }
            if (j == i)
            {
                QuickSortRelaxImproved(data, j + 1, high);
                QuickSortRelaxImproved(data, low, i - 1);
            }
            else //i-j==1
            {
                if (index >= i)
                {
                    if (index != i)
                        Swap(data, index, i);
                    QuickSortRelaxImproved(data, i + 1, high);
                    QuickSortRelaxImproved(data, low, i - 1);
                }
                else //index < i
                {
                    if (index != j)
                        Swap(data, index, j);
                    QuickSortRelaxImproved(data, j + 1, high);
                    QuickSortRelaxImproved(data, low, j - 1);
                }
            }
        }
public static void QuickSortRelaxImproved(IList<int> data)
        {
            QuickSortRelaxImproved(data, 0, data.Count - 1);
        }

        public static void QuickSortRelaxImproved(IList<int> data, int low, int high)
        {
            if (low >= high) return;
            int temp = data[(low + high) / 2];
            int i = low - 1, j = high + 1;
            int index = (low + high) / 2;
            while (true)
            {
                while (data[++i] < temp) ;
                while (data[--j] > temp) ;
                if (i >= j) break;
                Swap(data, i, j);
                if (i == index) index = j;
                else if (j == index) index = i;
            }
            if (j == i)
            {
                QuickSortRelaxImproved(data, j + 1, high);
                QuickSortRelaxImproved(data, low, i - 1);
            }
            else //i-j==1
            {
                if (index >= i)
                {
                    if (index != i)
                        Swap(data, index, i);
                    QuickSortRelaxImproved(data, i + 1, high);
                    QuickSortRelaxImproved(data, low, i - 1);
                }
                else //index < i
                {
                    if (index != j)
                        Swap(data, index, j);
                    QuickSortRelaxImproved(data, j + 1, high);
                    QuickSortRelaxImproved(data, low, j - 1);
                }
            }
        }

過程解析：定義了一個變數Index，來跟蹤哨兵的位置。發現哨兵最後在小於自己的那堆，

那就與j交換，否則與i交換。達到每次遞歸都能減少要排序的數列數總和的目的。

以上動圖由“圖鬥羅”提供


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

-Advertisement-
Play Games
更多相關文章
  • Visual Studio 2017開發環境的安裝
    Visual Studio 2017是微軟為了配合.NET戰略推出的IDE開發環境，同時也是目前開發C#程式最新的工具，本節以Visual Studio 2017社區版的安裝為例講解具體的安裝步驟。 說明：Visual Studio 2017 社區版是完全免費的，其下載地址為：https://www ...
  • Topshelf的使用
    一、簡介 Topshelf可用於創建和管理Windows服務。其優勢在於不需要創建windows服務，創建控制台程式就可以。便於調試。 二、官方地址： 1、官網：http://topshelf-project.com/ 2、官方文檔：https://topshelf.readthedocs.io/e ...
  • Nginx集群之WCF分散式區域網應用
    關於WCF即可以寄宿於IIS，也可以自我寄宿，本文采用的是自我寄宿方式。之所以採用自我寄宿方式，很大程度上，在一些特殊的場景，例如下載大文件（如幾百MB、1G等）、圖片、文檔等，如果以IIS為宿主，可能會產生記憶體不夠用。所以這裡採用自我寄宿的方式為例子。WCF是由微軟開發的一系列支持數據通信的應用程... ...
  • IIS載入JSON文件 錯誤 404
    問題描述 在發佈項目的時候，有一些文件是json文件，在網頁中進行載入，但是在IIS7發佈的時候，json文件居然是404，無法找到，在URL上輸入地址也一樣。 錯誤原因 IIS內部機制，不支持直接訪問json擴展名文件，沒有mime映射。因此IIS不認Json文件，如需要支持訪問json文件時，需 ...
  • ASP.NET沒有魔法——ASP.NET MVC 過濾器(Filter)
    上一篇文章介紹了使用Authorize特性實現了ASP.NET MVC中針對Controller或者Action的授權功能，實際上這個特性是MVC功能的一部分，被稱為過濾器(Filter)，它是一種面向切麵編程(AOP)的實現，本章將從以下幾個方面來介紹ASP.NET MVC中的過濾器。 ● ASP ...
  • 對js運算符“||”和“&&”的總結
    首先出個題： 如圖： 假設對成長速度顯示規定如下： 成長速度為5顯示1個箭頭； 成長速度為10顯示2個箭頭； 成長速度為12顯示3個箭頭； 成長速度為15顯示4個箭頭； 其他都顯示都顯示0各箭頭。 用代碼怎麼實現？ 差一點的if，else： Js代碼 var add_level = 0; if(ad ...
  • 背水一戰 Windows 10 (73) - 控制項（控制項基類）: UIElement - 拖放的基本應用, 手動開啟 UIElement 的拖放操作
    背水一戰 Windows 10 之 控制項（控制項基類 - UIElement ）: 拖放的基本應用, 手動開啟 UIElement 的拖放操作 ...
  • Winform開發框架中工作流模塊之申請單草稿處理
    在我們開發工作流模塊的時候，有時候填寫申請單過程中，暫時不想提交審批，那麼可以暫存為草稿，以供下次繼續填寫或者提交處理，那麼這個草稿的功能是比較實用的，否則對於一些填寫內容比較多的申請單，每次要重填寫很多數據，那會被用戶罵的，從用戶的角度上來講，提供草稿保存的功能是比較友好的。本篇隨筆介紹在工作流模... ...
一周排行
    -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.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類