前言 算法這個東西其實在開發中很少用到，特別是web開發中，但是算法也很重要，因為任何的程序，任何的軟件，都是由很多的算法和數據結構組成的。但是這不意味著算法對於每個軟件設計人員的實際工作都是很重要的。每個項目特點和需求特殊也導致算法運用場景上不同。但是個人覺得算法運用的好的話會給自己在程序設計的時候提供比較好的思路。下面就對一些排序算法小結一下，就當做自己的一個筆記吧。 插入排序 1.簡介 插入排序（Insertion Sort）的算法描述是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。插入排序在實現上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從後向前掃描過程中，需要反復把已排序元素逐步向後挪位，為最新元素提供插入空間。 2.算法描述 一般來說，插入排序都采用in-place在數組上實現。具體算法描述如下： 1.從第一個元素開始，該元素可以認為已經被排序 2.取出下一個元素，在已經排序的元素序列中從後向前掃描 3.如果該元素（已排序）大於新元素，將該元素移到下一位置 4.重復步驟3，直到找到已排序的元素小於或者等於新元素的位置 5.將新元素插入到該位置後 6.重復步驟2~5 如果比較操作的代價比交換操作大的話，可以采用二分查找法來減少比較操作的數目。該算法可以認為是插入排序的一個變種，稱為二分查找排序。 3.使用插入排序為一列數字進行排序的過程 最差時間復雜度 O(n^{2}) 最優時間復雜度 O(n) 平均時間復雜度O(n^{2}) 4.C#實現 復制代碼 /// <summary> /// 插入排序 /// </summary> public class InsertionSorter { public void Sort(int[] list) { for (int i = 1; i < list.Length; ++i) { int t = list[i]; int j = i; while ((j > 0) && (list[j - 1] > t)) { list[j] = list[j - 1]; --j; } list[j] = t; } } } 復制代碼 數組 int[] iArrary = new int[] { 1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47 }; 希爾排序 1.簡介 希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。希爾排序是非穩定排序算法。 2.算法實現 原始的算法實現在最壞的情況下需要進行O(n2)的比較和交換。V. Pratt的書[1] 對算法進行了少量修改，可以使得性能提升至O(n log2 n)。這比最好的比較算法的O(n log n)要差一些。 希爾排序通過將比較的全部元素分為幾個區域來提升插入排序的性能。這樣可以讓一個元素可以一次性地朝最終位置前進一大步。然後算法再取越來越小的步長進行排序，算法的最後一步就是普通的插入排序，但是到了這步，需排序的數據幾乎是已排好的了（此時插入排序較快）。 假設有一個很小的數據在一個已按升序排好序的數組的末端。如果用復雜度為O(n2)的排序（冒泡排序或插入排序），可能會進行n次的比較和交換才能將該數據移至正確位置。而希爾排序會用較大的步長移動數據，所以小數據只需進行少數比較和交換即可到正確位置。 一個更好理解的希爾排序實現：將數組列在一個表中並對列排序（用插入排序）。重復這過程，不過每次用更長的列來進行。最後整個表就只有一列了。將數組轉換至表是為了更好地理解這算法，算法本身僅僅對原數組進行排序（通過增加索引的步長，例如是用i += step_size而不是i++）。 3.排序過程 最差時間復雜度 根據步長串行的不同而不同。O(n\log^2 n) 最優時間復雜度 O(n) 平均時間復雜度 根據步長串行的不同而不同。 4.C#實現 復制代碼 /// <summary> /// 希爾排序 /// </summary> public class ShellSorter { public void Sort(int[] list) { int inc; for (inc = 1; inc <= list.Length / 9; inc = 3 * inc + 1) ; for (; inc > 0; inc /= 3) { for (int i = inc + 1; i <= list.Length; i += inc) { int t = list[i - 1]; int j = i; while ((j > inc) && (list[j - inc - 1] > t)) { list[j - 1] = list[j - inc - 1]; j -= inc; } list[j - 1] = t; } } } } 復制代碼 選擇排序 1.簡介 選擇排序(Selection sort)是一種簡單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩余未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。 選擇排序的主要優點與數據移動有關。如果某個元素位於正確的最終位置上，則它不會被移動。選擇排序每次交換一對元素，它們當中至少有一個將被移到其最終位置上，因此對n個元素的表進行排序總共進行至多n-1次交換。在所有的完全依靠交換去移動元素的排序方法中，選擇排序屬於非常好的一種。 2.實現過程 最差時間復雜度 О(n²) 最優時間復雜度 О(n²) 平均時間復雜度 О(n²) 3.C#實現 復制代碼 /// <summary> /// 選擇排序 /// </summary> public class SelectionSorter { // public enum comp {COMP_LESS,COMP_EQUAL,COMP_GRTR}; private int min; // private int m=0; public void Sort(int[] list) { for (int i = 0; i < list.Length - 1; ++i) { min = i; for (int j = i + 1; j < list.Length; ++j) { if (list[j] < list[min]) min = j; } int t = list[min]; list[min] = list[i]; list[i] = t; // Console.WriteLine("{0}",list[i]); } } } 復制代碼 冒泡排序 1.簡介 冒泡排序（Bubble Sort，台灣譯為：泡沫排序或氣泡排序）是一種簡單的排序算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。 冒泡排序對n個項目需要O(n^{2})的比較次數，且可以原地排序。盡管這個算法是最簡單了解和實作的排序算法之一，但它對於少數元素之外的數列排序是很沒有效率的。 冒泡排序是與插入排序擁有相等的執行時間，但是兩種法在需要的交換次數卻很大地不同。在最壞的情況，冒泡排序需要O(n^{2})次交換，而插入排序只要最多O(n)交換。冒泡排序的實現（類似下面）通常會對已經排序好的數列拙劣地執行（O(n^{2})），而插入排序在這個例子只需要O(n)個運算。因此很多現代的算法教科書避免使用冒泡排序，而用插入排序取代之。冒泡排序如果能在內部循環第一次執行時，使用一個旗標來表示有無需要交換的可能，也有可能把最好的復雜度降低到O(n)。在這個情況，在已經排序好的數列就無交換的需要。若在每次走訪數列時，把走訪順序和比較大小反過來，也可以稍微地改進效率。有時候稱為往返排序，因為算法會從數列的一端到另一端之間穿梭往返。 2.算法實現 1.比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。 2.對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。 3.針對所有的元素重復以上的步驟，除了最後一個。 4.持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。 3.實現過程 最差時間復雜度 O(n^{2}) 最優時間復雜度 O(n) 平均時間復雜度 O(n^{2}) 4.C#實現 復制代碼 /// <summary> /// 冒泡排序 /// </summary> public class bubblesort { public void BubbleSort(int[] R) { int i, j, temp; //交換標志 bool exchange; for (i = 0; i < R.Length; i++) //最多做R.Length-1趟排序 { exchange = false; //本趟排序開始前，交換標志應為假 for (j = R.Length - 2; j >= i; j--) { if (R[j + 1] < R[j]) //交換條件 { temp = R[j + 1]; R[j + 1] = R[j]; R[j] = temp; exchange = true; //發生了交換，故將交換標志置為真 } } if (!exchange) //本趟排序未發生交換，提前終止算法 { break; } } } } 復制代碼
