首先對排序有個宏觀的了解， 排序的思想是這樣的，將有序的記錄序列（或稱）按照一定的關鍵字，將一個序列排列成想要得到的一個新的序列?；旧犀F在的排序可以區(qū)分以下幾類：內排序和外排序，穩(wěn)定排序和不穩(wěn)定排序。

內排序：整個排序過程，所有元素調到內存中進行的排序。內排序效率用比較次數來衡量。

外排序：數據量較大的情況下，需要借助外部存儲設備才能完成排序。外排序用讀/寫外存的次數來衡量效率，塊與塊之間不能保證有序。

排序的性能比較最基本的是其穩(wěn)定性，之后就是時間復雜度，空間復雜度了。

穩(wěn)定排序：對于相的元素來說，在排序之前和之后的順序是一樣的。

不穩(wěn)定排序：對于相同的元素來說，在排序之前和之后順序發(fā)生了變化。

根據使用的實際情況，用到內排序的還是較多，所以重點討論幾種內排序。幾種常見的排序算法大概有以下圖中所示幾種：

那么，舉幾個例子，講解下其應用的相關排序算法。

（一）冒泡排序

         思想：反復掃描待排序序列，在掃描的過程中順次比較相鄰的兩個元素的大小，若逆序就交換位置。第一趟，從第一個數據開始，比較相鄰的兩個數據，（以升序為例）如果大就交換，得到一個最大數據在末尾；然后進行第二趟，只掃描前n-1個元素，得到次大的放在倒數第二位。以此類推，最后得到升序序列。如果在掃描過程中，發(fā)現沒有交換，說明已經排好序列，直接終止掃描。所以最多進行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，以示區(qū)別），按直接插入排序方法對k的排序過程如下：k={50，36，66，76，95，12，25，36}

上面呢，通過例題加圖示的方式，簡單的分析了其中的4個排序算法，是否理解了呢？好了，其他排序算法的分析我們以后有時間再講。當然，理解了這種套路的話，或者你來總結一下。