一、氣泡排序

已知一組無序資料a[1]、a[2]、……a[n]，需將其按升序排列。首先比較a[1]與 a[2]的值，若a[1]大於a[2]則交換 兩者的值，否則不變。再比較a[2]與a[3]的值，若a[2]大於a[3]則交換兩者的值，否則不變。再比 較a[3]與a[4]，以此 類推，最後比較a[n-1]與a[n]的值。這樣處理一輪後，a[n]的值一定是這組資料中最大的。再對a[1]~a[n- 1]以相同方法 處理一輪，則a[n-1]的值一定是a[1]~a[n-1]中最大的。再對a[1]~a[n-2]以相同方法處理一輪，以此類推。共處理 n-1 輪 後a[1]、a[2]、……a[n]就以升序排列了。

優點：穩定；

缺點：慢，每次只能移動相鄰兩個資料。

二、選擇排序

每一趟從待排序的資料元素中選出最小（或最大）的一個元素，順序放在已排好序的數列的最後，直到全部待排序的數 據元素排完。

選擇排序是不穩定的排序方法。

n 個記錄的檔案的直接選擇排序可經過n-1 趟直接選擇排序得到有序結果：

①初始狀態：無序區為R[1..n]，有序區為空。

②第1 趟排序 在無序區R[1..n]中選出關鍵字最小的記錄R[k]，將它與無序區的第1 個記錄R[1]交換，使R[1..1]和R[2..n]分別變 為記錄個數增加1 個的新有序區和記錄個數減少1 個的新無序區。

第i 趟排序開始時，當前有序區和無序區分別為R[1..i-1]和R(1≤i≤n-1)。該趟 排序從當前無序區中選出關鍵字最 小的記錄 R[k]，將它與無序區的第1 個記錄R 交換，使R[1..i]和R 分別變為記錄個數增加1 個的新有序區和記錄個數減少 1 個的新無序區。

這樣，n 個記錄的檔案的直接選擇排序可經過n-1 趟直接選擇排序得到有序結果。

優點：移動資料的次數已知（n-1 次）；

缺點：比較次數多。

三、插入排序

已知一組升序排列資料a[1]、a[2]、……a[n]，一組無序資料b[1]、 b[2]、……b[m]，需將二者合併成一個升序數列。 首先比較b[1]與a[1]的值，若b[1]大於a[1]，則跳過，比較b[1]與a[2]的值， 若b[1]仍然大於a[2]，則繼續跳過，直 到b[1]小於a 陣列中某一資料a[x]，則將a[x]~a[n]分別向後移動一位，將b[1]插入到原來 a[x]的位置這就完成了b[1] 的插入。b[2]~b[m]用相同方法插入。（若無陣列a，可將b[1]當作n=1 的陣列a）

優點：穩定，快；

缺點：比較次數不一定，比較次數越少，插入點後的資料移動越多，特別是當資料總量龐大的時候，但用連結串列可以解決 這個問題。

四、縮小增量排序

由在1959 年提出，又稱排序(shell 排序)。

已知一組無序資料a[1]、a[2]、……a[n]，需將其按升序排列。發現當n 不大時，插入 排序的效果很好。首先取一增 量d(d<n)，將a[1]、a[1+d]、a[1+2d]……列為第一組，a[2]、a[2+d]、 a[2+2d]……列為第二組……，a[d]、a[2d]、a[3d]……="" 列為最後一組以次類推，在各組內用插入排序，然後取d"<d，重複上述操="" 作，直到d="1。"

優點：快，資料移動少；=""

缺點：不穩定，d="" 的取值是多少，應取多少個不同的值，都無法確切知道，只能憑經驗來取。=""

五、快速排序=""

快速排序是氣泡排序的改進版，是目前已知的最快的排序方法。

="" 已知一組無序資料a[1]、a[2]、……a[n]，需將其按升序排列。首先任取資料a[x]="" 作為基準。比較a[x]與其它資料並="" 排序，使a[x]排在資料的第k="" 位，並且使a[1]~a[k-1]中的每一個數="" 據a[x]，然後採 用分治的策略分別對a[1]~a[k-1]和a[k+1]~a[n] 兩組資料進行快速排序。

優點：極快，資料移動少；

缺點：不穩定。

排序演算法一般分為以下幾種：

（1）非線性時間比較類排序：交換類排序（快速排序和氣泡排序）、插入類排序（簡單插入排序和希爾排序）、選擇類排序（簡單選擇排序和堆排序）、歸併排序（二路歸併排序和多路歸併排序）；

（2）線性時間非比較類排序：計數排序、基數排序和桶排序。

一、氣泡排序

已知一組無序資料a[1]、a[2]、……a[n]，需將其按升序排列。首先比較a[1]與 a[2]的值，若a[1]大於a[2]則交換 兩者的值，否則不變。再比較a[2]與a[3]的值，若a[2]大於a[3]則交換兩者的值，否則不變。再比 較a[3]與a[4]，以此 類推，最後比較a[n-1]與a[n]的值。這樣處理一輪後，a[n]的值一定是這組資料中最大的。再對a[1]~a[n- 1]以相同方法 處理一輪，則a[n-1]的值一定是a[1]~a[n-1]中最大的。再對a[1]~a[n-2]以相同方法處理一輪，以此類推。共處理 n-1 輪 後a[1]、a[2]、……a[n]就以升序排列了。

優點：穩定；

缺點：慢，每次只能移動相鄰兩個資料。

二、選擇排序

每一趟從待排序的資料元素中選出最小（或最大）的一個元素，順序放在已排好序的數列的最後，直到全部待排序的數 據元素排完。

選擇排序是不穩定的排序方法。

n 個記錄的檔案的直接選擇排序可經過n-1 趟直接選擇排序得到有序結果：

①初始狀態：無序區為R[1..n]，有序區為空。

②第1 趟排序 在無序區R[1..n]中選出關鍵字最小的記錄R[k]，將它與無序區的第1 個記錄R[1]交換，使R[1..1]和R[2..n]分別變 為記錄個數增加1 個的新有序區和記錄個數減少1 個的新無序區。

第i 趟排序開始時，當前有序區和無序區分別為R[1..i-1]和R(1≤i≤n-1)。該趟 排序從當前無序區中選出關鍵字最 小的記錄 R[k]，將它與無序區的第1 個記錄R 交換，使R[1..i]和R 分別變為記錄個數增加1 個的新有序區和記錄個數減少 1 個的新無序區。

這樣，n 個記錄的檔案的直接選擇排序可經過n-1 趟直接選擇排序得到有序結果。

優點：移動資料的次數已知（n-1 次）；

缺點：比較次數多。

三、插入排序

已知一組升序排列資料a[1]、a[2]、……a[n]，一組無序資料b[1]、 b[2]、……b[m]，需將二者合併成一個升序數列。 首先比較b[1]與a[1]的值，若b[1]大於a[1]，則跳過，比較b[1]與a[2]的值， 若b[1]仍然大於a[2]，則繼續跳過，直 到b[1]小於a 陣列中某一資料a[x]，則將a[x]~a[n]分別向後移動一位，將b[1]插入到原來 a[x]的位置這就完成了b[1] 的插入。b[2]~b[m]用相同方法插入。（若無陣列a，可將b[1]當作n=1 的陣列a）

優點：穩定，快；

缺點：比較次數不一定，比較次數越少，插入點後的資料移動越多，特別是當資料總量龐大的時候，但用連結串列可以解決 這個問題。

四、縮小增量排序

由希爾在1959 年提出，又稱希爾排序(shell 排序)。

已知一組無序資料a[1]、a[2]、……a[n]，需將其按升序排列。發現當n 不大時，插入 排序的效果很好。首先取一增 量d(d<n)，將a[1]、a[1+d]、a[1+2d]……列為第一組，a[2]、a[2+d]、 a[2+2d]……列為第二組……，a[d]、a[2d]、a[3d]……="" 列為最後一組以次類推，在各組內用插入排序，然後取d"<d，重複上述操="" 作，直到d="1。"

優點：快，資料移動少；=""

缺點：不穩定，d="" 的取值是多少，應取多少個不同的值，都無法確切知道，只能憑經驗來取。=""

五、快速排序=""

快速排序是氣泡排序的改進版，是目前已知的最快的排序方法。

="" 已知一組無序資料a[1]、a[2]、……a[n]，需將其按升序排列。首先任取資料a[x]="" 作為基準。比較a[x]與其它資料並="" 排序，使a[x]排在資料的第k="" 位，並且使a[1]~a[k-1]中的每一個數="" 據a[x]，然後採 用分治的策略分別對a[1]~a[k-1]和a[k+1]~a[n] 兩組資料進行快速排序。

優點：極快，資料移動少；

缺點：不穩定。