數據結構排序算法有哪些常用的
時間：2018-01-11 來源：未知
首先對排序有個宏觀的了解， 排序的思想是這樣的，將有序的記錄序列(或稱)按照一定的關鍵字，將一個序列排列成想要得到的一個新的序列。基本上現在的排序可以區分以下幾類：內排序和外排序，穩定排序和不穩定排序。
內排序：整個排序過程，所有元素調到內存中進行的排序。內排序效率用比較次數來衡量。
外排序：數據量較大的情況下，需要借助外部存儲設備才能完成排序。外排序用讀/寫外存的次數來衡量效率，塊與塊之間不能保證有序。
排序的性能比較基本的是其穩定性，之后就是時間復雜度，空間復雜度了。
穩定排序：對于相的元素來說，在排序之前和之后的順序是一樣的。
不穩定排序：對于相同的元素來說，在排序之前和之后順序發生了變化。
根據使用的實際情況，用到內排序的還是較多，所以重點討論幾種內排序。幾種常見的排序算法大概有以下圖中所示幾種：
那么，舉幾個例子，講解下其應用的相關排序算法。
(一)冒泡排序
思想：反復掃描待排序序列，在掃描的過程中順次比較相鄰的兩個元素的大小，若逆序就交換位置。第一趟，從第一個數據開始，比較相鄰的兩個數據，(以升序為例)如果大就交換，得到一個大數據在末尾;然后進行第二趟，只掃描前n-1個元素，得到次大的放在倒數第二位。以此類推，后得到升序序列。如果在掃描過程中，發現沒有交換，說明已經排好序列，直接終止掃描。所以多進行n-1趟掃描。
例：設記錄key集合k={50，36，66，76，95，12，25，36}，排序過程如下：
后排序結果為紅色背景的順序。
(二)簡單選擇排序
思想：第一趟時，從第一個記錄開始，通過n – 1次關鍵字的比較，從n個記錄中選出關鍵字小(大)的記錄，并和第一個(可以是后一個)記錄進行交換。第二趟從第二個記錄開始，選擇小(大)的和第二個記錄交換。以此類推，直至全部排序完畢。
例：設記錄key集合k={50，36，66，76，95，12，25，36}，排序過程如下：
(三)快速排序
思想：冒泡排序一次只能消除一個逆序，為了能一次消除多個逆序，采用快速排序。以一個關鍵字為軸，從左從右依次與其進行對比，然后交換，第一趟結束后，可以把序列分為兩個子序列，然后再分段進行快速排序，達到高效。
例：設記錄的key集合k={50，36，66，76，36，12，25，95}，每次以集合中第一個key為基準的快速排序過程如下：
(四)直接插入排序
思想：基本的插入排序，將第i個插入到前i-1個中的適當位置。
例： 設文件記錄的key集合k={50，36，66，76，95，12，25，36}(考慮到對記錄次key排序的情況，允許多個key相同。如此例中有2個key為36，后一個表示成36，以示區別)，按直接插入排序方法對k的排序過程如下：k={50，36，66，76，95，12，25，36}
上面呢，通過例題加圖示的方式，簡單的分析了其中的4個排序算法，是否理解了呢?好了，其他排序算法的分析我們以后有時間再講。當然，理解了這種套路的話，或者你來總結一下。
