各種排序算法：冒擇路(入)兮(稀)快歸堆，桶式排序，基數(shù)排序
冒泡排序，選擇排序，插入排序，稀爾排序，快速排序，歸并排序，堆排序，桶式排序，基數(shù)排序
一、冒泡排序(BubbleSort)
1. 基本思想：
兩兩比較待排序數(shù)據(jù)元素的大小，發(fā)現(xiàn)兩個數(shù)據(jù)元素的次序相反時即進(jìn)行交換，直到?jīng)]有反序的數(shù)據(jù)元素為止。
2. 排序過程：
設(shè)想被排序的數(shù)組R［1..N］垂直豎立，將每個數(shù)據(jù)元素看作有重量的氣泡，根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R，凡掃描到違反本原則的輕氣泡，就使其向上"漂浮"，如此反復(fù)進(jìn)行，直至最后任何兩個氣泡都是輕者在上，重者在下為止。
【示例】：
49 13 13 13 13 13 13 13
38 49 27 27 27 27 27 27
65 38 49 38 38 38 38 38
97 65 38 49 49 49 49 49
76 97 65 49 49 49 49 49
13 76 97 65 65 65 65 65
27 27 76 97 76 76 76 76
49 49 49 76 97 97 97 97
java代碼實現(xiàn)：
/**
* 冒泡排序：執(zhí)行完一次內(nèi)for循環(huán)后，最小的一個數(shù)放到了數(shù)組的最前面（跟那一個排序算法* 不一樣）。相鄰位置之間交換
*/
public class BubbleSort {
/**
* 排序算法的實現(xiàn)，對數(shù)組中指定的元素進(jìn)行排序
* @param array 待排序的數(shù)組
* @param from 從哪里開始排序
* @param end 排到哪里
* @param c 比較器
*/
public void bubble(Integer[] array, int from, int end) {
//需array.length - 1輪比較
for (int k = 1; k < end - from + 1; k++) {
//每輪循環(huán)中從最后一個元素開始向前起泡，直到i=k止，即i等于輪次止
for (int i = end - from; i >= k; i--) {
//按照一種規(guī)則（后面元素不能小于前面元素）排序
if ((array[i].compareTo(array[i - 1])) < 0) {
//如果后面元素小于了（當(dāng)然是大于還是小于要看比較器實現(xiàn)了）前面的元素，則前后交換
swap(array, i, i - 1);
}
}
}
}
/**
* 交換數(shù)組中的兩個元素的位置
* @param array 待交換的數(shù)組
* @param i 第一個元素
* @param j 第二個元素
*/
public void swap(Integer[] array, int i, int j) {
if (i != j) {//只有不是同一位置時才需交換
Integer tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
/**
* 測試
* @param args
*/
public static void main(String[] args) {
Integer[] intgArr = { 7, 2, 4, 3, 12, 1, 9, 6, 8, 5, 11, 10 };
BubbleSort bubblesort = new BubbleSort();
bubblesort.bubble(intgArr,0,intgArr.length-1);
for(Integer intObj:intgArr){
System.out.print(intObj + " ");
}
}
}
另外一種實現(xiàn)方式：
/**
冒泡排序：執(zhí)行完一次內(nèi)for循環(huán)后，最大的一個數(shù)放到了數(shù)組的最后面。相鄰位置之間交換
*/
public class BubbleSort2{
public static void main(String[] args){
int[] a = {3,5,9,4,7,8,6,1,2};
BubbleSort2 bubble = new BubbleSort2();
bubble.bubble(a);
for(int num:a){
System.out.print(num + " ");
}
}
public void bubble(int[] a){
for(int i=a.length-1;i>0;i--){
for(int j=0;j<i;j++){
if(new Integer(a[j]).compareTo(new Integer(a[j+1]))>0){
swap(a,j,j+1);
}
}
}
}
public void swap(int[] a,int x,int y){
int temp;
temp=a[x];
a[x]=a[y];
a[y]=temp;
}
}
二、選擇排序
1. 基本思想：
每一趟從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。
2. 排序過程：
【示例】：
初始關(guān)鍵字 [49 38 65 97 76 13 27 49]
第一趟排序后 13 ［38 65 97 76 49 27 49]
第二趟排序后 13 27 ［65 97 76 49 38 49]
第三趟排序后 13 27 38 [97 76 49 65 49]
第四趟排序后 13 27 38 49 [49 97 65 76]
第五趟排序后 13 27 38 49 49 [97 97 76]
第六趟排序后 13 27 38 49 49 76 [76 97]
第七趟排序后 13 27 38 49 49 76 76 [ 97]
最后排序結(jié)果 13 27 38 49 49 76 76 97
java代碼實現(xiàn)：
/**
* 簡單選擇排序：執(zhí)行完一次內(nèi)for循環(huán)后最小的一個數(shù)放在了數(shù)組的最前面。
*/
public class SelectSort {
/**
* 排序算法的實現(xiàn)，對數(shù)組中指定的元素進(jìn)行排序
* @param array 待排序的數(shù)組
* @param from 從哪里開始排序
* @param end 排到哪里
* @param c 比較器
*/
public void select(Integer[] array) {
int minIndex;//最小索引
/*
* 循環(huán)整個數(shù)組（其實這里的上界為 array.length - 1 即可，因為當(dāng) i= array.length-1
* 時，最后一個元素就已是最大的了，如果為array.length時，內(nèi)層循環(huán)將不再循環(huán)），每輪假設(shè)
* 第一個元素為最小元素，如果從第一元素后能選出比第一個元素更小元素，則讓讓最小元素與第一
* 個元素交換
*/
for (int i=0; i<array.length; i++) {
minIndex = i;//假設(shè)每輪第一個元素為最小元素
//從假設(shè)的最小元素的下一元素開始循環(huán)
for (int j=i+1;j<array.length; j++) {
//如果發(fā)現(xiàn)有比當(dāng)前array[smallIndex]更小元素，則記下該元素的索引于smallIndex中
if ((array[j].compareTo(array[minIndex])) < 0) {
minIndex = j;
}
}
//先前只是記錄最小元素索引，當(dāng)最小元素索引確定后，再與每輪的第一個元素交換
swap(array, i, minIndex);
}
}
public static void swap(Integer[] intgArr,int x,int y){
//Integer temp; //這個也行
int temp;
temp=intgArr[x];
intgArr[x]=intgArr[y];
intgArr[y]=temp;
}
/**
* 測試
* @param args
*/
public static void main(String[] args) {
Integer[] intgArr = { 5, 9, 1, 4, 2, 6, 3, 8, 0, 7 };
SelectSort insertSort = new SelectSort();
insertSort.select(intgArr);
for(Integer intObj:intgArr){
System.out.print(intObj + " ");
}
}
}
三、插入排序(Insertion Sort)
1. 基本思想：
每次將一個待排序的數(shù)據(jù)元素，插入到前面已經(jīng)排好序的數(shù)列中的適當(dāng)位置，使數(shù)列依然有序；直到待排序數(shù)據(jù)元素全部插入完為止。
2. 排序過程：
【示例】：
[初始關(guān)鍵字] [49] 38 65 97 76 13 27 49
J=2(38) [38 49] 65 97 76 13 27 49
J=3(65) [38 49 65] 97 76 13 27 49
J=4(97) [38 49 65 97] 76 13 27 49
J=5(76) [38 49 65 76 97] 13 27 49
J=6(13) [13 38 49 65 76 97] 27 49
J=7(27) [13 27 38 49 65 76 97] 49
J=8(49) [13 27 38 49 49 65 76 97]
java代碼實現(xiàn)：
/**
* 直接插入排序：
* 注意所有排序都是從小到大排。
*/
public class InsertSort {
/**
* 排序算法的實現(xiàn)，對數(shù)組中指定的元素進(jìn)行排序
* @param array 待排序的數(shù)組
* @param from 從哪里開始排序
* @param end 排到哪里
* @param c 比較器
*/
public void insert(Integer[] array, int from, int end) {
/*
* 第一層循環(huán)：對待插入（排序）的元素進(jìn)行循環(huán)
* 從待排序數(shù)組斷的第二個元素開始循環(huán)，到最后一個元素（包括）止
*/
for (int i=from+1; i<=end; i++) {
/*
* 第二層循環(huán)：對有序數(shù)組進(jìn)行循環(huán)，且從有序數(shù)組最第一個元素開始向后循環(huán)
* 找到第一個大于待插入的元素
* 有序數(shù)組初始元素只有一個，且為源數(shù)組的第一個元素，一個元素數(shù)組總是有序的
*/
for (int j = 0; j < i; j++) {
Integer insertedElem = array[i];//待插入到有序數(shù)組的元素
//從有序數(shù)組中最一個元素開始查找第一個大于待插入的元素
if ((array[j].compareTo(insertedElem)) > 0) {
//找到插入點后，從插入點開始向后所有元素后移一位
move(array, j, i - 1);
//將待排序元素插入到有序數(shù)組中
array[j] = insertedElem;
break;
}
}
}
//=======以下是java.util.Arrays的插入排序算法的實現(xiàn)
/*
* 該算法看起來比較簡潔一j點，有點像冒泡算法。
* 將數(shù)組邏輯上分成前后兩個集合，前面的集合是已經(jīng)排序好序的元素，而后面集合為待排序的
* 集合，每次內(nèi)層循從后面集合中拿出一個元素，通過冒泡的形式，從前面集合最后一個元素開
* 始往前比較，如果發(fā)現(xiàn)前面元素大于后面元素，則交換，否則循環(huán)退出
*
* 總感覺這種算術(shù)有點怪怪，既然是插入排序，應(yīng)該是先找到插入點，而后再將待排序的元素插
* 入到的插入點上，那么其他元素就必然向后移，感覺算法與排序名稱不匹，但返過來與上面實
* 現(xiàn)比，其實是一樣的，只是上面先找插入點，待找到后一次性將大的元素向后移，而該算法卻
* 是走一步看一步，一步一步將待排序元素往前移
*/
/*
for (int i = from; i <= end; i++) {
for (int j = i; j > from && c.compare(array[j - 1], array[j]) > 0; j--) {
swap(array, j, j - 1);
}
}
*/
}
/**
* 數(shù)組元素后移
* @param array 待移動的數(shù)組
* @param startIndex 從哪個開始移
* @param endIndex 到哪個元素止
*/
public void move(Integer[] array, int startIndex, int endIndex) {
for (int i = endIndex; i >= startIndex; i--) {
array[i+1] = array[i];
}
}
/**
* 測試
* @param args
*/
public static void main(String[] args) {
Integer[] intgArr = { 5, 9, 1, 4, 2, 6, 3, 8, 0, 7 };
InsertSort insertSort = new InsertSort();
insertSort.insert(intgArr,0,intgArr.length-1);
for(Integer intObj:intgArr){
System.out.print(intObj + " ");
}
}
}
四、稀爾排序
java代碼實現(xiàn)：
/**
* 插入排序----希爾排序：我們選擇步長為：15,7,3,1
* 我們選擇步長公式為：2^k-1,2^(k-1)-1,……,15,7,3,1 (2^4-1,2^3-1,2^2-1,2^1-1)
* 注意所有排序都是從小到大排。
*/
public class ShellSort {
/**
* 排序算法的實現(xiàn)，對數(shù)組中指定的元素進(jìn)行排序
* @param array 待排序的數(shù)組
* @param from 從哪里開始排序
* @param end 排到哪里
* @param c 比較器
*/
public void sort(Integer[] array, int from, int end) {
//初始步長，實質(zhì)為每輪的分組數(shù)
int step = initialStep(end - from + 1);
//第一層循環(huán)是對排序輪次進(jìn)行循環(huán)。(step + 1) / 2 - 1 為下一輪步長值
for (; step >= 1; step = (step + 1) / 2 - 1) {
//對每輪里的每個分組進(jìn)行循環(huán)
for (int groupIndex = 0; groupIndex < step; groupIndex++) {
//對每組進(jìn)行直接插入排序
insertSort(array, groupIndex, step, end);
}
}
}
/**
* 直接插入排序?qū)崿F(xiàn)
* @param array 待排序數(shù)組
* @param groupIndex 對每輪的哪一組進(jìn)行排序
* @param step 步長
* @param end 整個數(shù)組要排哪個元素止
* @param c 比較器
*/
public void insertSort(Integer[] array, int groupIndex, int step, int end) {
int startIndex = groupIndex;//從哪里開始排序
int endIndex = startIndex;//排到哪里
/*
* 排到哪里需要計算得到，從開始排序元素開始，以step步長，可求得下元素是否在數(shù)組范圍內(nèi)，
* 如果在數(shù)組范圍內(nèi)，則繼續(xù)循環(huán)，直到索引超現(xiàn)數(shù)組范圍
*/
while ((endIndex + step) <= end) {
endIndex += step;
}
// i為每小組里的第二個元素開始
for (int i = groupIndex + step; i <= end; i += step) {
for (int j = groupIndex; j < i; j += step) {
Integer insertedElem = array[i];
//從有序數(shù)組中最一個元素開始查找第一個大于待插入的元素
if ((array[j].compareTo(insertedElem)) >= 0) {
//找到插入點后，從插入點開始向后所有元素后移一位
move(array, j, i - step, step);
array[j] = insertedElem;
break;
}
}
}
}
/**
* 根據(jù)數(shù)組長度求初始步長
*
* 我們選擇步長的公式為：2^k-1,2^(k-1)-1,...,15,7,3,1 ，其中2^k 減一即為該步長序列，k
* 為排序輪次
*
* 初始步長：step = 2^k-1
* 初始步長約束條件：step < len - 1 初始步長的值要小于數(shù)組長度還要減一的值（因
* 為第一輪分組時盡量不要分為一組，除非數(shù)組本身的長度就小于等于4）
*
* 由上面兩個關(guān)系試可以得知：2^k - 1 < len - 1 關(guān)系式，其中k為輪次，如果把 2^k 表 達(dá)式
* 轉(zhuǎn)換成 step 表達(dá)式，則 2^k-1 可使用 (step + 1)*2-1 替換（因為 step+1 相當(dāng)于第k-1
* 輪的步長，所以在 step+1 基礎(chǔ)上乘以 2 就相當(dāng)于 2^k 了），即步長與數(shù)組長度的關(guān)系不等式為
* (step + 1)*2 - 1 < len -1
*
* @param len 數(shù)組長度
* @return
*/
public static int initialStep(int len) {
/*
* 初始值設(shè)置為步長公式中的最小步長，從最小步長推導(dǎo)出最長初始步長值，即按照以下公式來推:
* 1,3,7,15,...,2^(k-1)-1,2^k-1
* 如果數(shù)組長度小于等于4時，步長為1，即長度小于等于4的數(shù)組不用分組，此時直接退化為直接插入排序
*/
int step = 1;
//試探下一個步長是否滿足條件，如果滿足條件，則步長置為下一步長
while ((step + 1) * 2 - 1 < len - 1) {
step = (step + 1) * 2 - 1;
}
System.out.println("初始步長 : " + step);
return step;
}
/**
* 以指定的步長將數(shù)組元素后移，步長指定每個元素間的間隔
* @param array 待排序數(shù)組
* @param startIndex 從哪里開始移
* @param endIndex 到哪個元素止
* @param step 步長
*/
protected final void move(Integer[] array, int startIndex, int endIndex, int step) {
for (int i = endIndex; i >= startIndex; i -= step) {
array[i + step] = array[i];
}
}
/**
* 測試
* @param args
*/
public static void main(String[] args) {
Integer[] intgArr = { 5, 9, 1, 4, 8, 2, 6, 3, 7, 0 };
ShellSort shellSort = new ShellSort();
shellSort.sort(intgArr,0,intgArr.length-1);
for(Integer intObj:intgArr){
System.out.print(intObj + " ");
}
}
}
五、快速排序（Quick Sort）
1. 基本思想：
在當(dāng)前無序區(qū)R[1..H]中任取一個數(shù)據(jù)元素作為比較的"基準(zhǔn)"(不妨記為X)，用此基準(zhǔn)將當(dāng)前無序區(qū)劃分為左右兩個較小的無序區(qū)：R[1..I-1]和R[I+1..H]，且左邊的無序子區(qū)中數(shù)據(jù)元素均小于等于基準(zhǔn)元素，右邊的無序子區(qū)中數(shù)據(jù)元素均大于等于基準(zhǔn)元素，而基準(zhǔn)X則位于最終排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，當(dāng)R[1..I-1]和R[I+1..H]均非空時，分別對它們進(jìn)行上述的劃分過程，直至所有無序子區(qū)中的數(shù)據(jù)元素均已排序為止。
2. 排序過程：
【示例】：
初始關(guān)鍵字 ［49 38 65 97 76 13 27 49］
一趟排序之后 ［27 38 13］ 49 ［76 97 65 49］
二趟排序之后 ［13］ 27 ［38］ 49 ［49 65］76 ［97］
三趟排序之后 13 27 38 49 49 ［65］76 97
最后的排序結(jié)果 13 27 38 49 49 65 76 97
各趟排序之后的狀態(tài)
java代碼實現(xiàn)：
/**
* 快速排序：
*/
public class QuickSort {
/**
* 排序算法的實現(xiàn)，對數(shù)組中指定的元素進(jìn)行排序
* @param array 待排序的數(shù)組
* @param from 從哪里開始排序
* @param end 排到哪里
* @param c 比較器
*/
//定義了一個這樣的公有方法sort，在這個方法體里面執(zhí)行私有方法quckSort（這種方式值得借鑒）。
public void sort(Integer[] array, int from, int end) {
quickSort(array, from, end);
}
/**
* 遞歸快速排序?qū)崿F(xiàn)
* @param array 待排序數(shù)組
* @param low 低指針
* @param high 高指針
* @param c 比較器
*/
private void quickSort(Integer[] array, int low, int high) {
/*
* 如果分區(qū)中的低指針小于高指針時循環(huán)；如果low=higth說明數(shù)組只有一個元素，無需再處理；
* 如果low > higth，則說明上次樞紐元素的位置pivot就是low或者是higth，此種情況
* 下分區(qū)不存，也不需處理
*/
if (low < high) {
//對分區(qū)進(jìn)行排序整理
//int pivot = partition1(array, low, high);
int pivot = partition2(array, low, high);
//int pivot = partition3(array, low, high);
/*
* 以pivot為邊界，把數(shù)組分成三部分[low, pivot - 1]、[pivot]、[pivot + 1, high]
* 其中[pivot]為樞紐元素，不需處理，再對[low, pivot - 1]與[pivot + 1, high]
* 各自進(jìn)行分區(qū)排序整理與進(jìn)一步分區(qū)
*/
quickSort(array, low, pivot - 1);
quickSort(array, pivot + 1, high);
}
}
/**
* 實現(xiàn)一
*
* @param array 待排序數(shù)組
* @param low 低指針
* @param high 高指針
* @param c 比較器
* @return int 調(diào)整后中樞位置
*/
private int partition1(Integer[] array, int low, int high) {
Integer pivotElem = array[low];//以第一個元素為中樞元素
//從前向后依次指向比中樞元素小的元素，剛開始時指向中樞，也是小于與大小中樞的元素的分界點
int border = low;
/*
* 在中樞元素后面的元素中查找小于中樞元素的所有元素，并依次從第二個位置從前往后存放
* 注，這里最好使用i來移動，如果直接移動low的話，最后不知道數(shù)組的邊界了，但后面需要
* 知道數(shù)組的邊界
*/
for (int i = low + 1; i <= high; i++) {
//如果找到一個比中樞元素小的元素
if ((array[i].compareTo(pivotElem)) < 0) {
swap(array, ++border, i);//border前移，表示有小于中樞元素的元素
}
}
/*
* 如果border沒有移動時說明說明后面的元素都比中樞元素要大，border與low相等，此時是
* 同一位置交換，是否交換都沒關(guān)系；當(dāng)border移到了high時說明所有元素都小于中樞元素，此
* 時將中樞元素與最后一個元素交換即可，即low與high進(jìn)行交換，大的中樞元素移到了 序列最
* 后；如果 low <minIndex< high，表 明中樞后面的元素前部分小于中樞元素，而后部分大于
* 中樞元素，此時中樞元素與前部分?jǐn)?shù)組中最后一個小于它的元素交換位置，使得中樞元素放置在
* 正確的位置
*/
swap(array, border, low);
return border;
}
/**
* 實現(xiàn)二
*
* @param array 待排序數(shù)組
* @param low 待排序區(qū)低指針
* @param high 待排序區(qū)高指針
* @param c 比較器
* @return int 調(diào)整后中樞位置
*/
private int partition2(Integer[] array, int low, int high) {
int pivot = low;//中樞元素位置，我們以第一個元素為中樞元素
//退出條件這里只可能是 low = high
while (true) {
if (pivot != high) {//如果中樞元素在低指針位置時，我們移動高指針
//如果高指針元素小于中樞元素時，則與中樞元素交換
if ((array[high].compareTo(array[pivot])) < 0) {
swap(array, high, pivot);
//交換后中樞元素在高指針位置了
pivot = high;
} else {//如果未找到小于中樞元素，則高指針前移繼續(xù)找
high--;
}
} else {//否則中樞元素在高指針位置
//如果低指針元素大于中樞元素時，則與中樞元素交換
if ((array[low].compareTo(array[pivot])) > 0) {
swap(array, low, pivot);
//交換后中樞元素在低指針位置了
pivot = low;
} else {//如果未找到大于中樞元素，則低指針后移繼續(xù)找
low++;
}
}
if (low == high) {
break;
}
}
//返回中樞元素所在位置，以便下次分區(qū)
return pivot;
}
/**
* 實現(xiàn)三
*
* @param array 待排序數(shù)組
* @param low 待排序區(qū)低指針
* @param high 待排序區(qū)高指針
* @param c 比較器
* @return int 調(diào)整后中樞位置
*/
private int partition3(Integer[] array, int low, int high) {
int pivot = low;//中樞元素位置，我們以第一個元素為中樞元素
low++;
//----調(diào)整高低指針?biāo)赶虻脑仨樞颍研∮谥袠性氐囊频角安糠郑笥谥袠性氐囊频胶竺娌糠?nbsp;
//退出條件這里只可能是 low = high
while (true) {
//如果高指針未超出低指針
while (low < high) {
//如果低指針指向的元素大于或等于中樞元素時表示找到了，退出，注：等于時也要后移
if ((array[low].compareTo(array[pivot])) >= 0) {
break;
} else {//如果低指針指向的元素小于中樞元素時繼續(xù)找
low++;
}
}
while (high > low) {
//如果高指針指向的元素小于中樞元素時表示找到，退出
if ((array[high].compareTo(array[pivot])) < 0) {
break;
} else {//如果高指針指向的元素大于中樞元素時繼續(xù)找
high--;
}
}
//退出上面循環(huán)時 low = high
if (low == high) {
break;
}
swap(array, low, high);
}
//----高低指針?biāo)赶虻脑嘏判蛲瓿珊螅€得要把中樞元素放到適當(dāng)?shù)奈恢?nbsp;
if ((array[pivot].compareTo(array[low])) > 0) {
//如果退出循環(huán)時中樞元素大于了低指針或高指針元素時，中樞元素需與low元素交換
swap(array, low, pivot);
pivot = low;
} else if ((array[pivot].compareTo(array[low])) <= 0) {
swap(array, low - 1, pivot);
pivot = low - 1;
}
//返回中樞元素所在位置，以便下次分區(qū)
return pivot;
}
/**
* 交換數(shù)組中的兩個元素的位置
* @param array 待交換的數(shù)組
* @param i 第一個元素
* @param j 第二個元素
*/
public void swap(Integer[] array, int i, int j) {
if (i != j) {//只有不是同一位置時才需交換
Integer tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
/**
* 測試
* @param args
*/
public static void main(String[] args) {
Integer[] intgArr = { 5, 9, 1, 4, 2, 6, 3, 8, 0, 7 };
QuickSort quicksort = new QuickSort();
quicksort.sort(intgArr,0,intgArr.length-1);
for(Integer intObj:intgArr){
System.out.print(intObj + " ");
}
}
}
六、歸并排序
java代碼實現(xiàn)：
/**
歸并排序：里面是一個遞歸程序，深刻理解之。
*/
public class MergeSort{
/**
* 遞歸劃分?jǐn)?shù)組
* @param arr
* @param from
* @param end
* @param c void
*/
public void partition(Integer[] arr, int from, int end) {
//劃分到數(shù)組只有一個元素時才不進(jìn)行再劃分
if (from < end) {
//從中間劃分成兩個數(shù)組
int mid = (from + end) / 2;
partition(arr, from, mid);
partition(arr, mid + 1, end);
//合并劃分后的兩個數(shù)組
merge(arr, from, end, mid);
}
}
/**
* 數(shù)組合并，合并過程中對兩部分?jǐn)?shù)組進(jìn)行排序
* 前后兩部分?jǐn)?shù)組里是有序的
* @param arr
* @param from
* @param end
* @param mid
* @param c void
*/
public void merge(Integer[] arr, int from, int end, int mid) {
Integer[] tmpArr = new Integer[10];
int tmpArrIndex = 0;//指向臨時數(shù)組
int part1ArrIndex = from;//指向第一部分?jǐn)?shù)組
int part2ArrIndex = mid + 1;//指向第二部分?jǐn)?shù)組
//由于兩部分?jǐn)?shù)組里是有序的，所以每部分可以從第一個元素依次取到最后一個元素，再對兩部分
//取出的元素進(jìn)行比較。只要某部分?jǐn)?shù)組元素取完后，退出循環(huán)
while ((part1ArrIndex <= mid) && (part2ArrIndex <= end)) {
//從兩部分?jǐn)?shù)組里各取一個進(jìn)行比較，取最小一個并放入臨時數(shù)組中
if (arr[part1ArrIndex] - arr[part2ArrIndex] < 0) {
//如果第一部分?jǐn)?shù)組元素小，則將第一部分?jǐn)?shù)組元素放入臨時數(shù)組中，并且臨時數(shù)組指針
//tmpArrIndex下移一個以做好下次存儲位置準(zhǔn)備，前部分?jǐn)?shù)組指針part1ArrIndex
//也要下移一個以便下次取出下一個元素與后部分?jǐn)?shù)組元素比較
tmpArr[tmpArrIndex++] = arr[part1ArrIndex++];
} else {
//如果第二部分?jǐn)?shù)組元素小，則將第二部分?jǐn)?shù)組元素放入臨時數(shù)組中
tmpArr[tmpArrIndex++] = arr[part2ArrIndex++];
}
}
//由于退出循環(huán)后，兩部分?jǐn)?shù)組中可能有一個數(shù)組元素還未處理完，所以需要額外的處理，當(dāng)然不可
//能兩部分?jǐn)?shù)組都有未處理完的元素，所以下面兩個循環(huán)最多只有一個會執(zhí)行，并且都是大于已放入
//臨時數(shù)組中的元素
while (part1ArrIndex <= mid) {
tmpArr[tmpArrIndex++] = arr[part1ArrIndex++];
}
while (part2ArrIndex <= end) {
tmpArr[tmpArrIndex++] = arr[part2ArrIndex++];
}
//最后把臨時數(shù)組拷貝到源數(shù)組相同的位置
System.arraycopy(tmpArr, 0, arr, from, end - from + 1);
}
/**
* 測試
* @param args
*/
public static void main(String[] args) {
Integer[] intgArr = {5,9,1,4,2,6,3,8,0,7};
MergeSort insertSort = new MergeSort();
insertSort.partition(intgArr,0,intgArr.length-1);
for(Integer a:intgArr){
System.out.print(a + " ");
}
}
}
七、堆排序(Heap Sort)
1. 基本思想：
堆排序是一樹形選擇排序，在排序過程中，將R[1..N]看成是一顆完全二叉樹的順序存儲結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在關(guān)系來選擇最小的元素。
2. 堆的定義: N個元素的序列K1,K2,K3,...,Kn.稱為堆，當(dāng)且僅當(dāng)該序列滿足特性：
Ki≤K2i Ki ≤K2i+1(1≤ I≤ [N/2])
堆實質(zhì)上是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉子結(jié)點的關(guān)鍵字均大于等于其孩子結(jié)點的關(guān)鍵字。例如序列10,15,56,25,30,70就是一個堆，它對應(yīng)的完全二叉樹如上圖所示。這種堆中根結(jié)點（稱為堆頂）的關(guān)鍵字最小，我們把它稱為小根堆。反之，若完全二叉樹中任一非葉子結(jié)點的關(guān)鍵字均大于等于其孩子的關(guān)鍵字，則稱之為大根堆。
3. 排序過程：
堆排序正是利用小根堆（或大根堆）來選取當(dāng)前無序區(qū)中關(guān)鍵字小（或最大）的記錄實現(xiàn)排序的。我們不妨利用大根堆來排序。每一趟排序的基本操作是：將當(dāng)前無序區(qū)調(diào)整為一個大根堆，選取關(guān)鍵字最大的堆頂記錄，將它和無序區(qū)中的最后一個記錄交換。這樣，正好和直接選擇排序相反，有序區(qū)是在原記錄區(qū)的尾部形成并逐步向前擴(kuò)大到整個記錄區(qū)。
【示例】：對關(guān)鍵字序列42，13，91，23，24，16，05，88建堆
java代碼實現(xiàn)：
/**
* 選擇排序之堆排序：
*/
public class HeapSort {
/**
* 排序算法的實現(xiàn)，對數(shù)組中指定的元素進(jìn)行排序
* @param array 待排序的數(shù)組
* @param from 從哪里開始排序
* @param end 排到哪里
* @param c 比較器
*/
public void sort(Integer[] array, int from, int end) {
//創(chuàng)建初始堆
initialHeap(array, from, end);
/*
* 對初始堆進(jìn)行循環(huán)，且從最后一個節(jié)點開始，直接樹只有兩個節(jié)點止
* 每輪循環(huán)后丟棄最后一個葉子節(jié)點，再看作一個新的樹
*/
for (int i = end - from + 1; i >= 2; i--) {
//根節(jié)點與最后一個葉子節(jié)點交換位置，即數(shù)組中的第一個元素與最后一個元素互換
swap(array, from, i - 1);
//交換后需要重新調(diào)整堆
adjustNote(array, 1, i - 1);
}
}
/**
* 初始化堆
* 比如原序列為：7,2,4,3,12,1,9,6,8,5,10,11
* 則初始堆為：1,2,4,3,5,7,9,6,8,12,10,11
* @param arr 排序數(shù)組
* @param from 從哪
* @param end 到哪
* @param c 比較器
*/
private void initialHeap(Integer[] arr, int from, int end) {
int lastBranchIndex = (end - from + 1) / 2;//最后一個非葉子節(jié)點
//對所有的非葉子節(jié)點進(jìn)行循環(huán) ，且從最一個非葉子節(jié)點開始
for (int i = lastBranchIndex; i >= 1; i--) {
adjustNote(arr, i, end - from + 1);
}
}
/**
* 調(diào)整節(jié)點順序，從父、左右子節(jié)點三個節(jié)點中選擇一個最大節(jié)點與父節(jié)點轉(zhuǎn)換
* @param arr 待排序數(shù)組
* @param parentNodeIndex 要調(diào)整的節(jié)點，與它的子節(jié)點一起進(jìn)行調(diào)整
* @param len 樹的節(jié)點數(shù)
* @param c 比較器
*/
private void adjustNote(Integer[] arr, int parentNodeIndex, int len) {
int minNodeIndex = parentNodeIndex;
//如果有左子樹，i * 2為左子節(jié)點索引
if (parentNodeIndex * 2 <= len) {
//如果父節(jié)點小于左子樹時
if ((arr[parentNodeIndex - 1].compareTo(arr[parentNodeIndex * 2 - 1])) < 0) {
minNodeIndex = parentNodeIndex * 2;//記錄最大索引為左子節(jié)點索引
}
// 只有在有或子樹的前提下才可能有右子樹，再進(jìn)一步斷判是否有右子樹
if (parentNodeIndex * 2 + 1 <= len) {
//如果右子樹比最大節(jié)點更大
if ((arr[minNodeIndex - 1].compareTo(arr[(parentNodeIndex * 2 + 1) - 1])) < 0) {
minNodeIndex = parentNodeIndex * 2 + 1;//記錄最大索引為右子節(jié)點索引
}
}
}
//如果在父節(jié)點、左、右子節(jié)點三都中，最大節(jié)點不是父節(jié)點時需交換，把最大的與父節(jié)點交換，創(chuàng)建大頂堆
if (minNodeIndex != parentNodeIndex) {
swap(arr, parentNodeIndex - 1, minNodeIndex - 1);
//交換后可能需要重建堆，原父節(jié)點可能需要繼續(xù)下沉
if (minNodeIndex * 2 <= len) {//是否有子節(jié)點，注，只需判斷是否有左子樹即可知道
adjustNote(arr, minNodeIndex, len);
}
}
}
/**
* 交換數(shù)組中的兩個元素的位置
* @param array 待交換的數(shù)組
* @param i 第一個元素
* @param j 第二個元素
*/
public void swap(Integer[] array, int i, int j) {
if (i != j) {//只有不是同一位置時才需交換
Integer tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
/**
* 測試
* @param args
*/
public static void main(String[] args) {
Integer[] intgArr = { 5, 9, 1, 4, 2, 6, 3, 8, 0, 7 };
HeapSort heapsort = new HeapSort();
heapsort.sort(intgArr,0,intgArr.length-1);
for(Integer intObj:intgArr){
System.out.print(intObj + " ");
}
}
}
八、桶式排序
java代碼實現(xiàn)：
/**
* 桶式排序:
* 桶式排序不再是基于比較的了，它和基數(shù)排序同屬于分配類的排序，
* 這類排序的特點是事先要知道待排 序列的一些特征。
* 桶式排序事先要知道待排 序列在一個范圍內(nèi)，而且這個范圍應(yīng)該不是很大的。
* 比如知道待排序列在[0,M）內(nèi)，那么可以分配M個桶，第I個桶記錄I的出現(xiàn)情況，
* 最后根據(jù)每個桶收到的位置信息把數(shù)據(jù)輸出成有序的形式。
* 這里我們用兩個臨時性數(shù)組，一個用于記錄位置信息，一個用于方便輸出數(shù)據(jù)成有序方式，
* 另外我們假設(shè)數(shù)據(jù)落在0到MAX,如果所給數(shù)據(jù)不是從0開始，你可以把每個數(shù)減去最小的數(shù)。
*/
public class BucketSort {
public void sort(int[] keys,int from,int len,int max)
{
int[] temp=new int[len];
int[] count=new int[max];
for(int i=0;i<len;i++)
{
count[keys[from+i]]++;
}
//calculate position info
for(int i=1;i<max;i++)
{
count[i]=count[i]+count[i-1];//這意味著有多少數(shù)目小于或等于i，因此它也是position+ 1
}
System.arraycopy(keys, from, temp, 0, len);
for(int k=len-1;k>=0;k--)//從最末到開頭保持穩(wěn)定性
{
keys[--count[temp[k]]]=temp[k];// position +1 =count
}
}
/**
* @param args
*/
public static void main(String[] args) {
int[] a={1,4,8,3,2,9,5,0,7,6,9,10,9,13,14,15,11,12,17,16};
BucketSort bucketSort=new BucketSort();
bucketSort.sort(a,0,a.length,20);//actually is 18, but 20 will also work
for(int i=0;i<a.length;i++)
{
System.out.print(a[i]+",");
}
}
}
九、基數(shù)排序
java代碼實現(xiàn)：
/**
* 基數(shù)排序：
*/
import java.util.Arrays;
public class RadixSort {
/**
* 取數(shù)x上的第d位數(shù)字
* @param x 數(shù)
* @param d 第幾位，從低位到高位
* @return
*/
public int digit(long x, long d) {
long pow = 1;
while (--d > 0) {
pow *= 10;
}
return (int) (x / pow % 10);
}
/**
* 基數(shù)排序?qū)崿F(xiàn)，以升序排序（下面程序中的位記錄器count中，從第0個元素到第9個元素依次用來
* 記錄當(dāng)前比較位是0的有多少個..是9的有多少個數(shù)，而降序時則從第0個元素到第9個元素依次用來
* 記錄當(dāng)前比較位是9的有多少個..是0的有多少個數(shù)）
* @param arr 待排序數(shù)組
* @param digit 數(shù)組中最大數(shù)的位數(shù)
* @return
*/
public long[] radixSortAsc(long[] arr) {
//從低位往高位循環(huán)
for (int d = 1; d <= getMax(arr); d++) {
//臨時數(shù)組，用來存放排序過程中的數(shù)據(jù)
long[] tmpArray = new long[arr.length];
//位記數(shù)器，從第0個元素到第9個元素依次用來記錄當(dāng)前比較位是0的有多少個..是9的有多少個數(shù)
int[] count = new int[10];
//開始統(tǒng)計0有多少個，并存儲在第0位，再統(tǒng)計1有多少個，并存儲在第1位..依次統(tǒng)計到9有多少個
for (int i = 0; i < arr.length; i++) {
count[digit(arr[i], d)] += 1;
}
/*
* 比如某次經(jīng)過上面統(tǒng)計后結(jié)果為：[0, 2, 3, 3, 0, 0, 0, 0, 0, 0]則經(jīng)過下面計算后 結(jié)果為：
* [0, 2, 5, 8, 8, 8, 8, 8, 8, 8]但實質(zhì)上只有如下[0, 2, 5, 8, 0, 0, 0, 0, 0, 0]中
* 非零數(shù)才用到，因為其他位不存在，它們分別表示如下：2表示比較位為1的元素可以存放在索引為1、0的
* 位置，5表示比較位為2的元素可以存放在4、3、2三個(5-2=3)位置，8表示比較位為3的元素可以存放在
* 7、6、5三個(8-5=3)位置
*/
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
/*
* 注，這里只能從數(shù)組后往前循環(huán)，因為排序時還需保持以前的已排序好的 順序，不應(yīng)該打
* 亂原來已排好的序，如果從前往后處理，則會把原來在前面會擺到后面去，因為在處理某個
* 元素的位置時，位記數(shù)器是從大到到小（count[digit(arr[i], d)]--）的方式來處
* 理的，即先存放索引大的元素，再存放索引小的元素，所以需從最后一個元素開始處理。
* 如有這樣的一個序列[212,213,312]，如果按照從第一個元素開始循環(huán)的話，經(jīng)過第一輪
* 后（個位）排序后，得到這樣一個序列[312,212,213]，第一次好像沒什么問題，但問題會
* 從第二輪開始出現(xiàn)，第二輪排序后，會得到[213,212,312]，這樣個位為3的元素本應(yīng)該
* 放在最后，但經(jīng)過第二輪后卻排在了前面了，所以出現(xiàn)了問題
*/
for (int i = arr.length - 1; i >= 0; i--) {//只能從最后一個元素往前處理
//for (int i = 0; i < arr.length; i++) {//不能從第一個元素開始循環(huán)
tmpArray[count[digit(arr[i], d)] - 1] = arr[i];
count[digit(arr[i], d)]--;
}
System.arraycopy(tmpArray, 0, arr, 0, tmpArray.length);
}
return arr;
}
/**
* 基數(shù)排序?qū)崿F(xiàn)，以降序排序（下面程序中的位記錄器count中，從第0個元素到第9個元素依次用來
* 記錄當(dāng)前比較位是0的有多少個..是9的有多少個數(shù)，而降序時則從第0個元素到第9個元素依次用來
* 記錄當(dāng)前比較位是9的有多少個..是0的有多少個數(shù)）
* @param arr 待排序數(shù)組
* @return
*/
public long[] radixSortDesc(long[] arr) {
for (int d = 1; d <= getMax(arr); d++) {
long[] tmpArray = new long[arr.length];
//位記數(shù)器，從第0個元素到第9個元素依次用來記錄當(dāng)前比較位是9的有多少個..是0的有多少個數(shù)
int[] count = new int[10];
//開始統(tǒng)計0有多少個，并存儲在第9位，再統(tǒng)計1有多少個，并存儲在第8位..依次統(tǒng)計
//到9有多少個，并存儲在第0位
for (int i = 0; i < arr.length; i++) {
count[9 - digit(arr[i], d)] += 1;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (int i = arr.length - 1; i >= 0; i--) {
tmpArray[count[9 - digit(arr[i], d)] - 1] = arr[i];
count[9 - digit(arr[i], d)]--;
}
System.arraycopy(tmpArray, 0, arr, 0, tmpArray.length);
}
return arr;
}
private int getMax(long[] array) {
int maxlIndex = 0;
for (int j = 1; j < array.length; j++) {
if (array[j] > array[maxlIndex]) {
maxlIndex = j;
}
}
return String.valueOf(array[maxlIndex]).length();
}
public static void main(String[] args) {
long[] ary = new long[] { 123, 321, 132, 212, 213, 312, 21, 223 };
RadixSort rs = new RadixSort();
System.out.println("升 - " + Arrays.toString(rs.radixSortAsc(ary)));
ary = new long[] { 123, 321, 132, 212, 213, 312, 21, 223 };
System.out.println("降 - " + Arrays.toString(rs.radixSortDesc(ary)));
}
}
十、幾種排序算法的比較和選擇
1. 選取排序方法需要考慮的因素：
(1) 待排序的元素數(shù)目n；
(2) 元素本身信息量的大小；
(3) 關(guān)鍵字的結(jié)構(gòu)及其分布情況；
(4) 語言工具的條件，輔助空間的大小等。
2. 小結(jié)：
(1) 若n較小(n <= 50)，則可以采用直接插入排序或直接選擇排序。由于直接插入排序所需的記錄移動操作較直接選擇排序多，因而當(dāng)記錄本身信息量較大時，用直接選擇排序較好。
(2) 若文件的初始狀態(tài)已按關(guān)鍵字基本有序，則選用直接插入或冒泡排序為宜。
(3) 若n較大，則應(yīng)采用時間復(fù)雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序。 快速排序是目前基于比較的內(nèi)部排序法中被認(rèn)為是最好的方法。
(4) 在基于比較排序方法中，每次比較兩個關(guān)鍵字的大小之后，僅僅出現(xiàn)兩種可能的轉(zhuǎn)移，因此可以用一棵二叉樹來描述比較判定過程，由此可以證明：當(dāng)文件的n個關(guān)鍵字隨機(jī)分布時，任何借助于"比較"的排序算法，至少需要O(nlog2n)的時間。
(5) 當(dāng)記錄本身信息量較大時，為避免耗費大量時間移動記錄，可以用鏈表作為存儲結(jié)構(gòu)。
排序簡介
排序是數(shù)據(jù)處理中經(jīng)常使用的一種重要運算,在計算機(jī)及其應(yīng)用系統(tǒng)中,花費在排序上的時間在系統(tǒng)運行時間中占有很大比重;并且排序本身對推動算法分析的發(fā)展也起很大作用。目前已有上百種排序方法，但尚未有一個最理想的盡如人意的方法，本章介紹常用的如下排序方法，并對它們進(jìn)行分析和比較。
1、插入排序（直接插入排序、折半插入排序、希爾排序）；
2、交換排序（起泡排序、快速排序）；
3、選擇排序（直接選擇排序、堆排序）；
4、歸并排序；
5、基數(shù)排序；
學(xué)習(xí)重點
1、掌握排序的基本概念和各種排序方法的特點，并能加以靈活應(yīng)用；
2、掌握插入排序(直接插入排序、折半插入排序、希爾排序)、交換排序（起泡排序、快速排序）、選擇排序（直接選擇排序、堆排序）、二路歸并排序的方法及其性能分析方法；
3、了解基數(shù)排序方法及其性能分析方法。
排序（sort）或分類
所謂排序，就是要整理文件中的記錄，使之按關(guān)鍵字遞增(或遞減)次序排列起來。其確切定義如下：
輸入：n個記錄R1，R2，…，Rn，其相應(yīng)的關(guān)鍵字分別為K1，K2，…，Kn。
輸出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。
1．被排序?qū)ο?-文件
被排序的對象--文件由一組記錄組成。
記錄則由若干個數(shù)據(jù)項(或域)組成。其中有一項可用來標(biāo)識一個記錄，稱為關(guān)鍵字項。該數(shù)據(jù)項的值稱為關(guān)鍵字(Key)。
注意：
在不易產(chǎn)生混淆時，將關(guān)鍵字項簡稱為關(guān)鍵字。
2．排序運算的依據(jù)--關(guān)鍵字
用來作排序運算依據(jù)的關(guān)鍵字，可以是數(shù)字類型，也可以是字符類型。
關(guān)鍵字的選取應(yīng)根據(jù)問題的要求而定。
【例】在高考成績統(tǒng)計中將每個考生作為一個記錄。每條記錄包含準(zhǔn)考證號、姓名、各科的分?jǐn)?shù)和總分?jǐn)?shù)等項內(nèi)容。若要惟一地標(biāo)識一個考生的記錄，則必須用"準(zhǔn)考證號"作為關(guān)鍵字。若要按照考生的總分?jǐn)?shù)排名次，則需用"總分?jǐn)?shù)"作為關(guān)鍵字。
排序的穩(wěn)定性
當(dāng)待排序記錄的關(guān)鍵字均不相同時，排序結(jié)果是惟一的，否則排序結(jié)果不唯一。
在待排序的文件中，若存在多個關(guān)鍵字相同的記錄，經(jīng)過排序后這些具有相同關(guān)鍵字的記錄之間的相對次序保持不變，該排序方法是穩(wěn)定的；若具有相同關(guān)鍵字的記錄之間的相對次序發(fā)生變化，則稱這種排序方法是不穩(wěn)定的。
注意：
排序算法的穩(wěn)定性是針對所有輸入實例而言的。即在所有可能的輸入實例中，只要有一個實例使得算法不滿足穩(wěn)定性要求，則該排序算法就是不穩(wěn)定的。
排序方法的分類
1．按是否涉及數(shù)據(jù)的內(nèi)、外存交換分
在排序過程中，若整個文件都是放在內(nèi)存中處理，排序時不涉及數(shù)據(jù)的內(nèi)、外存交換，則稱之為內(nèi)部排序(簡稱內(nèi)排序)；反之，若排序過程中要進(jìn)行數(shù)據(jù)的內(nèi)、外存交換，則稱之為外部排序。
注意：
① 內(nèi)排序適用于記錄個數(shù)不很多的小文件
② 外排序則適用于記錄個數(shù)太多，不能一次將其全部記錄放人內(nèi)存的大文件。
2．按策略劃分內(nèi)部排序方法
可以分為五類：插入排序、選擇排序、交換排序、歸并排序和分配排序。
排序算法分析
1．排序算法的基本操作
大多數(shù)排序算法都有兩個基本的操作：
(1) 比較兩個關(guān)鍵字的大小；
(2) 改變指向記錄的指針或移動記錄本身。
注意：
第(2)種基本操作的實現(xiàn)依賴于待排序記錄的存儲方式。
2．待排文件的常用存儲方式
（1） 以順序表(或直接用向量)作為存儲結(jié)構(gòu)
排序過程：對記錄本身進(jìn)行物理重排（即通過關(guān)鍵字之間的比較判定，將記錄移到合適的位置）
（2） 以鏈表作為存儲結(jié)構(gòu)
排序過程：無須移動記錄，僅需修改指針。通常將這類排序稱為鏈表(或鏈?zhǔn)?排序；
（3） 用順序的方式存儲待排序的記錄，但同時建立一個輔助表(如包括關(guān)鍵字和指向記錄位置的指針組成的索引表)
排序過程：只需對輔助表的表目進(jìn)行物理重排（即只移動輔助表的表目，而不移動記錄本身）。適用于難于在鏈表上實現(xiàn)，仍需避免排序過程中移動記錄的排序方法。
3．排序算法性能評價
（1） 評價排序算法好壞的標(biāo)準(zhǔn)
評價排序算法好壞的標(biāo)準(zhǔn)主要有兩條：
① 執(zhí)行時間和所需的輔助空間
② 算法本身的復(fù)雜程度
（2） 排序算法的空間復(fù)雜度
若排序算法所需的輔助空間并不依賴于問題的規(guī)模n，即輔助空間是O(1)，則稱之為就地排序(In-PlaceSou)。
非就地排序一般要求的輔助空間為O(n)。
（3） 排序算法的時間開銷
大多數(shù)排序算法的時間開銷主要是關(guān)鍵字之間的比較和記錄的移動。有的排序算法其執(zhí)行時間不僅依賴于問題的規(guī)模，還取決于輸入實例中數(shù)據(jù)的狀態(tài)。
文件的順序存儲結(jié)構(gòu)表示
#define n l00 //假設(shè)的文件長度，即待排序的記錄數(shù)目
typedef int KeyType； //假設(shè)的關(guān)鍵字類型
typedef struct{ //記錄類型
KeyType key； //關(guān)鍵字項
InfoType otherinfo；//其它數(shù)據(jù)項，類型InfoType依賴于具體應(yīng)用而定義
}RecType；
typedef RecType SeqList[n+1]；//SeqList為順序表類型，表中第0個單元一般用作哨兵
注意：
若關(guān)鍵字類型沒有比較算符，則可事先定義宏或函數(shù)來表示比較運算。
【例】關(guān)鍵字為字符串時，可定義宏"#define LT(a，b)(Stromp((a)，(b))<0)"。那么算法中"a<b"可用"LT(a，b)"取代。若使用C++，則定義重載的算符"<"更為方便。
按平均時間將排序分為四類：
（1）平方階(O(n2))排序
一般稱為簡單排序，例如直接插入、直接選擇和冒泡排序；
（2）線性對數(shù)階(O(nlgn))排序
如快速、堆和歸并排序；
（3）O(n1+￡)階排序
￡是介于0和1之間的常數(shù)，即0<￡<1，如希爾排序；
（4）線性階(O(n))排序
如桶、箱和基數(shù)排序。
各種排序方法比較
簡單排序中直接插入最好，快速排序最快，當(dāng)文件為正序時，直接插入和冒泡均最佳。
影響排序效果的因素
因為不同的排序方法適應(yīng)不同的應(yīng)用環(huán)境和要求，所以選擇合適的排序方法應(yīng)綜合考慮下列因素：
①待排序的記錄數(shù)目n；
②記錄的大小(規(guī)模)；
③關(guān)鍵字的結(jié)構(gòu)及其初始狀態(tài)；
④對穩(wěn)定性的要求；
⑤語言工具的條件；
⑥存儲結(jié)構(gòu)；
⑦時間和輔助空間復(fù)雜度等。
不同條件下，排序方法的選擇
(1)若n較小(如n≤50)，可采用直接插入或直接選擇排序。
當(dāng)記錄規(guī)模較小時，直接插入排序較好；否則因為直接選擇移動的記錄數(shù)少于直接插人，應(yīng)選直接選擇排序為宜。
(2)若文件初始狀態(tài)基本有序(指正序)，則應(yīng)選用直接插人、冒泡或隨機(jī)的快速排序為宜；
(3)若n較大，則應(yīng)采用時間復(fù)雜度為O(nlgn)的排序方法：快速排序、堆排序或歸并排序。
快速排序是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法，當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時，快速排序的平均時間最短；
堆排序所需的輔助空間少于快速排序，并且不會出現(xiàn)快速排序可能出現(xiàn)的最壞情況。這兩種排序都是不穩(wěn)定的。
若要求排序穩(wěn)定，則可選用歸并排序。但本章介紹的從單個記錄起進(jìn)行兩兩歸并的 排序算法并不值得提倡，通常可以將它和直接插入排序結(jié)合在一起使用。先利用直接插入排序求得較長的有序子文件，然后再兩兩歸并之。因為直接插入排序是穩(wěn)定的，所以改進(jìn)后的歸并排序仍是穩(wěn)定的。
4)在基于比較的排序方法中，每次比較兩個關(guān)鍵字的大小之后，僅僅出現(xiàn)兩種可能的轉(zhuǎn)移，因此可以用一棵二叉樹來描述比較判定過程。
當(dāng)文件的n個關(guān)鍵字隨機(jī)分布時，任何借助于"比較"的排序算法，至少需要O(nlgn)的時間。
箱排序和基數(shù)排序只需一步就會引起m種可能的轉(zhuǎn)移，即把一個記錄裝入m個箱子之一，因此在一般情況下，箱排序和基數(shù)排序可能在O(n)時間內(nèi)完成對n個記錄的排序。但是，箱排序和基數(shù)排序只適用于像字符串和整數(shù)這類有明顯結(jié)構(gòu)特征的關(guān)鍵字，而當(dāng)關(guān)鍵字的取值范圍屬于某個無窮集合(例如實數(shù)型關(guān)鍵字)時，無法使用箱排序和基數(shù)排序，這時只有借助于"比較"的方法來排序。
若n很大，記錄的關(guān)鍵字位數(shù)較少且可以分解時，采用基數(shù)排序較好。雖然桶排序?qū)﹃P(guān)鍵字的結(jié)構(gòu)無要求，但它也只有在關(guān)鍵字是隨機(jī)分布時才能使平均時間達(dá)到線性階，否則為平方階。同時要注意，箱、桶、基數(shù)這三種分配排序均假定了關(guān)鍵字若為數(shù)字時，則其值均是非負(fù)的，否則將其映射到箱(桶)號時，又要增加相應(yīng)的時間。
(5)有的語言(如Fortran，Cobol或Basic等)沒有提供指針及遞歸，導(dǎo)致實現(xiàn)歸并、快速(它們用遞歸實現(xiàn)較簡單)和基數(shù)(使用了指針)等排序算法變得復(fù)雜。此時可考慮用其它排序。
(6)本章給出的排序算法，輸人數(shù)據(jù)均是存儲在一個向量中。當(dāng)記錄的規(guī)模較大時，為避免耗費大量的時間去移動記錄，可以用鏈表作為存儲結(jié)構(gòu)。譬如插入排序、歸并排序、基數(shù)排序都易于在鏈表上實現(xiàn)，使之減少記錄的移動次數(shù)。但有的排序方法，如快速排序和堆排序，在鏈表上卻難于實現(xiàn)，在這種情況下，可以提取關(guān)鍵字建立索引表，然后對索引表進(jìn)行排序。然而更為簡單的方法是：引人一個整型向量t作為輔助表，排序前令t[i]=i(0≤i<n)，若排序算法中要求交換R[i]和R[j]，則只需交換t[i]和t[j]即可；排序結(jié)束后，向量t就指示了記錄之間的順序關(guān)系：
R[t[0]].key≤R[t[1]].key≤…≤R[t[n-1]].key
若要求最終結(jié)果是：
R[0].key≤R[1].key≤…≤R[n-1].key
則可以在排序結(jié)束后，再按輔助表所規(guī)定的次序重排各記錄，完成這種重排的時間是O(n)。