10種排序演算法總結 排序演算法有很多，所以在特定情景中使用哪一種演算法很重要。為了選擇合適的演算法，可以按照建議的順序考慮以下標準： （1）執行時間 （2）存儲空間 （3）編程工作 對於數據量較小的情形，（1）（2）差別不大，主要考慮（3）；而對於數據量大的，（1）為首要。 主要排序法有： 一、冒泡（Bu ...
10種排序演算法總結
排序演算法有很多，所以在特定情景中使用哪一種演算法很重要。為了選擇合適的演算法，可以按照建議的順序考慮以下標準：
（1）執行時間
（2）存儲空間
（3）編程工作
對於數據量較小的情形，（1）（2）差別不大，主要考慮（3）；而對於數據量大的，（1）為首要。
主要排序法有：
一、冒泡（Bubble）排序——相鄰交換
二、選擇排序——每次最小/大排在相應的位置
三、插入排序——將下一個插入已排好的序列中
四、殼（Shell）排序——縮小增量
五、歸併排序
六、快速排序
七、堆排序
八、拓撲排序
九、錦標賽排序
十、基數排序
一、冒泡（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++)//迴圈從第二個數組元素開始，因為arr[0]作為最初已排序部分 { int temp=arr[i];//temp標記為未排序第一個元素 int j=i-1; while (j>=0 && arr[j]>temp)/*將temp與已排序元素從小到大比較，尋找temp應插入的位置*/ { arr[j+1]=arr[j]; j--; } arr[j+1]=temp; } }
最佳效率O（n）；最糟效率O（n²）與冒泡、選擇相同，適用於排序小列表
若列表基本有序，則插入排序比冒泡、選擇更有效率。
四、殼（Shell）排序——縮小增量排序
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)//對每個子列表應用插入排序 { 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），取決於增量值的最初大小。建議使用質數作為增量值，因為如果增量值是2的冪，則在下一個通道中會再次比較相同的元素。
殼（Shell）排序改進了插入排序，減少了比較的次數。是不穩定的排序，因為排序過程中元素可能會前後跳躍。
五、歸併排序
void MergeSort(int low,int high) { if(low>=high) return;//每個子列表中剩下一個元素時停止 else int mid=(low+high)/2;/*將列表劃分成相等的兩個子列表,若有奇數個元素，則在左邊子列表大於右側子列表*/ MergeSort(low,mid);//子列表進一步劃分 MergeSort(mid+1,high); int [] B=new int [high-low+1];//新建一個數組，用於存放歸併的元素 for(int i=low,j=mid+1,k=low;i<=mid && j<=high;k++)/*兩個子列表進行排序歸併，直到兩個子列表中的一個結束*/ { 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++)//將排序的數組B的 所有元素複製到原始數組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²）的最糟用例效率。若數基本有序，效率反而最差。選項中間值作為樞紐，效率是O（nlogn）。
基於分治法。
七、堆排序
最大堆：後者任一非終端節點的關鍵字均大於或等於它的左、右孩子的關鍵字，此時位於堆頂的節點的關鍵字是整個序列中最大的。
思想：
(1)令i=l,並令temp＝ kl ;
(2)計算i的左孩子j=2i+1;
(3)若j<＝n－1，則轉(4),否則轉(6);
(4)比較kj和kj+1,若kj+1>kj,則令j＝j＋1，否則j不變；
(5)比較temp和kj，若kj>temp，則令ki等於kj，並令i=j,j=2i+1,並轉(3),否則轉(6)
(6)令ki等於temp，結束。
void HeapSort(SeqIAst R) { //對R[1..n]進行堆排序，不妨用R[0]做暫存單元 int I; BuildHeap(R);//將R[1-n]建成初始堆 for(i=n;i>1;i--) //對當前無序區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]重新調整為堆，僅有R[1]可能違反堆性質 } }
堆排序的時間，主要由建立初始堆和反覆重建堆這兩部分的時間開銷構成，它們均是通過調用Heapify實現的。
堆排序的最壞時間複雜度為O(nlgn)。堆排序的平均性能較接近於最壞性能。 由於建初始堆所需的比較次數較多，所以堆排序不適宜於記錄數較少的文件。 堆排序是就地排序，輔助空間為O(1)， 它是不穩定的排序方法。
堆排序與直接插入排序的區別:
直接選擇排序中，為了從R[1..n]中選出關鍵字最小的記錄，必須進行n-1次比較，然後在R[2..n]中選出關鍵字最小的記錄，又需要做n-2次比較。事實上，後面的n-2次比較中，有許多比較可能在前面的n-1次比較中已經做過，但由於前一趟排序時未保留這些比較結果，所以後一趟排序時又重覆執行了這些比較操作。
堆排序可通過樹形結構保存部分比較結果，可減少比較次數。
八、拓撲排序
例 ：學生選修課排課先後順序
拓撲排序：把有向圖中各頂點按照它們相互之間的優先關係排列成一個線性序列的過程。
方法：
在有向圖中選一個沒有前驅的頂點且輸出
從圖中刪除該頂點和所有以它為尾的弧
重覆上述兩步，直至全部頂點均已輸出（拓撲排序成功），或者當圖中不存在無前驅的頂點（圖中有迴路）為止。
void TopologicalSort()/*輸出拓撲排序函數。若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("結點"+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("發生錯誤，程式結束。"); 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("該圖有環，出現錯誤，無法排序。"); else Console.WriteLine("排序成功。"); }
演算法的時間複雜度O（n+e）。
九、錦標賽排序
錦標賽排序的演算法思想與體育比賽類似。
首先將n個數據元素兩兩分組，分別按關鍵字進行比較，得到n／2個比較的優勝者(關鍵字小者)，作為第一步比較的結果保留下來，
然後對這n／2個數據元素再兩兩分組，分別按關鍵字進行比較，…，如此重覆，直到選出一個關鍵字最小的數據元素為止。
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #define SIZE 100000 #define MAX 1000000 struct node { long num;//關鍵字 char str[10]; int lastwin;//最後勝的對手 int killer;//被擊敗的對手 long times;//比賽次數 }data[SIZE]; long CompareNum=0; long ExchangeNum=0; long Read(char name[])//讀取文件a.txt中的數據，並存放在數組data[]中；最後返回數據的個數 { 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)//創建勝者樹，返回冠軍（最小數）在數組data[]中的下標 { int i,j1,j2,max,time=1; long min;//記錄當前冠軍的下標 for(i=1;pow(2,i-1)<num;i++) ; max=pow(2,i-1);//求葉子結點數目 for(i=1;i<=max;i++)//初始化葉子結點 { 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;//記錄連續的兩個未被淘汰的選手的下標 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;//最小數下標為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++;//輪數加1 } return min;//返回冠軍的下標 } void TournamentSort(long num)//錦標賽排序 { long tag=Create(num);//返回最小數下標 FILE *fp1; fp1=fopen("sort.txt","w+");//為寫入創建並打開文件sort.txt while(data[tag].num != MAX)//當最小值不是無窮大時 { printf("%d %s\n",data[tag].num,data[tag].str);//輸出數據 fprintf(fp1,"%d %s\n",data[tag].num,data[tag].str);//寫入數據 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; }
十、基數排序
基數排序又被稱為桶排序。與前面介紹的幾種排序方法相比較，基數排序和它們有明顯的不同。
前面所介紹的排序方法都是建立在對數據元素關鍵字進行比較的基礎上，所以可以稱為基於比較的排序；
而基數排序首先將待排序數據元素依次“分配”到不同的桶里，然後再把各桶中的數據元素“收集”到一起。
通過使用對多關鍵字進行排序的這種“分配”和“收集”的方法，基數排序實現了對多關鍵字進行排序。
———————————————————————————————————————
例：
每張撲克牌有兩個“關鍵字”：花色和麵值。其大小順序為：
花色：§＜¨＜©＜ª
面值：2＜3＜……＜K＜A
撲克牌的大小先根據花色比較，花色大的牌比花色小的牌大；花色一樣的牌再根據面值比較大小。所以，將撲克牌按從小到大的次序排列，可得到以下序列：
§2，…，§A，¨2，…，¨A，©2，…，©A，ª2，…，ªA
這種排序相當於有兩個關鍵字的排序，一般有兩種方法實現。
其一：可以先按花色分成四堆（每一堆牌具有相同的花色），然後在每一堆牌里再按面值從小到大的次序排序，最後把已排好序的四堆牌按花色從小到大次序疊放在一起就得到排序的結果。
其二：可以先按面值排序分成十三堆（每一堆牌具有相同的面值），然後將這十三堆牌按面值從小到大的順序疊放在一起，再把整副牌按順序根據花色再分成四堆（每一堆牌已按面值從小到大的順序有序），最後將這四堆牌按花色從小到大合在一起就得到排序的結果。
———————————————————————————————————————
實現方法：
最高位優先(Most Significant Digit first)法，簡稱MSD法：先按k1排序分組，同一組中記錄，關鍵碼k1相等，再對各組按k2排序分成子組，之後，對後面的關鍵碼繼續這樣的排序分組，直到按最次位關鍵碼kd對各子組排序後。再將各組連接起來，便得到一個有序序列。
最低位優先(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);//產生隨機數組 Print(arr);//輸出數組 RadixSort(ref arr);//排序 Print(arr);//輸出排序後的結果 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++)//給十個桶分配記憶體初始化。 listArr[i] = new List<int>(); for (int i = 0; i < iMaxLength; i++)//一共執行iMaxLength次，iMaxLength是元素的最大位數。 { foreach (int number in arr)//分桶 { currentItem = number.ToString();//將當前元素轉化成字元串 try { currnetChar = currentItem[currentItem.Length-i-1]; }//從個位向高位開始分桶 catch { listArr[0].Add(number); continue; }//如果發生異常，則將該數壓入listArr[0]。比如說5 是沒有十位數的，執行上面的操作肯定會發生越界異常的，這正是期望的行為，我們認為5的十位數是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++)//將十個桶里的數據重新排列，壓入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);//輸出一次排列的結果 list.Clear();//清空list } } //得到最大元素的位數 private static int GetMaxLength(int[] arr) { int iMaxNumber = Int32.MinValue; foreach (int i in arr)//遍歷得到最大值 { if (i > iMaxNumber) iMaxNumber = i; } return iMaxNumber.ToString().Length;//這樣獲得最大元素的位數是不是有點投機取巧了... } //輸出數組元素 public static void Print(int[] arr) { foreach (int i in arr) System.Console.Write(i.ToString()+'\t'); System.Console.WriteLine(); } //產生隨機數組。隨機數的範圍是0到1000。參數iLength指產生多少個隨機數 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; } } }
基數排序法是屬於穩定性的排序，其時間複雜度為O (nlog(r)m)，其中r為所採取的基數，而m為堆數，在某些時候，基數排序法的效率高於其它的比較性排序法。
