### 引言 本節主要介紹基本的排序算法原理與實現 ，即：插入排序，選擇排序，冒泡排序. ### 插入排序算法 #### 基本思想 插入排序首先考慮data中的前兩個元素，即data[0]和data[1]。如果它們的次序顛倒了，就交換它們。然后，考慮第三個元素data[2],將其插入到合適的位置上。如果data[2]同時小于data[0]和data[1],那么data[0]和data[1]都要移動一個位置；data[0]放在位置1上，data[1]放在位置2上，而將data[2]放在位置0上。如果data[2]小于data[1]，而不于data[0],那么只須把data[1]移動到位置2上，并由data[2]占據它的位置。最后，如果data[2]不小于前兩個元素，它將保留在當前的位置。每一個元素data[i]都要插入到合適的位置j上，使0<=j<=i,所有比data[i]大的元素都要移動一個位置。 插入排序算法的要點如下： ~~~ insertionsort(data[],n){ for(i=1; i<n; i++) move all elements data[j] greater than data[i] by one position; place data[i] in its proper position; } ~~~ 注意，在每次迭代中，排序只限于數組的一小部分，并且只在最后一次迭代中才涉及到整個數組。如下圖所示是當對數組[5 2 3 8 1]行insertionsort()方法時，數組所發生的一系變動。  因數組中只有一個元素已排序，所以算法從第二元素位置即位置1開始排序。接著，對于每一個元素tmp = data[i],所有比tmp大的位素都要復制到下一位置上，而把tmp放在合適的位置上。 實現代碼如下： ~~~ template< class T> void insertionsort(T data[], int n) { for(int i =1, j; i<n; i++){ T tmp = data[i]; for(j =i; i>0&&tmp< data[j-1]; j--) data[j] = data[j-1]; data[j] =tmp; } } ~~~ 插入排序的一個優點是只有需要時才對數組排序。如果數組已經排好序了，就不再對數組進行移動；只有變量tmp得到初始化，存儲在變量中的值返回值原位置。可以識別出已排序的數組部分，并相應停止，但忽視元素可以已在合適位置上的事實。一個缺點是：如果插入數據項，所有比插入元素大的元素都必須移動。插入操作不是局部的，可能需要移動大量的元素。其中，在博文[【編程珠璣】插入排序](http://blog.csdn.net/songzitea/article/details/8761722)中，介紹了關于插入排序優化代碼。 #### 算法分析 為了獲取insertionsort()算法執行的移動和比較次數，首先要注意，外層的for語句執行n-1次。但是，比data[i]大的元素移動一個位置的次數并不總是相同的。 **最好的情況是**：數據已排好序。對于每個位置i,只需比較一勻，這樣就只需進行n-1次比較(其數量級是o(n))和2(n-1)次移動，所有的移動和比較都是多余的。**最壞的情況是：**數據按相反順序排序。在這種情況下，對于外層for的每次迭代i,都比較i次，即所有迭代的比較總數是  內層for中的賦值次數可以用相同的公式計算。把tmp在外層for中加載和卸載的次數加起來，得到總的移動次數：  前面我們只考慮了極端情況。如果數據是隨機排序的，結果如何呢？假設數據項占用數組單元的概率相等，在外層for的迭代i中，data[i]與其它元素的平均比較次數計算如下：  為了求得所有比較次數的平均值，對于所有的迭代i來說，都必須從1開始一直累加到n-1為止。結果是  它的時間復雜度是O(n^2),大約是最壞情況下的比較次數的1/2。按照相同的方式，可以確定在外層for的迭代i中，data[i]需要移動0,1,..i-1次：即  次，加上一定分會發生的兩次移動。因此，在外層for中所有迭代中，平均移動次數為  其中時間復雜度為O(n^2)。 綜上所述，對于隨機順序的數組來說，移動和比較的次數是與最好情況接近，還是與最壞情況接近？遺憾的是，它接近于后者，即：當數組的元素加倍時，平均需要付出4倍的努力來排序。 #### 測試輸出結果  ### 選擇排序算法 #### 基本思想 選擇排序先找到時位置不合適的元素，再把它放在其最終的合適位置上，它試圖僅在本地交換數組元素。基本思想是：先找出數組中的最小元素，將其與第一個位置上的元素進行交換。然后在剩余元素data[1],...,data[i-1]中找到最小元素，把它放到第二個位置上。這種選擇和定位的方法是：在每次迭代中，找出元素data[i],....data[n-1]中的最小元素，然后將其與data[i]交換位置，直到所有的元素都放到了合適位置為止。 如下的偽代碼反映出選擇排序算法的簡單性： ~~~ selectionsort(data[] ,n) for i =0 到n-2 找出元素data[i]....data[n-1]中的最小元素； 將其與data[i]交換； ~~~ 很明顯，n-2是最后一個i值，因為尋如果除最后一個元素之外的所有元素都放在合適的位置上，那么第n個元素就是一定是最大的。下面提選擇排序的C++代碼： ~~~ template <class genType> void selectionsort (genType data[], int n) { int j,least; for(int i =0; i<n-1; i++) { for(j = i+1,least = i; j< n; j++){ if(data[j] <data[least]) least =j; } genType temp = data[least]; data[least] = data[i]; data[i] = temp; } } ~~~ 選擇排序最大的優點是賦值次數少，這一點是其他算法無法比擬的。然而，所有情況下總是交換次數都為3(n-1)次，讓人不太理想。 #### 算法分析 函數selectionsort( ) 的性能分析可通過兩個for循環的上下界來簡化，外層循環行了運行n-1次，對于任意一個0和n-2之間的整數i,內層循環迭代了j= (n-1)－1 次.因為為關鍵字的比較是在內層循環進行的。因此總共進行了O(n*n)次比較，這個數字對所有情況都是一樣。只有交換次數是不同的。 #### 測試輸出結果  ### 冒泡排序算法 #### 基本思想 如果把要排序的數組設想成一個垂直的柱體，其中最小的元素在頂部，最大的元素在底部，冒泡排序算法就容易理解了。數組從底部往上掃描，如果相鄰兩個元素逆序，則交換兩者。首先，比較數據項data[n-1]和data[n-2]，如果逆序，則互序，接著比較data[n-2]和data[n-3],構建需要發生它們的順序，一直到時data[1]和data[0].這樣最小的元素就到了數組的頂部。然而，這還只是第一次遍歷數組。再次對數組掃描，比較剩下的數據項，當需要時交換它們。但是這一次，最后比較的數據項是data[2]和data[1],因為最小的元素已經在合適的位置上，也就是位置0.第二次冒泡將第二個最小元素入在數組的第二個位置。即位置1.這一過程繼續下，直到時最后一次，此時只比較一次，即比較data[n-1]與data[n-2],這時有可能要一次換。 算法的偽代碼如下： ~~~ bubblesort(data[],n) for (i =0; i<n-1; i++) for(j =n-1; j>i;--j) 如果兩者逆序，交換位置j和j-1的元素 ~~~ 下面是冒泡排序的實現： ~~~ template <class genType> void bubblesort( genType data[], int n) { for( int i =0; i<n-1; i++) { for (int j =n-1; j>i;--j){ if(data[j]<data[j-1]){ genType temp = data[least]; data[least] = data[i]; data[i] = temp; } } } } ~~~ 冒泡排序的主要缺點是元素需要要一步步地向上冒泡直到數組的頂部，這是非常花時間的。算法每次都考慮相鄰兩個元素尋，若為逆序，需要交換。如果元素需要從底部移到頂部，它和數組中的每一個元素交換位置。而不能像選擇排序那樣跳過它們。 #### 算法分析 算法中比較的次數在各種條件下都是相同的，都 等于內層for循環的總迭代次數O(n*n).最好情況是所有元素都已排好序，此時不需要交換。 #### 測試輸出結果  ### 比較三種算法性能 插入排序，選擇排序，冒泡排序，這三種算法，當輸入一個數組，運行100000次，所花費時間如圖所下：  ### 參考文獻 [1] Adam Drozdek , Data Structures and Algorithms in C++,Third Edition. [2] Thomas H.Cormnen ,Charles E.Lesersion et.al .Introduction to Algorithms second Edition. 轉載請注明出處：[http://blog.csdn.net/ songzitea/article/details/8864084]