數據結構幾種排序算法詳解和總結（java版）
一、排序的概念：
1、設 n 個記錄的序列為 { R1 , R2 , R3 , . . . , Rn}
其相應的關鍵字序列為 { K1 , K2 , K3, . . . , Kn }
若規定 1 , 2 , 3 , . . . , n 的一個排列 p1 , p2 , p3 , . . . , pn，使得相應的關鍵字滿足如下非遞減關系:
Kp1 ≤ Kp2 ≤ Kp3≤ . . . ≤ Kpn
則原序列變為一個按關鍵字有序的序列:
Rp1 , Rp2 , Rp3 , . . . , Rpn
此操作過程稱為排序。
2、排序問題一般分為內排序( internal sorting )和外排序( external sorting )兩類：
2.1. 內排序：待排序的表中記錄個數較少，整個排序過程中所有的記錄都可以保留在內存中；按照排序過程中所依據的原則的不同可以分類為:
? 插入排序（直接插入排序、折半插入排序、希爾排序）
? 交換排序(快速排序)（冒泡泡排序、快速排序）
? 選擇排序（直接選擇排序、堆排序）
? 歸并排序
? 基數排序
? 二叉排序樹排序
2.2.外排序：待排序的記錄個數足夠多，以至于他們必須存儲在磁帶、磁盤上組成外部文件，排序過程中需要多次訪問外存。
3、排序的時間復雜性：
排序過程主要是對記錄的排序碼進行比較和記錄的移動過程。因此排序的時間復雜性可以算法執行中的數據比較次數及數據移動次數來衡量。當一種排序方法使排序過程在最壞或平均情況下所進行的比較和移動次數越少，則認為該方法的時間復雜性就越好，分析一種排序方法，不僅要分析它的時間復雜性，而且要分析它的空間復雜性、穩定性和簡單性等。
二、各種排序算法及代碼詳解：
1、插入類排序--直接插入排序
插入類排序算法思想：主要就是對于一個已經有序的序列中，插入一個新的記錄，但要求插入后此數據序列仍然有序，這個時候就要用到插入排序法。它包括：直接插入排序，折半插入排序和希爾排序。
1.1、直接插入排序的基本思想是，經過i-1遍處理后,L[1..i-1]己排好序。第i遍處理僅將L[i]插入L[1..i-1]的適當位置，使得L[1..i]又是排好序的序列。要達到這個目的，直接插入排序用順序比較的方法。首先比較L[i]和L[i-1]，如果L[i-1]≤ L[i]，則L[1..i]已排好序，第i遍處理就結束了；否則交換L[i]與L[i-1]的位置，繼續比較L[i-1]和L[i-2]，直到找到某一個位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]時為止。
算法描述
1.2、一般來說，插入排序都采用in-place在數組上實現。具體算法描述如下：
1. 從第一個元素開始，該元素可以認為已經被排序，
2. 取出下一個元素，在已經排序的元素序列中從后向前掃描，
3. 如果該元素（已排序）大于新元素，將該元素移到下一位置，
4. 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置，
5. 將新元素插入到下一位置中，
6. 重復步驟2；
如果比較操作的代價比交換操作大的話，可以采用二分查找法來減少比較操作的數目。該算法可以認為是插入排序的一種，稱為二分查找排序。
1.3、算法代碼實現：
public class DirectInserSort {
public static void main(String[] args) {
int count1 = 0, count2 = 0;// 復制次數，比較次數
long begin = System.currentTimeMillis();
System.out.println("插入前時間為：" + begin);
// TODO Auto-generated method stub
int data[] = { 2, 6, 10, 3, 9, 80, 1, 16, 27, 20 };
int temp, j;
for (int i = 1; i < data.length; i++) {
temp = data[i];
j = i - 1;
// 每次比較都是對于已經有序的
while (j >= 0 && data[j] > temp) {
data[j + 1] = data[j];
j--;
count1++;
}
data[j + 1] = temp;
count2++;
}
long end = System.currentTimeMillis();
System.out.println("插入后時間為：" + end);
System.out.println("插入法用時為：" + (end - begin));
// 輸出排序好的數據
for (int k = 0; k < data.length; k++) {
System.out.print(data[k] + " ");
}
System.out.println("復制次數為：" + count1 + " 比較次數為：" + count2);
}
}
插入排序法在數據已有一定順序的情況下，效率較好。但如果數據無規則，則需要移動大量的數據，其效率就與冒泡排序法和選擇排序法一樣差了。因此插入排序是一個不穩定的排序方法，插入效率與數組初始順序息息相關。一般情況下，插入排序的時間復雜度和空間復雜度分別為 O(n2 ) 和 O(1) 。
2、插入類排序--二分法排序
2.1、二分法排序算法思想：折半插入排序記錄的比較次數與初始序列無關，折半插入就是首先將隊列中取最小位置low和最大位置high，然后算出中間位置mid，將中間位置mid與待插入的數據data進行比較，如果mid大于data，則就表示插入的數據在mid的左邊，high=mid-1，如果mid小于data，則就表示插入的數據在mid的右邊,low=mid+1。
2.2、具體算法描述如下：
1.確定查找范圍front=0，end=N-1，計算中項mid=（front+end）/2。
2.若data [mid]=x或front>=end,則結束查找；否則，向下繼續。
3.若data [mid]<x,說明待查找的元素值只可能在比中項元素大的范圍內，則把mid+1的值賦給front，并重新計算mid，轉去執行步驟2；若data [mid]>x，說明待查找的元素值只可能在比中項元素小的范圍內，則把mid-1的值賦給end，并重新計算mid，轉去執行步驟2。
2.3、算法代碼實現：
public class BinInsertSort {
//折半插入排序
public static void main(String[] args) {
int count1 = 0, count2 = 0;// 復制次數，比較次數
long begin = System.currentTimeMillis();
System.out.println("插入前時間為：" + begin);
int data[] = { 2, 6, 10, 3, 9, 80, 1, 16, 27, 20 };
// 存放臨時要插入的元素數據
int temp;
int low, mid, high;
for (int i = 1; i < data.length; i++) {
temp = data[i];
// 在待插入排序的序號之前進行折半插入
low = 0;
high = i - 1;
while (low <= high) {
mid = (low + high) / 2;
if (temp < data[mid])
high = mid - 1;
else
// low=high的時候也就是找到了要插入的位置，
// 此時進入循環中，將low加1，則就是要插入的位置了
low = mid + 1;
count2++;
}
// 找到了要插入的位置，從該位置一直到插入數據的位置之間數據向后移動
for (int j = i; j >= low + 1; j--){
data[j] = data[j - 1];
count1++;
}
// low已經代表了要插入的位置了
data[low] = temp;
}
long end = System.currentTimeMillis();
System.out.println("插入后時間為：" + end);
System.out.println("插入法用時為：" + (end - begin));
for (int k = 0; k < data.length; k++) {
System.out.print(data[k] + " ");
}
System.out.println("復制次數為：" + count1 + " 比較次數為：" + count2);
}折半查找是一種高效的查找方法。它可以明顯減少比較次數，提高查
找效率。但是，折半查找的先決條件是查找表中的數據元素必須有序。二分插入算法與直接插入算法相比，需要輔助空間與直接插入排序基本一致；時間上，前者的比較次數比直接插入查找的最壞情況好，最好的情況壞，兩種方法的元素的移動次數相同，因此二分插入排序的時間復雜度仍為O(n2)。二分插入算法與直接插入算法的元素移動一樣是順序的，因此該方法也是穩定的。
3、插入類排序--希爾排序
3.1、對于插入排序算法來說，如果原來的數據就是有序的，那么數據就不需要移動，而插入排序算法的效率主要消耗在數據的移動中。因此可知：如果數據的本身就是有序的或者本身基本有序，那么效率就會得到提高。
希爾排序的基本思想是：將需要排序的序列劃分成為若干個較小的子序列，對子序列進行插入排序，通過則插入排序能夠使得原來序列成為基本有序。這樣通過對較小的序列進行插入排序，然后對基本有序的數列進行插入排序，能夠提高插入排序算法的效率。
在希爾排序中首先解決的是子序列的選擇問題。對于子序列的構成不是簡單的分段，而是采取相隔某個增量的數據組成一個序列。一般的選擇原則是：去上一個增量的一般作為此次序列的劃分增量。首次選擇序列長度的一般為增量。
3.2算法步驟：
Step1 將n個元素個數列分為比如5個小組，在每個小組內按直接插入法排序；
step2 在第i步，分組個數取 di+1 =（di +1）/2 {9，5，3，2，1}；相臨兩組之間的對應元素進行比較，如果ai>aj，則交換它們的位置；
Step3 當dK = 1的循環過程完成后，排序過程結束。
3.3、算法代碼實現：
import java.util.Random;
class ShellSort{
public void sort(int[] resource){
int h = 1;
int temp;
while (h*3+1<resource.length+1){
h = h*3+1;
}
while (h != 0){
for(int i=0; i<h; i++){
for (int j=i; j<resource.length-h; j+=h){
temp = resource[j+h];
int k;
for (k=j; k>i-h; k-=h){
if (temp<resource[k]){
resource[k+h] = resource[k];
} else {
break;
}
}
resource[k+h] = temp;
}
}
h = (h-1)/3;
}
}
public static void main(String[] args){
ShellSort shell = new ShellSort();
Random random = new Random();
int[] test = new int[10000];
for (int i=0; i<test.length; i++){
test[i] = random.nextInt(10000);
}
for(int i : test){
System.out.print(i+",");
}
System.out.println();
long s = System.currentTimeMillis();
shell.sort(test);
long e = System.currentTimeMillis();
for(int i : test){
System.out.print(i+",");
}
System.out.println("\n"+(e-s)/1000.0+"秒");
}
}3.4、算法討論：
Shell排序算法的時間復雜度分析比較復雜，實際所需的時間取決于各次排序時增量的個數和增量的取值。研究證明，若增量的取值比較合理，Shell排序算法的時間復雜度約為O（n（ldn）2）。由于Shell排序算法是按增量分組進行的排序，所以Shell排序算法是一種不穩定的排序算法。也稱為遞減增量排序算法，各種實現在如何進行遞減上有所不同。不穩定，不需要輔助空間。希爾排序幾乎沒有最壞情況，無論是正序、逆序、亂序，所用時間都不是很多，附加儲存是O(1)，的確非常不錯。
4、 交換類排序--冒泡排序
所謂交換，就是根據序列中兩個記錄鍵值的比較結果來對換這兩個記錄在序列中的位置，交換排序的特點是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動。
4.1、冒泡排序（Bubble Sort）是一種最直觀的排序方法，在排序過程中，將相鄰的記錄的關鍵字進行比較，若前面記錄的關鍵字大于后面記錄的關鍵字，則將它們交換，否則不交換。或者反過來，使較大關鍵字的記錄后移，像水中的氣泡一樣，較小的記錄向前冒出，較大的記錄像石頭沉入后部。故稱此方法為冒泡排序法。
算法的基本思想為：首先在n個元素中，若ai>ai+1(i=1..n-1)則交換，得到一個最大元素放于an；其次在n-1個元素中，若ai>ai+1(i=1..n-2)則交換，這樣得到的一個次大元素放于an-1，以此類推，直到選出n-1個元素，排序完成。
4.2、算法代碼實現：
public class BubbleSort {
public static void main(String[] args) {
int vec[] = new int[] { 37, 46, 33, -5, 17, 51 };
int temp;
long begin = System.currentTimeMillis();
begin = System.currentTimeMillis();
for (int k = 0; k < 1000000; k++) {
for (int i = 0; i < vec.length; i++) {
for (int j = i; j < vec.length - 1; j++) {
if (vec[j + 1] < vec[j]) {
temp = vec[j + 1];
vec[j + 1] = vec[j];
vec[j] = temp;
}
}
}
}
long end = System.currentTimeMillis();
System.out.println("冒泡法用時為：" + (end - begin));
//打印排序好的結果
for (int i = 0; i < vec.length; i++) {
System.out.println(vec[i]);
}
}
}4.3、算法討論：冒泡排序算法穩定，O(1)的額外的空間，比較和交換的時間復雜度都是O(n^2)，自適應，對于已基本排序的算法，時間復雜度為O(n)。冒泡算法的許多性質和插入算法相似，但對于系統開銷高一點點。使用冒泡排序法對n個數據進行排序，共需要進行n-1次的比較。如果本來就是有順序的數據，也需要進行n-1次比較。冒泡排序法的算法很簡單，效率也較差。
5、交換類排序--快速排序
5.1、快速排序（Quick Sorting）是對冒泡排序的一種改進。在冒泡排序中，記錄的比較和交換是在相鄰的單元中進行的，記錄每次交換只能上移或下移一個單元，因而總的比較和移動次數較多。而在快速排序中，記錄的比較和交換是從兩端向中間進行的，關鍵字較小的記錄一次就能從后面單元交換到前面去，而關鍵字較大的記錄一次就能從前面的單元交換到后面的單元，記錄每次移動的記錄較遠，因此可以減少記錄總的比較和移動次數。
快速排序的基本做法是：任取待排序的n個記錄中的某個記錄作為基準（一般選取第一個記錄），通過一趟排序，將待排序記錄分成左右兩個字序列，左子序列記錄的關鍵字均小于或等于該基準記錄的關鍵字，右子序列記錄的關鍵字均大于或等于該基準記錄的關鍵字，從而得到該記錄最終排序的位置，然后該記錄不再參加排序，此一趟排序成為第一趟快速排序。然后對所分得左右子序列分別重復上述方法，直到所有的記錄都處在他們的最終位置，此時排序完成。在快速排序中，有時把待排序序列按照基準記錄的關鍵字分為左右兩個子序列的過程稱為一次劃分。
5.2、快速排序的過程為：
設待排序序列為r[s..t]，為實現一次劃分，可設置兩個指針low和high，他們的初值分別為s和t。以r[s]為基準，在劃分的過程中：
(1)從high端開始，依次向前掃描，并將掃描到的每一個記錄的關鍵字同r[s]（即基準記錄）的關鍵字進行比較，直到r[high].key<r[s].key時，將r[high]賦值到low所指的位置。
(2)從low端開始，依次向后掃描，并將掃描到的每一個記錄的關鍵字同r[s]（即基準記錄）的關鍵字進行比較，直到r[low].key>r[s].key時，將r[low]賦值到high所指的位置。
(3)如此交替改變掃描方向，重復上述兩個步驟從兩端各自向中間位置靠攏，直到low等于或大于high。經過此次劃分后得到的左右兩個子序列分別為r[s..low-1]和r[low+1..t]。然后對這兩個子序列按上述方法進行再次劃分，依次重復，直到每個序列只剩一個元素為止。
5.3算法實現：
public class QuickSort {
public void swap(int a[], int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
public int partSort(int a[], int low, int high) {
int pivot, p_pos, i;
p_pos = low;
pivot = a[p_pos];
for (i = low + 1; i <= high; i++) {
if (a[i] > pivot) {
p_pos++;
swap(a, p_pos, i);
}
}
swap(a, low, p_pos);
return p_pos;
}
public void quicksort(int a[], int low, int high) {
int pivot;
if (low < high) {
pivot = partSort(a, low, high);
quicksort(a, low, pivot - 1);
quicksort(a, pivot + 1, high);
}
}
public static void main(String[] args) {
// 快速排序法(Quick Sort)
int vec[] = new int[] { 37, 46, 33, -5, 17, 51 };
QuickSort s = new QuickSort();
long begin = System.currentTimeMillis();
for (int k = 0; k < 1000000; k++) {
s.quicksort(vec, 0, 5);
}
long end = System.currentTimeMillis();
System.out.println("快速法用時為：" + (end - begin));
// 打印排序好的結果
for (int i = 0; i < vec.length; i++) {
System.out.println(vec[i]);
}
}
}5.4算法討論：在快速排序中，若把每次劃分所用的基準記錄看作根節點，把劃分得到的左子序列和右子序列分別看成根節點的左、右子樹，那么整個排序過程就對應著一顆具有n個節點的二叉排序樹，所需劃分的層數等于二叉樹的深度，所需劃分的所有子序列數等于二叉樹分枝結點數，而在快速排序中，記錄的移動次數通常小于記錄的比較次數。因此，討論快速排序的時間復雜度時，僅考慮記錄的比較次數即可。
若快速排序出現最好的情況（左、右子序列的長度大致相等），則結點數n與二叉樹深度h應滿足log2(n)<=h<=log2(n+1)，所以總的比較次數不會超過（n+1）log2(n).因此，快速排序的最好時間復雜度應為O（nlog2(n)）。若快速排序出現最壞的情況（每次能劃分成兩個子序列，但是其中一個為空），則此時得到的二叉樹是一棵單枝樹，得到的非空子序列包含有n-i（i代表二叉樹的層數），每層劃分需要比較n-i+2次，所以總的比較次數為（n^2+3n-4）/2.因此，快速排序的最壞時間復雜度為O(n^2).
快速排序所占用的輔助空間為遞歸時所需棧的深度，故空間復雜度為O（log2(n)）。同時，快速排序是不穩定的排序。
6、選擇類排序--簡單選擇排序
6.1、選擇排序(Selection Sort)的基本思想是：每一趟從待排序的記錄中選出關鍵字最小的記錄，順序放在已排好序的子文件的最后，直到全部記錄排序完畢。如對于一組關鍵字{K1,K2,…,Kn}，首先從K1,K2,…,Kn中選擇最小值，假如它是 Kz，則將Kz與 K1對換；然后從K2，K3，…，Kn中選擇最小值 Kz，再將Kz與K2對換。如此進行選擇和調換n-2趟，第(n-1)趟，從Kn-1、Kn中選擇最小值 Kz將Kz與Kn-1對換，最后剩下的就是該序列中的最大值，一個由小到大的有序序列就這樣形成。
6.2、n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果：
①初始狀態：無序區為R[1..n]，有序區為空。
②第1趟排序
在無序區R[1..n]中選出關鍵字最小的記錄R[k]，將它與無序區的第1個記錄R[1]交換，使R[1..1]和R[2..n]分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。
……
③第i趟排序
第i趟排序開始時，當前有序區和無序區分別為R[1..i-1]和R(1≤i≤n-1)。該趟排序從當前無序區中選出關鍵字最小的記錄 R[k]，將它與無序區的第1個記錄R交換，使R[1..i]和R分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。
這樣，n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。
6.3、算法具體實現：
public class SelectSort {
public static void main(String[] args) {
int vec[] = new int[] { 37, 46, 33, -5, 17, 51 };
int temp;
//選擇排序法(Selection Sort)
long begin = System.currentTimeMillis();
for (int k = 0; k < 1000000; k++) {
for (int i = 0; i < vec.length; i++) {
for (int j = i; j < vec.length; j++) {
if (vec[j] > vec[i]) {
temp = vec[i];
vec[i] = vec[j];
vec[j] = temp;
}
}
}
}
long end = System.currentTimeMillis();
System.out.println("選擇法用時為：" + (end - begin));
//打印排序好的結果
for (int i = 0; i < vec.length; i++) {
System.out.println(vec[i]);
}
}
}選擇排序法與冒泡排序法一樣，最外層循環仍然要執行n-1次，其效率仍然較差。該算法的時間復雜度為 O(n2)。并且排序是穩定的。
7、八 選擇類排序--堆排序
7.1、堆的概念： 一棵完全二叉樹，任一個非終端結點的值均小于等于(或大于等于)其左、右兒子結點的值。堆分為大頂堆和小頂堆，滿足Key[i]>=Key[2i+1]&&key>=key[2i+2]稱為大頂堆，滿足Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]稱為小頂堆。由上述性質可知大頂堆的堆頂的關鍵字肯定是所有關鍵字中最大的，小頂堆的堆頂的關鍵字是所有關鍵字中最小的。
例：
7.2、用大根堆排序的基本思想
①先將初始文件R[1..n]建成一個大根堆，此堆為初始的無序區；
②再將關鍵字最大的記錄R[1]（即堆頂）和無序區的最后一個記錄R[n]交換，由此得到新的無序區R[1..n-1]和有序區R[n]，且滿足R[1..n-1].keys≤R[n].key；
③由于交換后新的根R[1]可能違反堆性質，故應將當前無序區R[1..n-1]調整為堆。然后再次將R[1..n-1]中關鍵字最大的記錄R[1]和該區間的最后一個記錄R[n-1]交換，由此得到新的無序區R[1..n-2]和有序區R[n-1..n]，且仍滿足關系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調整為堆。
……
直到無序區只有一個元素為止。
（2）大根堆排序算法的基本操作：
①初始化操作：將R[1..n]構造為初始堆；
②每一趟排序的基本操作：將當前無序區的堆頂記錄R[1]和該區間的最后一個記錄交換，然后將新的無序區調整為堆（亦稱重建堆）。
7.3、基本排序過程：
1. 將序列構造成一棵完全二叉樹 ；
2. 把這棵普通的完全二叉樹改造成堆，便可獲取最小值 ；
3. 輸出最小值或者最大值；
4. 刪除根結點，繼續改造剩余樹成堆，便可獲取次小值 ；
5. 輸出次小值 ；
6. 重復改造，輸出次次小值、次次次小值，直至所有結點均輸出，便得到一個排序 。
7.4、算法基本實現（看了很多人寫的算法，本人覺得這種算法蠻好）：
public class HeapSort {
public static int heap_size;
// 左孩子編號
public static int leftChild(int i) {
return 2 * i+1;
}
// 右孩子編號
public static int rightChild(int i) {
return 2 * i + 2;
}
/**
* 保持最大堆的性質
* 堆中的數組元素
* 對以該元素為根元素的堆進行調整，假設前提：左右子樹都是最大堆
* 由于左右孩子都是最大堆，首先比較根元素與左右孩子，找出最大值，假如大于根元素，則調整兩個元素的值；
* 由于左孩子（右孩子）的值與根元素交換，有可能打破左子樹（右子樹）的最大堆性質，因此繼續調用，直至葉子元素。
*/
public static void max_heapify(int[] a, int i) {
int left = leftChild(i);
int right = rightChild(i);
int largest = 0;
if (left < heap_size && a[i] < a[left]) {
largest = left;
} else {
largest = i;
}
if (right < heap_size && a[right] > a[largest]) {
largest = right;
}
if (largest == i) {
return;
} else {
int temp = a[i];
a[i] = a[largest];
a[largest] = temp;
max_heapify(a, largest);
}
}
/**
* 建立最大堆。在數據中，下標a.length/2+1一直到最后的元素a.length-1都是葉子元素
* 因此從其前一個元素開始，一直到
* 第一個元素，重復調用max_heapify函數，使其保持最大堆的性質
*/
public static void build_max_heap(int[] a) {
//從0~a.length/2中建立最大堆
for (int i = a.length / 2; i >= 0; i--)
{
max_heapify(a, i);
}
}
/**
* 堆排序：首先建立最大堆，然后將堆頂元素（最大值）與最后一個值交換，同時使得 堆的長度減小1
* 調用保持最大堆性質的算法調整，使得堆頂元素成為最大值，此時最后一個元素已被排除在外、
*/
public static void heapSort(int[] a) {
//構建最大堆
build_max_heap(a);
for (int i = a.length - 1; i >= 0; i--)
{
//將第一個元素和最后一個元素進行互換
int temp = a[0];
a[0] = a[i];
a[i] = temp;
heap_size--;
//調整堆為最大堆
max_heapify(a, 0);
}
}
public static void main(String[] args) {
int a[] = {5, 4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
long begin = System.currentTimeMillis();
for (int k = 0; k < 1000000; k++) {
heap_size = a.length;//最大數
heapSort(a);
//輸出結果
}
long end = System.currentTimeMillis();
System.out.println("選擇法用時為：" + (end - begin));
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
}7.5、算法討論：從上述過程可知，堆排序其實也是一種選擇排序，是一種樹形選擇排序。只不過直接選擇排序中，為了從R[1...n]中選擇最大記錄，需比較n-1次，然后從R[1...n-2]中選擇最大記錄需比較n-2次。事實上這n-2次比較中有很多已經在前面的n-1次比較中已經做過，而樹形選擇排序恰好利用樹形的特點保存了部分前面的比較結果，因此可以減少比較次數。對于n個關鍵字序列，最壞情況下每個節點需比較log2(n)次，因此其最壞情況下時間復雜度為nlogn。堆排序為不穩定排序，不適合記錄較少的排序。
8、二路歸并排序
8.1、歸并排序（Merge）是將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。
歸并---合并兩個有序的序列假設有兩個已排序好的序列A（長度為n1），B（長度為n2），將它們合并為一個有序的序列C（長度為n=n1+n2)
方法很簡單：把A，B兩個序列的最小元素進行比較，把其中較小的元素作為C的第一個元素；在A，B剩余的元素中繼續挑最小的元素進行比較，確定C的第二個元素，依次類推，就可以完成對A和B的歸并，其復雜度為O(n)。
例如：
A: 1 3 8 9 11
B: 2 5 7 10 13
C: 1 2 3 5 7 8 9 10 11 13
8.2、歸并排序：
1、遞歸基礎：若序列只有一個元素，則它是有序的，不執行任何操作
2、遞歸步驟：
先把序列劃分成長度基本相等的兩個序列
對每個子序列遞歸排序
把排好序的子序列歸并成最后的結果
例如：
初始序列： [8，4，5，6，2，1，7，3]
分解： [8，4，5，6] [2，1，7，3]
分解： [8，4] [5，6] [2，1] [7，3]
分解： [8] [4] [5] [6] [2] [1] [7] [3]
歸并： [4，8] [5，6] [1，2] [3，7
歸并： [4，5，6， 8] [1，2，3，7]
歸并： [1，2，3， 4，5，6，7，8]
8.3、算法具體實現：
import java.util.Arrays;
//二路歸并排序主要分為
//分割和合并
public class MergeSort {
public static void main(String[] args) {
int data[] = { 2, 6, 10, 3, 9, 80, 1, 16, 27, 20 };
mergeSort(data,0,data.length-1);
//直接打印
System.out.println(Arrays.toString(data));
}
//二路歸并的分割處理
public static void mergeSort(int[] array,int start,int end)
{
if(start<end)
{
//劃分為兩部分，每次兩部分進行歸并
int mid=(start+end)/2;
//兩路歸并
//先遞歸處理每一個部分
mergeSort(array,start,mid);
mergeSort(array,mid+1,end);
//然后將已經排序好的，兩兩歸并排序再進行合并處理
merge(array,start,mid,mid+1,end);
}
}
//二路歸并兩個部分的時候進行排序
public static void merge(int[] array,int start1,int end1,int start2,int end2)
{
int i=start1;//左路起始索引
int j=start2;//右路起始索引
int k=0;
//歸并的時候，會將兩個數組數據按照大小輸入到一個臨時數組中
//建立臨時長度為兩個子列表長度的數組
int[] temp=new int[end2-start1+1];
//循環遍歷，按順序找出兩個表中的最小數據依次放入臨時表中
//注意此時左路和右路已經是有序的了。
//當一路有一個小的，則會索引加1，繼續喝另外一路的上次索引進行比較
while(i<=end1&&j<=end2)
{
//這里確定歸并的次序大小
if(array[i]>array[j])
temp[k++]=array[j++];
else
temp[k++]=array[i++];
}
//把剩下的元素放入臨時數組中，只有一路的
while(i<=end1)
temp[k++]=array[i++];
while(j<=end2)
temp[k++]=array[j++];
k=start1;
for(int item:temp)
array[k++]=item;
}
}8．4、算法分析：歸并排序先分解要排序的序列，從1分成2，2分成4，依次分解，當分解到只有1個一組的時候，就可以排序這些分組，然后依次合并回原來的序列中，這樣就可以排序所有數據。合并排序比堆排序稍微快一點，但是需要比堆排序多一倍的內存空間，因為它需要一個額外的數組。
盡管歸并排序最壞情況的比較次數比快速排序少，但它需要更多的元素移動，因此，它在實用中不一定比快速排序快
9、基數排序
9.1基數排序是一種借助多關鍵字排序的思想對單邏輯關鍵字進行排序的方法。最典型的應該就是撲克牌問題。
基數排序就是借助于“分配”和“收集”兩種操作實現對單邏輯關鍵字的排序。
首先，單邏輯關鍵字通常都可以看作是由若干關鍵字復合而成。
例，若關鍵字是數值，且值域為 0≤K≤999，故可以將 K 看作是由 3 個關鍵字 K0 K1 K2組成；
例，603是由 6 0 3 組成。
其次，利用 LSDF 法實現對若干關鍵字的排序。
例，序列 278 109 063 930 589 184 505 269 008 083
各種排序算法的總結和比較
一、時間性能
按平均的時間性能來分，有三類排序方法：
時間復雜度為O(nlogn)的方法有：快速排序、堆排序和歸并排序，其中以快速排序為最好；
時間復雜度為O(n2)的有：直接插入排序、起泡排序和簡單選擇排序，其中以直接插入為
最好，特別是對那些對關鍵字近似有序的記錄序列尤為如此；
當待排記錄序列按關鍵字順序有序時，直接插入排序和起泡排序能達到O(n)的時間復雜
度;而對于快速排序而言，這是最不好的情況，此時的時間性能蛻化為O(n2)，因此是應
該盡量避免的情況。
簡單選擇排序、堆排序和歸并排序的時間性能不隨記錄序列中關鍵字的分布而改變。
二、空間性能
指的是排序過程中所需的輔助空間大小。
1. 所有的簡單排序方法(包括：直接插入、起泡和簡單選擇)和堆排序的空間復雜度為O(1)；
2. 快速排序為O(logn)，為棧所需的輔助空間;
3. 歸并排序所需輔助空間最多，其空間復雜度為O(n);
三、排序方法的穩定性能
1. 穩定的排序方法指的是，對于兩個關鍵字相等的記錄，它們在序列中的相對位置，在
排序之前和經過排序之后，沒有改變。
2. 當對多關鍵字的記錄序列進行LSD方法排序時，必須采用穩定的排序方法。
3. 對于不穩定的排序方法，只要能舉出一個實例說明即可。
4. 希爾排序、快速排序和堆排序是不穩定的排序方法
四、應用
歸并排序很難用于主存排序，主要問題在于：合并兩個排序的表需要線性附加內存，在整個算法中還要花費將數據拷貝到臨時數組再拷貝回來這樣一些附加的工作，其結果嚴重放慢了排序的速度。
對于重要的內部排序應用而言，應選擇快速排序。
快排和歸并排序都是分治的遞歸算法。
對于很小的數組（N<=20），快速排序不如插入排序好。
1 快速排序（QuickSort）
快速排序是一個就地排序，分而治之，大規模遞歸的算法。從本質上來說，它是歸并排序的就地版本。快速排序可以由下面四步組成。
（1） 如果不多于1個數據，直接返回。
（2） 一般選擇序列最左邊的值作為支點數據。
（3） 將序列分成2部分，一部分都大于支點數據，另外一部分都小于支點數據。
（4） 對兩邊利用遞歸排序數列。
快速排序比大部分排序算法都要快。盡管我們可以在某些特殊的情況下寫出比快速排序快的算法，但是就通常情況而言，沒有比它更快的了。快速排序是遞歸的，對于內存非常有限的機器來說，它不是一個好的選擇。
2 歸并排序（MergeSort）
歸并排序先分解要排序的序列，從1分成2，2分成4，依次分解，當分解到只有1個一組的時候，就可以排序這些分組，然后依次合并回原來的序列中，這樣就可以排序所有數據。合并排序比堆排序稍微快一點，但是需要比堆排序多一倍的內存空間，因為它需要一個額外的數組。
3 堆排序（HeapSort）
堆排序適合于數據量非常大的場合（百萬數據）。
堆排序不需要大量的遞歸或者多維的暫存數組。這對于數據量非常巨大的序列是合適的。比如超過數百萬條記錄，因為快速排序，歸并排序都使用遞歸來設計算法，在數據量非常大的時候，可能會發生堆棧溢出錯誤。
堆排序會將所有的數據建成一個堆，最大的數據在堆頂，然后將堆頂數據和序列的最后一個數據交換。接下來再次重建堆，交換數據，依次下去，就可以排序所有的數據。
4 Shell排序（ShellSort）
Shell排序通過將數據分成不同的組，先對每一組進行排序，然后再對所有的元素進行一次插入排序，以減少數據交換和移動的次數。平均效率是O(nlogn)。其中分組的合理性會對算法產生重要的影響。現在多用D.E.Knuth的分組方法。
Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相對比較簡單，它適合于數據量在5000以下并且速度并不是特別重要的場合。它對于數據量較小的數列重復排序是非常好的。
5 插入排序（InsertSort）
插入排序通過把序列中的值插入一個已經排序好的序列中，直到該序列的結束。插入排序是對冒泡排序的改進。它比冒泡排序快2倍。一般不用在數據大于1000的場合下使用插入排序，或者重復排序超過200數據項的序列。
6 冒泡排序（BubbleSort）
冒泡排序是最慢的排序算法。在實際運用中它是效率最低的算法。它通過一趟又一趟地比較數組中的每一個元素，使較大的數據下沉，較小的數據上升。它是O(n^2)的算法。
7 交換排序（ExchangeSort）和選擇排序（SelectSort）
這兩種排序方法都是交換方法的排序算法，效率都是 O(n2)。在實際應用中處于和冒泡排序基本相同的地位。它們只是排序算法發展的初級階段，在實際中使用較少。
8 基數排序（RadixSort）
基數排序和通常的排序算法并不走同樣的路線。它是一種比較新穎的算法，但是它只能用于整數的排序，如果我們要把同樣的辦法運用到浮點數上，我們必須了解浮點數的存儲格式，并通過特殊的方式將浮點數映射到整數上，然后再映射回去，這是非常麻煩的事情，因此，它的使用同樣也不多。而且，最重要的是，這樣算法也需要較多的存儲空間。
9 總結
下面是一個總的表格，大致總結了我們常見的所有的排序算法的特點。
|
排序法 |
平均時間 |
最差情形 |
穩定度 |
額外空間 |
備注 |
|
冒泡 |
O(n2) |
O(n2) |
穩定 |
O(1) |
n小時較好 |
|
交換 |
O(n2) |
O(n2) |
不穩定 |
O(1) |
n小時較好 |
|
選擇 |
O(n2) |
O(n2) |
不穩定 |
O(1) |
n小時較好 |
|
插入 |
O(n2) |
O(n2) |
穩定 |
O(1) |
大部分已排序時較好 |
|
基數 |
O(logrd) |
O(logrd) |
穩定 |
O(n) |
d是關鍵字項數(0-9)， r是基數(個十百) |
|
Shell |
O(nlogn) |
O(ns) 1<s<2 |
不穩定 |
O(1) |
s是所選分組 |
|
快速 |
O(nlogn) |
O(n2) |
不穩定 |
O(nlogn) |
n大時較好 |
|
歸并 |
O(nlogn) |
O(nlogn) |
穩定 |
O(1) |
n大時較好 |
|
堆 |
O(nlogn) |
O(nlogn) |
不穩定 |
O(1) |
n大時較好 |
來自： http://blog.csdn.net//u011067360/article/details/17684729