基礎排序算法總結 · 點滴算法

# 穩定性概念 ?????? 假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，則稱這種排序算法是穩定的；否則稱為不穩定的。選擇排序、快速排序、希爾排序、堆排序不是穩定的排序算法，冒泡排序、插入排序、歸并排序和基數排序是穩定的排序算法。 ![](https://box.kancloud.cn/2016-06-07_575683a458e55.jpg) # [一、冒泡排序](http://blog.csdn.net/u013074465/article/details/44339187) 冒泡排序的普通思路： ??????? 比較相鄰的兩個元素，交換元素使得小元素在前、大元素在后。 ??????? 第一次排序將對n個元素進行n-1次比較，將最大的元素放到了數組的最后邊； ??????? 第二次排序將剩下的n-1個元素進行n-2次比較，將第二大的數放在數組的倒數第二個位置； ?? ? ?? 依次進行該過程； ??????? 第n-1趟則所有元素都是有序的，即完成了排序。改進的冒泡排序： ?????? 設置一個標志用來記錄某次遍歷數組中，有沒有發生元素的交換；如果發生了元素的交換，說明數組還沒有完全有序；如果沒發生元素交換，說明整個數組已經有序，則排序結束。 ????? 通過設置這個標志可以減少元素的比較次數。 # [二、插入排序](http://blog.csdn.net/u013074465/article/details/42043665) 思路： ?????? 每次將數組右邊一個待排序的數據插入到數組左邊已經排序的序列中，直到整個數組都是有序的。 ?????? 某次排序，將數組分為已排序序列A（數組左邊部分）和未排序序列B（數組右邊部分）；每次排序依次從B序列中取一個元素b，讓其依次與A序列的元素比較（依次從A序列的最右一個元素向左開始比較），為數b在A序列中尋找一個合適的插入位置，將b插入A。 ?????? 由于每次都是將大于b的元素右移動，然后將b放在該位置，因此不會發生相同元素的交換，因此是穩定的。 # [三、希爾排序](http://blog.csdn.net/u013074465/article/details/42043665) 思路： ?????? 將數組分割為若干個子序列，每個序列中的元素都是由相隔某個增量的元素組成。 ?????? 對每個子序列分別進行插入排序；然后依次縮減增量，再次重復上述排序。 ?????? 直到增量為1后，進行依次排序，這時整個數組就是有序的，排序結束。希爾排序是對相隔若干距離的數據進行直接插入排序的。 ?????? 一次插入排序是穩定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最后其穩定性就會被打亂，所以shell排序是**不穩定的。 # [四、選擇排序](http://blog.csdn.net/u013074465/article/details/44342373) 思路（假設非遞減排序）： ?????? 類似于插入排序，將序列分為了有序的和無序的子序列，不過這里不是依次選擇一個未排序的元素插入已排序序列；而是找出未排序序列中最小的元素，將其與已經排序的序列緊鄰的那個元素交換（初始已排序序列為0）。例如5，8，5，2，9序列的第一趟排序是將第一個5與2交換，那么，兩個5的次序就交換了，所以選擇排序不穩定。 # [五、歸并排序](http://blog.csdn.net/u013074465/article/details/42043967) 思路： ??????? 當一個數組的左部分有序、右部分也有序時，只要將這兩部分合并即可完成排序。而如何使得左、右部分分別有序呢？遞歸使用歸并排序即可。 ?????? 在歸并的過程中，主要的操作是合并兩個有序的序列，在合并中，如果兩個元素相等，不會對它們交換，因此穩定。 # [六、快速排序](http://blog.csdn.net/u013074465/article/details/42083607) ??????? 上述鏈接的文章中給出了詳細的思路和過程。 ??????? 快速排序被認為是所有同數量級(O(nlogn))排序方法中，平均性能最好的。 **時間復雜度：** ?????? 但是，如果初始記錄序列有序時，以左側元素為樞紐的快速排序算法將退化為冒泡排序，其時間復雜度為O(n ^ 2)；在初始序列有序或逆序情況下，每次排序需要n * n次比較，因此算法復雜度為O(n ^ 2)。 **空間復雜度：** ????? 快速排序需要一個棧空間來實現遞歸（即使是[非遞歸算法](http://blog.csdn.net/u013074465/article/details/42083607#t3)，它也需要一個輔助棧來保存下次帶排序數組的下標范圍）。若每一趟排序都將記錄序列均勻分割為長度接近相等的兩個子序列，則平均情況下棧的最大深度為logn + 1（包括最外層參數進棧），但是若每趟排序后，樞紐位置均偏向子序列的一端（初始序列有序或逆序），則為最壞情況，棧的最大深度為n。 # [七、堆排序](http://blog.csdn.net/u013074465/article/details/42043697) ? ? ?? 如果要按照非遞減順序排序，那么要使用大根堆；按照非遞增順序排序，要使用小根堆。假設按照非遞減順序排列，那么排序的思路是： ??????? 首先建立一個大根堆； ??????? 刪除大根堆的根元素（說是刪除，其實是利用了堆最后的那個空間來存儲該元素，即將根元素與堆尾部元素交換，這樣當堆刪除完后，那么存儲空間就是有序的了）； ????? ? 每次交換的根元素和尾元素后要進行下濾操作，使得滿足大根堆。 ??????? 排序過程就是刪除根元素并上濾的過程，上濾中可能會讓相等元素位置改變，因此不穩定。 # 八、線性時間排序以上將的都是基于比較的排序，時間復雜度上界為O(n ^ 2)，下界為O(nlogn)。下面介紹幾種線性排序： ### 1、基數排序 ?????? 基數排序是按照低位先排序，然后收集；再按照次低位排序，然后再收集；依次類推，直到最高位。有時候有些屬性是有優先級順序的，先按低優先級排序，再按高優先級排序，最后的次序就是高優先級高的在前，高優先級相同的低優先級高的在前。基數排序基于分別排序，分別收集，它在每一位排序中依賴于一個穩定的排序算法，所以基數排序是穩定的排序算法。 ?????? 給定n個d位數，其中每個數位有k個可能的取值。那么需要d輪排序，所以基數排序耗時為d(n + k)，而d為常數，所以基數排序復雜度為O(n + k)。 ### 2、計數排序假設n個輸入元素中每個都是在0到k區間的整數(k是某個整數)。當k = O(n)時，排序的運行時間為O(n)。 ### 3、桶排序 ?????? 假設輸入數據服從均勻分布，平均情況下其時間代價為O(n)。和計數排序類似，計數排序假設數據都是一個小區間內的整數，桶排序則假定輸入由一個隨機過程產生，該過程將元素均勻、獨立地分布在[0,1)區間內。 ?????? 桶排序將[0,1)區間劃分為n個相同大小的子區間，稱為桶；然后，將n個數分別放入到各個桶中，因為輸入數據是均勻分布的，所以不會出現很多數落在一個桶內的情況。為了得到輸出結果，先對每個桶中數進行排序（例如，利用插入排序），然后遍歷每個桶，按照次序把各個桶內的元素列出來即可。