排序算法的實作及性能分析
——（java版）
排序是對資料元素序列建立某種有序排列的過程。更确切的說，排序是把一個資料元素序列整理成按關鍵字遞增（或遞減）排列的過程。
不過首先，我們必須先解釋一下關鍵字這個詞。關鍵字是要排序的資料元素集合中的一個域，排序是以關鍵字為基準進行的。而關鍵字也分為主關鍵字和次關鍵字。對于要排序的資料元素集合來說，如果關鍵字滿足資料元素值不同時，該關鍵字也不同，這樣的關鍵字稱為主關鍵字。不滿足主關鍵字定義的就稱為次關鍵字。
簡單來說，排序分為内部排序和外部排序兩種。内部排序是把待排序的資料元素全部調入記憶體中進行的排序。如果資料元素的數量過大，需要分批導入記憶體，分批導入記憶體的資料元素排好序後在分批導出到磁盤和錄音帶外媒體上的排序方法稱為外部排序。在本篇部落格中将隻讨論分析内部排序算法的性能。
那麼通常比較内部排序算法優劣的标準有如下3個：
<!--[if !supportlists]-->（1）<!--[endif]-->時間複雜度。時間複雜度是衡量排序算法好壞最重要的标準，它是一個函數，定量描述了某個算法的運作時間，時間複雜度通常使用大o符号表述，比如說直接插入排序算法的最差時間複雜度為o(n^2)。
<!--[if !supportlists]-->（2）<!--[endif]-->空間複雜度。空間複雜度用于衡量算法中使用額外記憶體空間的多少。當排序算法中使用的額外記憶體空間與要排序資料元素的個數n無關時，其空間複雜度為o(1)，大多數排序算法的空間複雜度都為o(1)。
<!--[if !supportlists]-->（3）<!--[endif]-->穩定性。當使用主關鍵字排序時，任何排序算法對相同的資料元素序列的排序結果必定是相同的。但使用次關鍵字排序時，其排序結果有可能相同，也用可能不同。設待排序的資料元素共有n個，設ki和kj分表表示第i個資料元素的關鍵字和第j個資料元素的關鍵字，設ri和rj分别表示第i個資料元素和第j個資料元素。若ki=kj，且在排序之前資料元素ri排在資料元素rj之前，在排序之後資料元素ri仍然排在資料元素rj之前的排序算法稱為穩定的排序算法，否則稱為不穩定的排序算法。
常見的内部排序算法有以下幾種：
<!--[if !supportlists]-->（1）<!--[endif]-->直接插入排序；
<!--[if !supportlists]-->（2）<!--[endif]-->希爾排序；
<!--[if !supportlists]-->（3）<!--[endif]-->直接選擇排序；
<!--[if !supportlists]-->（4）<!--[endif]-->堆排序；
<!--[if !supportlists]-->（5）<!--[endif]-->冒泡排序；
<!--[if !supportlists]-->（6）<!--[endif]-->快速排序；
<!--[if !supportlists]-->（7）<!--[endif]-->歸并排序；
<!--[if !supportlists]-->（8）<!--[endif]-->基數排序；
直接插入排序
基本思想：順序地将待排序的資料元素按其值得大小插入到已排序的資料元素子集合的适當位置。
實作代碼：
public class insertsort {
public int[] insertsort(int[] a){
int i,j,temp;
int n = a.length;
for(i = 0;i < n-1;i++){
temp = a[i+1];
j = i;
while(j > -1 && temp <= a[j]){
a[j+1] = a[j];
j--;
}
a[j+1] = temp;
}
return a;
}
}
直接插入排序算法的時間複雜度在o(n)和o(n^2)之間，即最好情況下是o(n)，最壞情況下是o(n^2)，其空間複雜度是o(1)，是一種穩定的排序算法。
希爾排序
基本思想：把待排序的資料元素分為若幹個小組，對同一組内的資料元素用直接插入排序；小組的個數逐次遞減；當完成了所有資料元素都在一個組内的排序後排序過程結束。希爾排序又稱為縮小增量排序。
示範效果圖：
public class shellsort {
/**
* 希爾排序實作方法
* @param a 需要排序的數組
* @param d 增量數組
* @param numofd 增量數組的長度
* @return
*/
public int[] shellsort(int[]a,int[]d,int numofd){
int i,j,k,m,span;
int temp;
for(m = 0;m < numofd;m++){
span = d[m];
for(k = 0;k < span;k++){
for(i = k;i < n - span;i = i + span){
temp = a[i + span];
j = i;
while(j > -1&&temp <= a[j]){
a[j + span] = a[j];
j = j - span;
}
a[j + span] = temp;
}
希爾排序的時間複雜度是o(n(lbn)^2)，空間複雜度是o(1)，由于希爾排序是按增量分組進行的排序，兩個相同的資料元素有可能分在不同的組内，是以希爾排序算法是一種不穩定的排序算法。
直接選擇排序
基本思想：從待排序的資料元素集合中選取最小的資料元素并将它與原始資料元素集合中的第一個資料元素交換位置；然後從不包括第一個位置上的資料元素集合中選取最小的資料元素并将它與原始資料元素集合中的第二個資料元素交換位置；如此重複，知道資料元素集合隻剩下一個資料元素為止。
動态示範圖：
public class selectsort {
* 不穩定的直接插入排序算法
* @param a 待排序數組
* @return 已排序數組
public int[] selectsort(int[] a){
int i,j,min;
for(i = 0;i < n - 1;i++){
min = i;
//找出無序區中最小元素
for(j = i + 1;j < n;j++){
if(a[j] < a[min]){
min = j;
//将無序區的最小元素與無序區第一個元素交換位置
if(min != i){//當最小元素為i時不交換位置
temp = a[i];
a[i] = a[min];
a[min] = temp;
public int[] selectsort2(int[] a){
temp = a[min];
for(j = min;j > i;j--){
a[j] = a[j-1];
a[i] = temp;
直接選擇排序算法的時間複雜度是o(n^2),其空間複雜度o(1)，直接選擇排序算法是不穩定的排序算法，這是由于每次從無序區下半選出最小元素後，與無序區第一個元素交換而引起的，因為交換可能引起相同的資料元素位置發生變化。如果在選出最小元素後，将它前面的無序記錄依次後移，然後再将最小記錄放在有序區的後面，這樣就能保證排序算法的穩定性
堆排序
在直接選擇排序中，放在數組的n個資料元素排成一個線性序列(即線性結構)，要從有n個資料元素的數組中選擇出一個最小的資料元素需要比較n-1次，如果能把待排序的資料元素集合構造成一個完全二叉樹結構，則每次選擇出一個最大(或最小)的資料元素隻需比較完全二叉樹的高度次，即lbn次。
基本思想：循環執行過程（1）——（3）直到數組為空為止。
<!--[if !supportlists]-->(1)<!--[endif]-->把堆頂a[0]元素(最大元素)和目前最大堆的最後一個元素交換；
<!--[if !supportlists]-->(2)<!--[endif]-->最大堆元素個數減一；
<!--[if !supportlists]-->(3)<!--[endif]-->調節新的堆使之滿足最大堆的定義。
動态示範：
* 保持最大堆的性質
* @param a 原始元素序列
* @param n 數組的長度，即待排序元素的個數
* @param h 以h為根結點元素下标
*/
public static void createheap(int[] a,int n,int h){
int i,j,flag;
int temp;
i = h;
j = 2 * i + 1;
temp = a[i];
flag = 0;
//沿左右孩子較大者重複向下篩選
while(j < n&&flag != 1){
//尋找左右孩子結點中的較大者，j為其下标
if(j < n - 1&&a[j] < a[j+1]){
j++;
if(temp > a[j]){
flag = 1;
}else{
a[i] = a[j];
i = j;
j = 2 * i + 1;
a[i] = temp;
public static void initcreateheap(int[] a){
int n = a.length;
for(int i = (n - 1) / 2;i >= 0;i--){
createheap(a, n, i);
public static int[] heapsort(int[] a){
initcreateheap(a);
for(int i = n - 1;i > 0;i--){
temp = a[0];
a[0] = a[i];
a[i] = temp;
createheap(a, i, 0);
return a;
推排序算法的時間複雜度是o(nlbn),其空間複雜度是o(1),而且該算法是一種不穩定的排序算法。
冒泡排序
基本思想：設數組a中存放了n個資料元素，循環進行n-1次如下的排序過程：第一次時，依次比較相鄰兩個資料元素a[i]和a[i+1](i=0,1,2……,n-2)，若為逆序，即a[i]>a[i+1]，則交換兩個資料元素，否則不交換，這樣數值最大的資料元素将被放置在a[n-1]中。第2次時，循環次數減一，即資料元素個數為n-1，操作方法和第一次的類似，這樣整個n個資料元素集合中數值較大的資料元素将放置在a[n-2]中。當第n-1次結束時，整個n個資料元素中較小的資料元素中次小的資料元素将被放置在a[1]中，a[0]中放置了最小的資料元素。
public static int[] bubblesort(int[] a){
int i,j,flag = 1;
for(i = 1;i < n&&flag == 1;i++){
flag = 0;
for(j = 0;j < n - i;j++){
if(a[j] > a[j+1]){
flag = 1;
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
冒泡排序算法最好情況的時間複雜度是o(n)，最壞情況下的時間複雜度是o(n^2)，而冒泡排序算法的空間複雜度是o(1)，冒泡排序算法是一種穩定的排序算法。
快速排序
基本思想：設數組a中存放了n個資料元素，low為數組的低端下标，high為數組的高端下标，從數組a中任取一個元素(通常取a[low])作為标準元素，以該标準元素為基準來調整數組a中其他各個元素的位置，使排在标準元素前面的元素均小于标準元素，排在标準元素後面均大于或等于标準元素。這樣一次排序過程結束後，一方面将标準元素為中心分為了兩個子數組，位于标準元素左邊子數組中的元素均小于标準元素，位于标準元素右邊子數組中的元素均大于或等于标準元素。對于這兩個子數組中的元素分别在進行方法類同的遞歸快速排序。算法的遞歸出口條件是low>=high。
動态示範:
public static int[] quicksort(int[] a,int low,int high){
int i,j;
i = low;
j = high;
temp = a[low];
while(i < j){
//在數組右端開始掃描
while(i < j&&temp <= a[j]){
if(i < j){
a[i] = a[j];
i++;
//在數組左端開始掃描
while(i < j&&a[i] < temp){
a[j] = a[i];
if(low < i){
quicksort(a, low, i-1);
if(i < high){
quicksort(a, j+1, high);
快速排序的時間複雜度是o(nlbn),空間複雜度為o(lbn),最壞情況下的空間複雜度是o(n)，而且該排序算法是一種不穩定的排序算法。
歸并排序
基本思想：設數組a中存放了n個資料元素，初始時我們把它們看成是n個長度為1的有序子數組，然後從第一個子數組開始，把相鄰的子樹組兩兩合并，得到n/2個（若n/2為小數則向上取整）長度為2的新的有序子數組（當n為奇數時最後一個新的有序子數組的長度為1）;對這些新的有序子數組在兩兩歸并，如此重複，直到得到一個長度為n的有序數組為止。
/**
* 歸并排序的實作
* @param swap 在排序過程中用于存放數組
* @param k 第一個有序子數組的長度
public static void merge(int[] a,int[] swap,int k){
int m = 0,u1,l2,i,j,u2;
int l1 = 0;//是第一個有界數組的下界為0
while(l1 + k <= n - 1){
l2 = l1 + k;//計算第二個有序子數組下界
u1 = l2 - 1;//計算第一個有序子數組上界
u2 = (l2 + k - 1 <= n - 1)?l2 + k -1:n - 1;//計算第二個有序子數組上界
for(i = l1,j = l2;i <= u1&&j <= u2;m++){
if(a[i] <= a[j]){
swap[m] = a[i];
i++;
}else{
swap[m] = a[j];
j++;
//子數組2已歸并完畢，将子數組1中剩餘的元素存放到數組swap中
while(i <= u1){
swap[m] = a[i];
m++;
//子數組1已歸并完畢，将子數組2中剩餘的元素存放到數組swap中
while(j <= u2){
swap[m] = a[j];
j++;
l1 = u2 + 1;
//将原數組中隻夠一組的資料元素存放在數組swap中
for(i = l1;i < n;i++,m++){
swap[m] = a[i];
public static int[] mergesort(int[] a){
int i;
int k = 1;//歸并長度從1開始
int[] swap = new int[n];
while(k < n){
merge(a,swap,k);
for(i = 0;i < n;i++){
a[i] = swap[i];
k = 2*k;//歸并長度翻倍
對n個元素進行一次二路歸并排序時，歸并的次數約為lbn，任何一次的二路歸并排序元素的比較次數都約為n-1，是以，二路歸并排序算法的時間複雜度是o(nlbn)；二路歸并排序時使用了n個臨時記憶體空間存放資料元素，是以，二路歸并排序算法的空間複雜度是o(n)。二路歸并排序算法是一種穩定的排序算法。
基數排序
基數排序也成為桶排序，是一種當待排序資料元素為整數類型時非常高效的排序方法。
基本思想：設待排序的資料元素是m位d進制整數（不足m位的在高位補0），設定n個桶，令其編号分别為0,1,2，…，d-1。首先按最低位(即個位)的數值一次把各資料元素放到相應的桶中，然後按照桶号從小到大和進入桶中資料元素的先後次序手機配置設定在各桶中的資料元素，這樣就形成了資料元素集合的一個新的排列，我們稱這樣的一次排序過程為一次基數排序；對一次基數排序得到的資料元素序列再按次低位(即十位)的數值一次把各資料元素放到相應的桶中，然後按照桶号從小到大和進入桶中資料元素的先後次序收集配置設定在各桶中的資料元素；這樣的過程重複進行，當完成了第m次基數排序後，就得到了排好序的資料元素序列。
* 基數排序的實作方法
* @param a 尚未排序的方法
* @param m 資料元素的最大位數
* @param d 進制的基數
* @return 已排好序的數組
* @throws exception 抛出異常
public static int[] radixsort(int[] a,int m,int d) throws exception{
int i,j,k,l,power = 1;
linqueue[] queue_sort = new linqueue[d];
//建立鍊式隊列數組對象
for(i = 0;i < d;i++){
linqueue queue = new linqueue();
queue_sort[i] = queue;
//進行m次排序
for(i = 0;i < m;i++){
if(i == 0){
power = 1;
}else{
power = power * d;
//一次将n個資料元素按第k為的大小放到相應的隊列中
for(j = 0;j < n;j++){
k = a[j]/power - (a[j]/(power * d)) * d;//計算k值
queue_sort[k].insert(new integer(a[j]));//将a[j]存儲到隊列k中
//順序回收各隊列中的資料元素到數組a中
l = 0;
for(j = 0;j < d;j++){
while(queue_sort[j].notempty()){
a[l] = ((integer)queue_sort[j].delete()).intvalue();
l++;
//生成100個從零到1000的随機數
public static int[] random(int[] a){
for(int i = 0;i < 100;i++){
a[i] = (int)(math.random()*1000);
system.out.print(" a["+i+"]:"+a[i]);
基數排序算法的時間複雜度為o（m*n），該排序算法的空間複雜度是o(n),并且基數排序算法是一種穩定的排序算法。
各排序算法的性能比較
排序算法
最好時間複雜度
平均時間複雜度
最壞時間複雜度
空間複雜度
穩定性
插入排序
o(n)
o(n^2)
o(1)
穩定
o(n^1.3)
不穩定
選擇排序
o(nlbn)
o(lbn)
o(m*n)