sort

定義
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(輸家樹):各非端末節在多紀錄左右兒子的最大值



2007-03-05 18:56:12發表 2014-04-21 21:46:27修改   

數據分析
程式開發
計算機組織與結構
資料結構與演算法

Database and MySql
manage tool
windows
unix-like
linux service
network
network layer3
network layer2
network WAN
network service
作業系統
數位鑑識
資訊安全解決方案
資訊安全威脅
Cisco security
Cisco network
Cisco layer3
Cisco layer2



  登入      [牛的大腦] | [單字我朋友] Powered by systw.net