首先對排序有個宏觀的了解， 排序的思想是這樣的，將有序的記錄序列（或稱）按照一定的關(guān)鍵字，將一個序列排列成想要得到的一個新的序列。基本上現(xiàn)在的排序可以區(qū)分以下幾類：內(nèi)排序和外排序，穩(wěn)定排序和不穩(wěn)定排序。

內(nèi)排序：整個排序過程，所有元素調(diào)到內(nèi)存中進行的排序。內(nèi)排序效率用比較次數(shù)來衡量。

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

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

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

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

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

那么，舉幾個例子，講解下其應(yīng)用的相關(guān)排序算法。

（一）冒泡排序

         思想：反復(fù)掃描待排序序列，在掃描的過程中順次比較相鄰的兩個元素的大小，若逆序就交換位置。第一趟，從第一個數(shù)據(jù)開始，比較相鄰的兩個數(shù)據(jù)，（以升序為例）如果大就交換，得到一個最大數(shù)據(jù)在末尾；然后進行第二趟，只掃描前n-1個元素，得到次大的放在倒數(shù)第二位。以此類推，最后得到升序序列。如果在掃描過程中，發(fā)現(xiàn)沒有交換，說明已經(jīng)排好序列，直接終止掃描。所以最多進行n-1趟掃描。

例：設(shè)記錄key集合k={50，36，66，76，95，12，25，36}，排序過程如下：

最后排序結(jié)果為紅色背景的順序。

（二）簡單選擇排序

思想：第一趟時，從第一個記錄開始，通過n – 1次關(guān)鍵字的比較，從n個記錄中選出關(guān)鍵字最小（大）的記錄，并和第一個（可以是最后一個）記錄進行交換。第二趟從第二個記錄開始，選擇最小（大）的和第二個記錄交換。以此類推，直至全部排序完畢。

例：設(shè)記錄key集合k={50，36，66，76，95，12，25，36}，排序過程如下：

（三）快速排序

思想：冒泡排序一次只能消除一個逆序，為了能一次消除多個逆序，采用快速排序。以一個關(guān)鍵字為軸，從左從右依次與其進行對比，然后交換，第一趟結(jié)束后，可以把序列分為兩個子序列，然后再分段進行快速排序，達到高效。

例：設(shè)記錄的key集合k={50，36，66，76，36，12，25，95}，每次以集合中第一個key為基準(zhǔn)的快速排序過程如下：

（四）直接插入排序

思想：最基本的插入排序，將第i個插入到前i-1個中的適當(dāng)位置。

例： 設(shè)文件記錄的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個排序算法，是否理解了呢？好了，其他排序算法的分析我們以后有時間再講。當(dāng)然，理解了這種套路的話，或者你來總結(jié)一下。