十種JAVA排序算法實例

更新時間：2013年11月14日 15:38:12 作者：

本文件講了十種JAVA排序方法(冒泡（Bubble）排序——相鄰交換、選擇排序——每次最小/大排在相應(yīng)的位置、插入排序——將下一個插入已排好的序列中、殼（Shell）排序——縮小增量、歸并排序、快速排序、堆排序、拓撲排序、錦標賽排序、基數(shù)排序)的使用，并提供了實例代碼可參考

排序算法有很多，所以在特定情景中使用哪一種算法很重要。為了選擇合適的算法，可以按照建議的順序考慮以下標準：
（1）執(zhí)行時間
（2）存儲空間
（3）編程工作
對于數(shù)據(jù)量較小的情形，（1）（2）差別不大，主要考慮（3）；而對于數(shù)據(jù)量大的，（1）為首要。

一、冒泡（Bubble）排序

復制代碼代碼如下:

void BubbleSortArray() 
{ 
      for(int i=1;i<n;i++) 
      { 
        for(int j=0;i<n-i;j++) 
         { 
              if(a[j]>a[j+1])//比較交換相鄰元素 
               { 
                   int temp; 
                   temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; 
               } 
         } 
      } 
} 

效率 O（n²）,適用于排序小列表。

二、選擇排序

復制代碼代碼如下:

void SelectSortArray() 
{ 
    int min_index; 
    for(int i=0;i<n-1;i++) 
    { 
         min_index=i; 
         for(int j=i+1;j<n;j++)//每次掃描選擇最小項 
            if(arr[j]<arr[min_index])  min_index=j; 
         if(min_index!=i)//找到最小項交換，即將這一項移到列表中的正確位置 
         { 
             int temp; 
             temp=arr[i]; arr[i]=arr[min_index]; arr[min_index]=temp; 
} 
} 
} 

效率O（n²），適用于排序小的列表。

三、插入排序

復制代碼代碼如下:

void InsertSortArray() 
{ 
for(int i=1;i<n;i++)//循環(huán)從第二個數(shù)組元素開始，因為arr[0]作為最初已排序部分 
{ 
    int temp=arr[i];//temp標記為未排序第一個元素 
    int j=i-1; 
while (j>=0 && arr[j]>temp)/*將temp與已排序元素從小到大比較，尋找temp應(yīng)插入的位置*/ 
{ 
    arr[j+1]=arr[j]; 
    j--; 
} 
arr[j+1]=temp; 
} 
} 

最佳效率O（n）；最糟效率O（n²）與冒泡、選擇相同，適用于排序小列表
若列表基本有序，則插入排序比冒泡、選擇更有效率。

復制代碼代碼如下:

void ShellSortArray() 
{ 
  for(int incr=3;incr<0;incr--)//增量遞減，以增量3，2，1為例 
{ 
       for(int L=0;L<(n-1)/incr;L++)//重復分成的每個子列表 
{ 
   for(int i=L+incr;i<n;i+=incr)//對每個子列表應(yīng)用插入排序 
   { 
      int temp=arr[i]; 
      int j=i-incr; 
      while(j>=0&&arr[j]>temp) 
      { 
          arr[j+incr]=arr[j]; 
          j-=incr; 
} 
arr[j+incr]=temp; 
} 
} 
} 
} 

適用于排序小列表。
效率估計O（nlog2^n）~O（n^1.5），取決于增量值的最初大小。建議使用質(zhì)數(shù)作為增量值，因為如果增量值是2的冪，則在下一個通道中會再次比較相同的元素。
殼（Shell）排序改進了插入排序，減少了比較的次數(shù)。是不穩(wěn)定的排序，因為排序過程中元素可能會前后跳躍。

復制代碼代碼如下:

 
void MergeSort(int low,int high) 
{ 
   if(low>=high)   return;//每個子列表中剩下一個元素時停止 
   else int mid=(low+high)/2;/*將列表劃分成相等的兩個子列表,若有奇數(shù)個元素，則在左邊子列表大于右側(cè)子列表*/ 
   MergeSort(low,mid);//子列表進一步劃分 
   MergeSort(mid+1,high); 
   int [] B=new int [high-low+1];//新建一個數(shù)組，用于存放歸并的元素 
   for(int i=low,j=mid+1,k=low;i<=mid && j<=high;k++)/*兩個子列表進行排序歸并，直到兩個子列表中的一個結(jié)束*/ 
   { 
       if (arr[i]<=arr[j];) 
{ 
    B[k]=arr[i]; 
    I++; 
} 
else
    { B[k]=arr[j]; j++; } 
} 
for(   ;j<=high;j++,k++)//如果第二個子列表中仍然有元素，則追加到新列表 
      B[k]=arr[j]; 
   for(   ;i<=mid;i++,k++)//如果在第一個子列表中仍然有元素，則追加到新列表中 
      B[k]=arr[i]; 
   for(int z=0;z<high-low+1;z++)//將排序的數(shù)組B的 所有元素復制到原始數(shù)組arr中 
      arr[z]=B[z]; 
} 

效率O（nlogn），歸并的最佳、平均和最糟用例效率之間沒有差異。
適用于排序大列表，基于分治法。

復制代碼代碼如下:

/*快速排序的算法思想：選定一個樞紐元素，對待排序序列進行分割，分割之后的序列一個部分小于樞紐元素，一個部分大于樞紐元素，再對這兩個分割好的子序列進行上述的過程。*/                  void swap(int a,int b){int t;t =a ;a =b ;b =t ;} 
        int Partition(int [] arr,int low,int high) 
        { 
            int pivot=arr[low];//采用子序列的第一個元素作為樞紐元素 
            while (low < high) 
            { 
                //從后往前栽后半部分中尋找第一個小于樞紐元素的元素 
                while (low < high && arr[high] >= pivot) 
                { 
                    --high; 
                } 
                //將這個比樞紐元素小的元素交換到前半部分 
                swap(arr[low], arr[high]); 
                //從前往后在前半部分中尋找第一個大于樞紐元素的元素 
                while (low <high &&arr [low ]<=pivot ) 
                { 
                    ++low ; 
                } 
                swap (arr [low ],arr [high ]);//將這個樞紐元素大的元素交換到后半部分 
            } 
            return low ;//返回樞紐元素所在的位置 
        } 
        void QuickSort(int [] a,int low,int high) 
        { 
            if (low <high ) 
            { 
                int n=Partition (a ,low ,high ); 
                QuickSort (a ,low ,n ); 
                QuickSort (a ,n +1,high ); 
            } 
        } 

平均效率O（nlogn），適用于排序大列表。
此算法的總時間取決于樞紐值的位置；選擇第一個元素作為樞紐，可能導致O（n²）的最糟用例效率。若數(shù)基本有序，效率反而最差。選項中間值作為樞紐，效率是O（nlogn）。
基于分治法。

七、堆排序
最大堆：后者任一非終端節(jié)點的關(guān)鍵字均大于或等于它的左、右孩子的關(guān)鍵字，此時位于堆頂?shù)墓?jié)點的關(guān)鍵字是整個序列中最大的。
思想：
(1)令i=l,并令temp＝ kl ;
(2)計算i的左孩子j=2i+1;
(3)若j<＝n－1，則轉(zhuǎn)(4),否則轉(zhuǎn)(6);
(4)比較kj和kj+1,若kj+1>kj,則令j＝j(luò)＋1，否則j不變；
(5)比較temp和kj，若kj>temp，則令ki等于kj，并令i=j,j=2i+1,并轉(zhuǎn)(3),否則轉(zhuǎn)(6)
(6)令ki等于temp，結(jié)束。

復制代碼代碼如下:

void HeapSort(SeqIAst R) 

    {
    //對R[1..n]進行堆排序，不妨用R[0]做暫存單元   
    int I;    BuildHeap(R)；
    //將R[1-n]建成初始堆for(i=n;i>1；i--) //對當前無序區(qū)R[1..i]進行堆排序，共做n-1趟。
    {     
    R[0]=R[1]; R[1]=R[i]; R[i]=R[0]; //將堆頂和堆中最后一個記錄交換      Heapify(R,1,i-1);  //將R[1..i-1]重新調(diào)整為堆，僅有R[1]可能違反堆性質(zhì)   
    }   
    }
 

堆排序的時間，主要由建立初始堆和反復重建堆這兩部分的時間開銷構(gòu)成，它們均是通過調(diào)用Heapify實現(xiàn)的。
堆排序的最壞時間復雜度為O(nlgn)。堆排序的平均性能較接近于最壞性能。由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。堆排序是就地排序，輔助空間為O(1)，它是不穩(wěn)定的排序方法。

堆排序與直接插入排序的區(qū)別:
直接選擇排序中，為了從R[1..n]中選出關(guān)鍵字最小的記錄，必須進行n-1次比較，然后在R[2..n]中選出關(guān)鍵字最小的記錄，又需要做n-2次比較。事實上，后面的n-2次比較中，有許多比較可能在前面的n-1次比較中已經(jīng)做過，但由于前一趟排序時未保留這些比較結(jié)果，所以后一趟排序時又重復執(zhí)行了這些比較操作。
堆排序可通過樹形結(jié)構(gòu)保存部分比較結(jié)果，可減少比較次數(shù)。

八、拓撲排序
例：學生選修課排課先后順序
拓撲排序：把有向圖中各頂點按照它們相互之間的優(yōu)先關(guān)系排列成一個線性序列的過程。
方法：
在有向圖中選一個沒有前驅(qū)的頂點且輸出
從圖中刪除該頂點和所有以它為尾的弧
重復上述兩步，直至全部頂點均已輸出（拓撲排序成功），或者當圖中不存在無前驅(qū)的頂點（圖中有回路）為止。

復制代碼代碼如下:

void TopologicalSort()/*輸出拓撲排序函數(shù)。若G無回路，則輸出G的頂點的一個拓撲序列并返回OK，否則返回ERROR*/ 
{ 
      int indegree[M]; 
      int i,k,j; 
      char n; 
      int count=0; 
      Stack thestack; 
      FindInDegree(G,indegree);//對各頂點求入度indegree[0....num] 
      InitStack(thestack);//初始化棧 
      for(i=0;i<G.num;i++) 
          Console.WriteLine("結(jié)點"+G.vertices[i].data+"的入度為"+indegree[i]); 
      for(i=0;i<G.num;i++) 
      { 
           if(indegree[i]==0) 
              Push(thestack.vertices[i]); 
      } 
      Console.Write("拓撲排序輸出順序為："); 
      while(thestack.Peek()!=null) 
      { 
               Pop(thestack.Peek()); 
               j=locatevex(G,n); 
               if (j==-2) 
                  { 
                         Console.WriteLine("發(fā)生錯誤，程序結(jié)束。"); 
                         exit(); 
                  } 
                Console.Write(G.vertices[j].data); 
                count++; 
                for(p=G.vertices[j].firstarc;p!=NULL;p=p.nextarc) 
                { 
                     k=p.adjvex; 
                     if (!(--indegree[k])) 
                         Push(G.vertices[k]); 
                } 
      } 
      if (count<G.num) 
          Cosole.WriteLine("該圖有環(huán)，出現(xiàn)錯誤，無法排序。"); 
      else
          Console.WriteLine("排序成功。"); 
} 

算法的時間復雜度O（n+e）。

九、錦標賽排序
錦標賽排序的算法思想與體育比賽類似。
首先將n個數(shù)據(jù)元素兩兩分組，分別按關(guān)鍵字進行比較，得到n／2個比較的優(yōu)勝者(關(guān)鍵字小者)，作為第一步比較的結(jié)果保留下來，
然后對這n／2個數(shù)據(jù)元素再兩兩分組，分別按關(guān)鍵字進行比較，…，如此重復，直到選出一個關(guān)鍵字最小的數(shù)據(jù)元素為止。

復制代碼代碼如下:

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <math.h> 
#define SIZE 100000 
#define MAX 1000000 
struct node 
{ 
 long num;//關(guān)鍵字 
 char str[10]; 
 int lastwin;//最后勝的對手 
 int killer;//被擊敗的對手 
 long times;//比賽次數(shù) 
}data[SIZE]; 
long CompareNum=0; 
long ExchangeNum=0; 
long Read(char name[])//讀取文件a.txt中的數(shù)據(jù)，并存放在數(shù)組data[]中；最后返回數(shù)據(jù)的個數(shù) 
{ 
 FILE *fp; 
 long i=1; 
 fp=fopen(name,"rw"); 
 fscanf(fp,"%d%s",&data[i].num,data[i].str); 
 while(!feof(fp)) 
 { 
  i++; 
  fscanf(fp,"%d%s",&data[i].num,data[i].str);  
 } 
 return (i-1); 
} 
long Create(long num)//創(chuàng)建勝者樹，返回冠軍（最小數(shù)）在數(shù)組data[]中的下標 
{ 
 int i,j1,j2,max,time=1; 
 long min;//記錄當前冠軍的下標 
 for(i=1;pow(2,i-1)<num;i++) 

 max=pow(2,i-1);//求葉子結(jié)點數(shù)目 
 for(i=1;i<=max;i++)//初始化葉子結(jié)點 
 { 
  data[i].killer=0; 
  data[i].lastwin=0; 
  data[i].times=0; 
  if(i>num) 
   data[i].num=MAX; 
 } 
 for(i=1;i<=max;i+=2)//第一輪比賽 
 { 
  ++CompareNum; 
  if(data[i].num <= data[i+1].num) 
  { 
   data[i].lastwin = i+1; 
   data[i+1].killer=i; 
   ++data[i].times; 
   ++data[i+1].times; 
   min=i; 
  } 
  else
  { 
   data[i+1].lastwin=i; 
   data[i].killer=i+1; 
   ++data[i].times; 
   ++data[i+1].times; 
   min=i+1; 
  } 
 } 
 j1=j2=0;//記錄連續(xù)的兩個未被淘汰的選手的下標 
 while(time <= (log(max)/log(2)))//進行淘汰賽 
 { 
  for(i=1;i<=max;i++) 
  { 
   if(data[i].times==time && data[i].killer==0)//找到一名選手 
   { 
    j2=i;//默認其為兩選手中的后來的 
    if(j1==0)//如果第一位置是空的，則剛來的選手先來的 
     j1=j2; 
    else//否則剛來的選手是后來的，那么選手都已到場比賽開始 
    { 
     ++CompareNum; 
     if(data[j1].num <= data[j2].num)//先來的選手獲勝 
     { 
      data[j1].lastwin = j2;//最后贏的是j2 
      data[j2].killer=j1;//j2是被j1淘汰的 
      ++data[j1].times; 
      ++data[j2].times;//兩選手場次均加1  
      min=j1;//最小數(shù)下標為j1 
      j1=j2=0;//將j1，j2置0 
     } 
     else//同理 
     { 
      data[j2].lastwin=j1; 
      data[j1].killer=j2; 
      ++data[j1].times; 
      ++data[j2].times;      
      min=j2; 
      j1=j2=0; 
     } 
    } 
   } 

  } 
  time++;//輪數(shù)加1 
 } 
 return min;//返回冠軍的下標 
} 
void TournamentSort(long num)//錦標賽排序 
{ 
 long tag=Create(num);//返回最小數(shù)下標 
 FILE *fp1; 
 fp1=fopen("sort.txt","w+");//為寫入創(chuàng)建并打開文件sort.txt 
 while(data[tag].num != MAX)//當最小值不是無窮大時 
 { 
  printf("%d %s\n",data[tag].num,data[tag].str);//輸出數(shù)據(jù) 
  fprintf(fp1,"%d %s\n",data[tag].num,data[tag].str);//寫入數(shù)據(jù) 
  data[tag].num=MAX;//將當前冠軍用無窮大替換 
  tag=Create(num);//返回下一個冠軍的下標  
 } 
} 
int main() 
{ 
 int num; 
 char name[10]; 
 printf("Input name of the file:"); 
 gets(name); 
 num=Read(name);//讀文件 
 TournamentSort(num);//錦標賽排序 
 printf("CompareNum=%d\nExchangeNum=%d\n",CompareNum,ExchangeNum); 
 return 0; 
} 

十、基數(shù)排序
基數(shù)排序又被稱為桶排序。與前面介紹的幾種排序方法相比較，基數(shù)排序和它們有明顯的不同。
    前面所介紹的排序方法都是建立在對數(shù)據(jù)元素關(guān)鍵字進行比較的基礎(chǔ)上，所以可以稱為基于比較的排序；
    而基數(shù)排序首先將待排序數(shù)據(jù)元素依次“分配”到不同的桶里，然后再把各桶中的數(shù)據(jù)元素“收集”到一起。
通過使用對多關(guān)鍵字進行排序的這種“分配”和“收集”的方法，基數(shù)排序?qū)崿F(xiàn)了對多關(guān)鍵字進行排序。
例：
    每張撲克牌有兩個“關(guān)鍵字”：花色和面值。其大小順序為：
    花色：§＜¨＜©＜ª
    面值：2＜3＜……＜K＜A
    撲克牌的大小先根據(jù)花色比較，花色大的牌比花色小的牌大；花色一樣的牌再根據(jù)面值比較大小。所以，將撲克牌按從小到大的次序排列，可得到以下序列：
§2，…，§A，¨2，…，¨A，©2，…，©A，ª2，…，ªA
    這種排序相當于有兩個關(guān)鍵字的排序，一般有兩種方法實現(xiàn)。
    其一：可以先按花色分成四堆（每一堆牌具有相同的花色），然后在每一堆牌里再按面值從小到大的次序排序，最后把已排好序的四堆牌按花色從小到大次序疊放在一起就得到排序的結(jié)果。
其二：可以先按面值排序分成十三堆（每一堆牌具有相同的面值），然后將這十三堆牌按面值從小到大的順序疊放在一起，再把整副牌按順序根據(jù)花色再分成四堆（每一堆牌已按面值從小到大的順序有序），最后將這四堆牌按花色從小到大合在一起就得到排序的結(jié)果。
實現(xiàn)方法：
　　最高位優(yōu)先(Most Significant Digit first)法，簡稱MSD法：先按k1排序分組，同一組中記錄，關(guān)鍵碼k1相等，再對各組按k2排序分成子組，之后，對后面的關(guān)鍵碼繼續(xù)這樣的排序分組，直到按最次位關(guān)鍵碼kd對各子組排序后。再將各組連接起來，便得到一個有序序列。
　　最低位優(yōu)先(Least Significant Digit first)法，簡稱LSD法：先從kd開始排序，再對kd-1進行排序，依次重復，直到對k1排序后便得到一個有序序列。

復制代碼代碼如下:

　　using System; 
　　using System.Collections.Generic; 
　　using System.Linq; 
　　using System.Text; 
　　namespace LearnSort 
　　{ 
　　class Program 
　　{ 
　　static void Main(string[] args) 
　　{ 
　　int[] arr = CreateRandomArray(10);//產(chǎn)生隨機數(shù)組 
　　Print(arr);//輸出數(shù)組 
　　RadixSort(ref arr);//排序 
　　Print(arr);//輸出排序后的結(jié)果 
　　Console.ReadKey(); 
　　} 
　　public static void RadixSort(ref int[] arr) 
　　{ 
　　int iMaxLength = GetMaxLength(arr); 
　　RadixSort(ref arr, iMaxLength); 
　　} 
　　private static void RadixSort(ref int[] arr, int iMaxLength) 
　　{ 
　　List<int> list = new List<int>();//存放每次排序后的元素 
　　List<int>[] listArr = new List<int>[10];//十個桶 
　　char currnetChar;//存放當前的字符比如說某個元素123 中的2 
　　string currentItem;//存放當前的元素比如說某個元素123 
　　for (int i = 0; i < listArr.Length; i++)//給十個桶分配內(nèi)存初始化。 
　　listArr[i] = new List<int>(); 
　　for (int i = 0; i < iMaxLength; i++)//一共執(zhí)行iMaxLength次，iMaxLength是元素的最大位數(shù)。 
　　{ 
　　foreach (int number in arr)//分桶 
　　{ 
　　currentItem = number.ToString();//將當前元素轉(zhuǎn)化成字符串 
　　try { currnetChar = currentItem[currentItem.Length-i-1]; }//從個位向高位開始分桶 
　　catch { listArr[0].Add(number); continue; }//如果發(fā)生異常，則將該數(shù)壓入listArr[0]。比如說5 是沒有十位數(shù)的，執(zhí)行上面的操作肯定會發(fā)生越界異常的，這正是期望的行為，我們認為5的十位數(shù)是0，所以將它壓入listArr[0]的桶里。 
　　switch (currnetChar)//通過currnetChar的值，確定它壓人哪個桶中。 
　　{ 
　　case '0': listArr[0].Add(number); break; 
　　case '1': listArr[1].Add(number); break; 
　　case '2': listArr[2].Add(number); break; 
　　case '3': listArr[3].Add(number); break; 
　　case '4': listArr[4].Add(number); break; 
　　case '5': listArr[5].Add(number); break; 
　　case '6': listArr[6].Add(number); break; 
　　case '7': listArr[7].Add(number); break; 
　　case '8': listArr[8].Add(number); break; 
　　case '9': listArr[9].Add(number); break; 
　　default: throw new Exception("unknow error"); 
　　} 
　　} 
　　for (int j = 0; j < listArr.Length; j++)//將十個桶里的數(shù)據(jù)重新排列，壓入list 
　　foreach (int number in listArr[j].ToArray<int>()) 
　　{ 
　　list.Add(number); 
　　listArr[j].Clear();//清空每個桶 
　　} 
　　arr = list.ToArray<int>();//arr指向重新排列的元素 
　　//Console.Write("{0} times:",i); 
　　Print(arr);//輸出一次排列的結(jié)果 
　　list.Clear();//清空list 
　　} 
　　} 
　　//得到最大元素的位數(shù) 
　　private static int GetMaxLength(int[] arr) 
　　{ 
　　int iMaxNumber = Int32.MinValue; 
　　foreach (int i in arr)//遍歷得到最大值 
　　{ 
　　if (i > iMaxNumber) 
　　iMaxNumber = i; 
　　} 
　　return iMaxNumber.ToString().Length;//這樣獲得最大元素的位數(shù)是不是有點投機取巧了... 
　　} 
　　//輸出數(shù)組元素 
　　public static void Print(int[] arr) 
　　{ 
　　foreach (int i in arr) 
　　System.Console.Write(i.ToString()+'\t'); 
　　System.Console.WriteLine(); 
　　} 
　　//產(chǎn)生隨機數(shù)組。隨機數(shù)的范圍是0到1000。參數(shù)iLength指產(chǎn)生多少個隨機數(shù) 
　　public static int[] CreateRandomArray(int iLength) 
　　{ 
　　int[] arr = new int[iLength]; 
　　Random random = new Random(); 
　　for (int i = 0; i < iLength; i++) 
　　arr[i] = random.Next(0,1001); 
　　return arr; 
　　} 
　　} 
　　} 