定義
stable sort(穩定的排序法):
若有相同資料，則相對位置不會改變
comparison sort:
用兩兩比對方式做排序的方法
comparison sort最快也至少要花n*log(n)的時間
一些not a comparison sort可比comparison sort快
常見的not a comparison sort有counting sort,radix sort,…
in-place
不需用藉由其他空間來處理排序
Adaptability
若數列已經有部分排過序了,則sorting的time complexity可降低
…………………………………………………
內部排序法
可分為
一般排序法
高等排序法
分配排序法
一般排序法
常見的有:insertion sort,bubble sort,selection sort
時間複雜度平均和最差都是O(N^2),額外空間都是O(1)
通常將資料視為前(己排好)後(需要排)兩部份
…..
insertion sort(插入排序法):逐步改良法
平均O(N^2),最差O(N^2),額外空間O(1),屬stable sort
比較與交換次數：
最多需要比較和交換1+2+…+(n-1)=n*(n-1)/2次(若資料排列和想要的順序完全相反)
最少只需比較n-1次，交換0次(若順序完全一樣),處理己排序資料效率最佳
平均情況是比較和交換n*(n-1)/4次
做法：
每次將後部份第一個資料和前部份最後資料比較，若大於則交換並繼續和下個值比較
若小於則前部份資料多1，而後部份資料少1，在重覆上述直到後部份資料為0
排序過程大致如下
step0:37,(1,5,26,12,60)
step1:1,37,(5,26,12,60)
step2:1,5,37,(26,12,60)
step3:1,5,26,37,(12,60)
step4:1,5,12,26,37,(60)
step5:1,5,12,26,37,60
…..
selection sort(選擇排序法):貪婪法
平均O(N^2),最差O(N^2),額外空間O(1),
比較與交換次數：
比較次數固定為n*(n-1)/2次
最多需要交換n-1次(若資料排列和想要的順序完全相反)
最少只需交換0次(若順序完全一樣)
平均情況只需交換(n-1)/2次
做法：
找1~n之間最小值和資料1交換，在找2~n之間的最小值和資料2交換….在找(n-1)~n間最小值和資料(n-1)交換
排序過程大致如下
step0:(37,1,5,26,12,60)
step1:1,(37,5,26,12,60)
step2:1,5,(37,26,12,60)
step3:1,5,12,(37,26,60)
step4:1,5,12,26,(37,60)
step5:1,5,12,26,37,(60)
…..
bubble sort(氣泡排序法):逐步改良法
平均O(N^2),最差O(N^2),額外空間O(1),屬stable sort
比較和交換和插入排序法一樣
做法：
每次將邊資料(頭或尾)視為min，然後min和下一個值比較，若小於就交換資料，若大於則把下一個值當min，
重覆上述步驟一直到比較到第1個資料，第2次則重覆上述步驟比較到第2個資料，一直到第n-1次
排序過程大致如下
step0:(24,26),3,9,45,1,12
step0.1:24,(3,26),9,45,1,12
step0.2:24,3,(9,26),45,1,12
step0.3:24,3,9,(26,45),1,12
step0.4:24,3,9,26,(1,45),12
step1:24,3,9,26,1,(12,45)
step2:3,9,24,1,12,26,45
step3:3,9,1,12,24,26,45
bubble_sort(int list[],int n){
int i,j;
for(i=1;i
for(j=1;j
if(list[j]>list[j+1]){swap(list[j],list[j+1])}
}
}
}
…………………..
高等排序法
內部排序法中最佳演算法(N 2底log N)
常見的有:快速排序法，二項合併排序法，堆積排序法
其他有:radix sort(基底排序法)
ps:
mergesort與heapsort都是asymptotically optimal sorting algorithm
他們的最好和最差情況下，時間複雜度一樣
…..
quick sort(快速排序法):
最佳平圴O(n 2底log n)額外空間O(2底log n)
最差O(n^2)額外空間O(n)
說明：
使用partition切割技巧，根據r值將資料切成前後兩部份，前面所有值小於資料r，後面所有值大於資料r，在遞迴對兩部份進行處理
由C.A.R hoare所發展，平圴複雜度是所有內部排序法中最佳的
做法：
1第1個資料r從左往右找大於r的資料s,假設位置=i，在從右往左找比r小的資料t,假設位置=j
2若i
3分別對資料r的前面部份與後面部分進行步驟1，2
排序過程大致如下
step0:(26,5,37,1,61,11,59,15,48,19)
step0.1:(26,5,19,1,61,11,59,15,48,37)
step0.2:(26,5,19,1,15,11,59,61,48,37)
step1:(11,5,19,1,15),26,(59,61,48,37) //以26為依據進行切割
step2:(1,5),11,(19,15),26,(59,61,48,37) //以11為依據進行切割
step3:1,5,11,(19,15),26,(59,61,48,37) //以1為依據進行切割
step4:1,5,11,15,19,26,(59,61,48,37) //以19為依據進行切割
step5:1,5,11,15,19,26,(48,37),59,61 //以59為依據進行切割
step6:1,5,11,15,19,26,37,48,59,61 //以48為依據進行切割
若資料個數為n，則切割複雜度為O(n)
worst case:切割後兩部份長度差異最大(當資料有排序時)複雜度最大(每次切割，一部份資料個數為n-1,另一部份資料個數為0)，且需要的堆疊空間是O(N)
最差情況遞迴關係式
t(n)={ t(n-1)+n,n>1 ;1,n=1
t(n)=t(n-1)+n=t(n-2)+(n-1)+n=…=t(1)+2+3+…+(n-1)+n=1+2+…+n=n*(n+1)/2=O(n^2)
best case:若切割後差異最小，複雜度越小，每次切割後兩部份資料個數大約都是n/2個，且需要的堆疊空間是O(2底log n)
最佳情況遞迴關係式 t(n)=2t(n/2)+n=…=O(n log2(n))
void quick_sort(int list[],int first,int last){
int left,right,key;
if(first < last){
left=first;right=last+1;key=list[first];
do{
do{left++;}while(list[left] < key); //從左往右找比資料key大的資料s,若把list跑完都沒有就到下一行
do{right–;}while(list[right] > key); //從右往左找比資料key小的資料t，若把list跑完都沒有就到下一行
if(left < right)swap(list[left],list[right]); //(沒掃描完),則將資料s和資料t交換
}while(left < right);
swap(list[first],list[right]); //(己掃描完)將資料key與資料t交換(此時資料key大於前面資料)
quick_sort(list,first,right-1);
quick_sort(list,right+1,last);
}
}
…..
merge sort(合併排序法):
平圴最佳最差O(n 2底log n),額外空間O(N),屬stable sort
做法：將串列視為n個長度1的己排序串列，由第一個開始進行兩兩合併，產生個數ceil(n/2)長度為2的己排序串列，反覆上述步驟一直到個數為1長度為n
排序過程大致如下
step0:(26),(5),(37),(2),(61),(10),(59),(16)
step1:(5,26),(2,37),(10,61),(16,59)
step2:(2,5,26,37),(10,16,59,61)
step3:(2,5,10,16,26,37,59,61)
若有n個資料，則每階段的合併複雜度等級固定O(n),而總共需要2底log n個階段
遞迴關係式：t(n)={2t(n/2)+n,n>1 ; 1,n=1
t(n)=2t(n/2)+n=2[2t(n/4)+n/2]+n=4t(n/4)+2n=…=(2^k)t(n/(2^k))+k*n=2^k*t(1)+k*n=n+n*log2(n),這裡假設2^k=n
演算法：
void merge_sort(){ //合併排序
}
void merge(){ //合併的副程式
}
…..
heap sort(堆積排序法):
平圴最差O(n 2底log n),額外空間O(1)
做法：
1將排序資料視為二元樹並變成max heap
2在把樹根和最後節點交換
3調整max heap(省略被換到最後的那些節點)複雜度為O(2底log n)
4重覆步驟2,3(會重覆n-1次)
不管資料是否排序，處理次數固定
演算法
void adjust(int list[],int position,int last){ //產生heap tree
int child;int large;
while(last>=2*position){
large=list[2*position];
child=2*position;
if(last>2*position){if(list[child+1]>larger)larger=list[++child]}
if(list[child]>list[position]){swap(list[child],list[position]);position=child;}
else{break;}
}
}
viod heapsort(int list[],int n){
int i,j;
int temp;
for(i=n/2;i>0;i–){ //將排序資料視為二元樹並變成heap tree
adjust(list,i,n);
}
for(i=n-1;i>0;i–){ //重覆n次步驟2
temp=list[1];
list[1]=list[i+1];
list[i+1]=temp;
adjust(list,1,i); //重覆n次步驟3
}
}
………………………………………………………………………………………..
分配排序法
也稱bin sort(容器排序法)
根據每個關鍵值的範圍，設立相同個數的容器，再根據資料的值，把資料分配到對應的容器，即可得到排序結果
the most significant digit first,msd主要關鍵值優先：各容器資料獨立地視為一組，各組須單獨進行排序
the least significant digit first,lsd次要關鍵值優先：所有容器資料視為一組，對所有資料進行排序
做法：如果要對基底為b,由d個數字組成的n個整數進行分配排序，則需d個階段，各階段要b個容器，將n個整數分配到對應的容器中
因此演算法複雜度等級是O(d*(n+b))
…………………………………………………………………………………………
…………………………………………………………………………………………
external sort(外部排序法)
因資料個數太多無法全放入主記憶體,所以存放在輔助記憶體在做排序
常見的排序法有:
磁碟排序法
磁帶排序法
磁碟排序法
分段排序：把輔助記憶體中要排序的資料分批輸入到主記憶體中，再用任一內部排序法將己排序的資料段輸出到輔助記憶體
分段合併：對輔助記憶體中排序好的資料合併，可將主記憶分成兩個輸入緩衝區(取兩個資料段)和一個輸出緩衝區(合併結果)，且會有多次輸入與輸出
若有nx筆己排序好的資料段，則需要ceil(log2(nx))個階段
若用二項合併，輸出入次數多，比較次數少，只需經過一次比較即可完成一個合併運作，整個合併需要比較1*n*log2(n)
若用m項合併，輸出入次數少，比較次數多，則需m-1次比較完成一個合併動作，整個合併需要比較(m-1)*n*logm(n)
選擇樹結構
各非端末節點的值等於左右兒子最小的值
需ceil(log2(m))次比較完成一個合併動作，整個合併需要比較n*log2(n)
loser tree(輸家樹):各非端末節在多紀錄左右兒子的最大值