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
  • Dapr Outbox 執行流程
    Dapr Outbox 是1.12中的功能。 本文只介紹Dapr Outbox 執行流程，Dapr Outbox基本用法請閱讀官方文檔 。本文中appID=order-processor，topic=orders 本文前提知識：熟悉Dapr狀態管理、Dapr發佈訂閱和Outbox 模式。 Outbo ...
  • Advanced .Net Debugging 7：托管堆與垃圾收集
    引言 在前幾章我們深度講解了單元測試和集成測試的基礎知識，這一章我們來講解一下代碼覆蓋率,代碼覆蓋率是單元測試運行的度量值,覆蓋率通常以百分比表示，用於衡量代碼被測試覆蓋的程度，幫助開發人員評估測試用例的質量和代碼的健壯性。常見的覆蓋率包括語句覆蓋率（Line Coverage）、分支覆蓋率（Bra ...
  • C#S7.NET實現西門子PLCDB塊數據採集的完整步驟
    前言 本文介紹瞭如何使用S7.NET庫實現對西門子PLC DB塊數據的讀寫，記錄了使用電腦模擬，模擬PLC，自至完成測試的詳細流程，並重點介紹了在這個過程中的易錯點，供參考。 用到的軟體： 1.Windows環境下鏈路層網路訪問的行業標準工具（WinPcap_4_1_3.exe）下載鏈接：http ...
  • WPF控制項：密碼框綁定MVVM
    從依賴倒置原則（Dependency Inversion Principle, DIP）到控制反轉（Inversion of Control, IoC）再到依賴註入（Dependency Injection, DI）的演進過程，我們可以理解為一種逐步抽象和解耦的設計思想。這種思想在C#等面向對象的編 ...
  • Python中的私有屬性與私有方法
    關於Python中的私有屬性和私有方法 Python對於類的成員沒有嚴格的訪問控制限制，這與其他面相對對象語言有區別。關於私有屬性和私有方法，有如下要點： 1、通常我們約定，兩個下劃線開頭的屬性是私有的（private）。其他為公共的（public）； 2、類內部可以訪問私有屬性（方法）； 3、類外 ...
  • C++ 訪問說明符詳解：封裝數據，控制訪問，提升安全性
    C++ 訪問說明符 訪問說明符是 C++ 中控制類成員（屬性和方法）可訪問性的關鍵字。它們用於封裝類數據並保護其免受意外修改或濫用。 三種訪問說明符： public：允許從類外部的任何地方訪問成員。 private：僅允許在類內部訪問成員。 protected：允許在類內部及其派生類中訪問成員。 示 ...
  • static_cast與dynamic_cast到底是什麼？
    寫這個隨筆說一下C++的static_cast和dynamic_cast用在子類與父類的指針轉換時的一些事宜。首先，【static_cast，dynamic_cast】【父類指針，子類指針】，兩兩一組，共有4種組合：用 static_cast 父類轉子類、用 static_cast 子類轉父類、使用 ...
  • C語言數據結構：雙向鏈表的增刪操作
    /******************************************************************************************************** * * * 設計雙向鏈表的介面 * * * * Copyright (c) 2023-2 ...
  • @ComponentScan註解的實現，Spring掃描包的過程
    相信接觸過spring做開發的小伙伴們一定使用過@ComponentScan註解 @ComponentScan("com.wangm.lifecycle") public class AppConfig { } @ComponentScan指定basePackage，將包下的類按照一定規則註冊成Be ...
  • opensips開啟python支持
    操作系統 ：CentOS 7.6_x64 opensips版本： 2.4.9 python版本：2.7.5 python作為腳本語言，使用起來很方便，查了下opensips的文檔，支持使用python腳本寫邏輯代碼。今天整理下CentOS7環境下opensips2.4.9的python模塊筆記及使用 ...
所有分類