排序 Sorting

學習目標 在學習本章之後，讀者們要能夠瞭解： 排序的定義及種類。 各種排序資料結構演算法。 各種排序的比較。

 簡介 排序(Sorting)是指一群資料按照某一個排列規則，重新安排此群資料的次序，使其相對於此規則具有一種遞增(或遞減)性質的線性次序關係。 排序可分成下列兩大類： 內部排序(Internal Sorting)：意指資料量小，可以直接放在記憶體內進行。 外部排序(External Sorting)：意指資料量大，無法直接存放在記憶體，必須先存放於輔助記憶體內再處理。

其中內部排序的方法常見的有： 插入排序法(Insertion Sort) 選擇排序法(Selection Sort) 氣泡排序法(Bubble Sort) 謝耳排序法(Shell Sort) 快速排序法(Quick Sort) 合併排序法(Merge Sort) 累堆排序法(Heap Sort) 基數排序法(Radix Sort)

若按演算法的時間複雜度，以及鍵值的比較方式，又可將這些內部排序區分為下面三種模式： 簡單排序技巧： 選擇排序、插入排序、謝耳排序及氣泡排序。 謝耳的平均時間複雜度為O(n(logn)2)及最差時間複雜度為O(Ns)，1<s<2 選擇排序、插入排序及氣泡排序平均時間複雜度及最差時間複雜度均為O(n2)。

高等排序技巧： 使用的方法是每次比較兩個鍵值後，便分成兩個部份，而選擇其中一部份先處理，即決策樹(Decision Tree)型式。 有快速排序、合併排序、累堆排序 除了快速排序最差時間複雜度為O(n2)，其他的平均時間複雜度及最差時間複雜度均為O(nlogn)。 基數排序技巧： 屬於分配性排序之一，此方法的平均時間複雜度為O(nlogpk)， 最差時間複雜度則為O(nlogpk)~ O(n) 其中p為所使用基底(Base,Radix)，k為數值的位數。

插入排序法 (Insertion Sort)

定義 插入排序法的基本運算是將一個元素插入一串已排序的元素之中，使該串元素仍然按順序排列。 掃瞄已排序好的串列 若找到元素小於這個欲插入的元素，將元素向下移動以空出一個位置。 當掃瞄到某一元素大於欲插入值，則掃瞄停止，較大之元素之後剛好有一空位可被插入。

基本運算 index 1 2 3 4 5 i 60 70 15 40 80 99 說明 60不變 70插入陣列中index為0的位置 1 2 3 4 5 i 60 70 15 40 80 99 說明 60不變 70插入陣列中index為0的位置 15不變 40插入陣列中index為2的位置 80插入陣列中index為0的位置 99插入陣列中index為0的位置

演算法 ＝＞虛擬程式碼 演算法則如下： procedure insertionsort(int data[ ], int n) { index i, j ; int item ; for (i 從1~ n-1) { 每次將data[i]中的元素當成欲加入的元素; 從已排序完的陣列的最後 { 從前尋找可以加入的地方; 將所有元素往後位移一格; 　　 } } }

＝＞C語言程式碼 insertionsrot(int data[ ], int n) { index i, j ,item; for (i=1; i<n; i++) /*共n+1次*/ { item=data[i]; j=i; /*當data[i]小於前面排好的資料時,將較大的資料 往後移*/ while (j>0 && a[j-1]>item) { data[j]=data[j-1]; j- -; data[j] = item; /*將a[i]插入適當位置*/ } } }

＝＞時間複雜度分析 插入排序是相當穩定的 最壞時間和平均時間複雜度皆為O(n2) 所需的額外空間很少。

程式範例－插入排序 # include <studio.h> void insertion_sort ( int [ ], int ) ; void main ( ) { int data [20] ; int size = 0, i; printf ( “\nPlease enter number to sort (enter 0 when end):\n ) ; printf ( “Number : “ )

do { scanf ( “%d “, &data [size] ); } while (data [size ++] != 0 ) ; for ( i = 0; i < 60 ; i ++ ) printf ( “－” ) ; printf ( “\nSorting : “ ); for ( I = 0; I < size ; i ++) printf ( “%d “, data [i] ); }

void insertion_sort (int data[ ], int size ) { int base, compare, temp, i; for (base = 1; base < size ; base ++) temp = data [base] ; compare = base ; while ( compare > 0 && data [compare – 1] > temp)

{ data [compare] = data [compare – 1]; compare - -; } data [compare] = temp ; printf ( “Access : “) ; for ( I = 0; i < size ; i ++) printf ( “%d “, data [i]) ; printf ( “\n” ) ;

氣泡排序法 (Bubble Sort)

定義 氣泡排序可說是最簡單的排序法之一 屬於交換排序(Swap sort)的方法 一開始資料都都放在同一個陣列中，比較相鄰的陣列元素大小，依照排序來決定是否交換彼此的值，這樣的比較從輸入陣列的第一個元素開始，跟相鄰元素比大小。

基本運算 泡沫排序的基本運算是將一對相鄰的元素互換。 整個排序過程由許多回合構成，每一回合由陣列的一端開始，向另一端執行互換。每對元素若其順序相反時，則兩者互換

index 1 2 3 4 5 i 60 70 15 40 80 99 (a) 原始資料 (b) 第一次排序 (c) (d) (e) (f) 第二次排序 第三次排序 第四次排序 第五次排序(結束)

演算法 ＝＞虛擬程式碼 Bubble_sort(int a[ ], int size) { for (pass = size-1 to 1) for ( j = 1 to size – 1) if (a[ j ]＞a[ j+1 ] 交換a[ j ] , a[ j+1 ] }

＝＞C語言程式碼 Bubble_sort(int a[ ], int size) { int i , j , t; for (i = size-1; i＞0 ; i- -) for ( j = 0; j＜1; j + +) if (a[ j ]＞a[ j+1 ] t＝a[ j ]; a[ j ]＝a[ j+1 ]; a[ j+1 ]＝t; }

＝＞時間複雜度分析 氣泡排序是相當穩定的 最壞時間和平均時間複雜度皆為O(n2)， 所需的額外空間很少。

程式範例 #include <stdio.h> #define n 10 // 定義陣列大小 void bubble(int *);       // 氣泡排序副程式 void show(int *);         // 列印陣列 void main() { int data[n] = {9,1,7,3,4,8,6,2,5,0}; printf("The default is :"); show(data);              // 印出預設陣列 bubble(data);            // 執行氣泡排序法 printf("The answer is :"); show(data);              // 印出答案 }

void bubble(int *data) { int temp,i,j,flag; for (i=n-1;i>=0;i--)                // 變數i遞減 flag = 0;                // 設定交換次數為0次 for (j=0;j< i;j++) if(data[j] > data[j+1])           // 當data[j] > data[j+1]執行交換 printf("\ndata[%d] > data[%d]",j ,j+1); printf(" data[%d],data[%d] swap,",j ,j+1); temp = data[j+1]; data[j+1] = data[j]; data[j] = temp; flag++;  // 如果有交換過執行flag++; }

else                           // 當data[j] <= data[j+1]不交換 { printf("\ndata[%d] <=data[%d]",j ,j+1); printf(" data[%d],data[%d] not swap",j,j+1); } if(flag==0)                //flag為0表示沒有交換過,現在的陣列即為所求 break;

printf("\nThe %d time is :",-(i-n));      // 印出回合次數 show(data);                    // 印出執行此回合後陣列情況 printf("\n"); } void show(int *data) { int i; for(i=0;i< n;i++) printf("%d,",*(data+i));

選擇排序法 (Selection Sort)

定義 選擇排序從輸入的陣列中選擇最大（或最小）的值，移到輸出陣列中，原來儲存最大（或最小）值的陣列元素則以0代之，這樣的操作一直進行到所有陣列元素都被輸出為止。

原選擇排序

選擇排序使用了兩個陣列，假如把選擇排序和交換排序的技巧合在一起，只要使用一個陣列，由於每一輪都有一個元素就定位，下一輪要處理的元素數目就少一個，因此，改良以後的排序方法執行的效率也比較好。

改良後的選擇排序

基本運算 選擇排序法（selection sort）的基本運算是由一連串的元素中選出一個最小元素（或是最大元素）。

index 1 2 3 4 5 i 60 70 15 40 99 80 原始資料 第一次排序 第二次排序 第三次排序 第四次排序 第五次排序(結束)

演算法 ＝＞虛擬程式碼 select_sort (int a[ ], int size) { index i , j ; for (i = n –1到1) 最大值 = data [0] ; for ( j = 1 到 i) if ( a[ j ]＞最大值 ) 最大值 = a [ j ] ; } 將a [ j ]與 a [ i ]的資料互換 ;

＝＞C語言程式碼 select_sort(int a[ ], int size) { int i, j , index, larger; //在1~i的數中，將最大的數放到a [i ]中// for (i = n-1 ; I>0 ; i--) larger= a[0]; index =0; for (j=1; j<=i; j + +)

if(a[j]>larger) { larger = a[j]; index = ; } a[index] = a[i]; a[i] = larger;

＝＞時間複雜度分析 外層迴路需執行n-1次，內層共n-i次， 每次需執行一個比較運算及可能的指定運算。執行時間為： 此法無論資料原始排列方式如何，總需 O(n2 )的比較運算。 其資料移動次數最多是O(n)次。

選擇排序程式範例 #include <stdio.h> #define n 10 void selection(int *);            // 傳入陣列作選擇排序 void show(int *);                 // 列印陣列 void main() { int data[n] = {9,1,7,3,4,8,6,2,5,0}; printf("The default is :"); show(data); selection(data); printf("The answer is :"); }

void selection(int *data) { int temp,i,j,flag; for (i=0;i< n;i++) for (j=i;j< n;j++) if(data[i] > data[j])         // 當data[i] > data[j]時交換 printf("\ndata[%d] > data[%d]",i ,j); printf(" data[%d],data[%d] swap,",i ,j); temp = data[j]; data[j] = data[i]; data[i] = temp; } // 當data[i] <= data[j]時不交換

else { printf("\ndata[%d] <=data[%d]",i ,j); printf(" data[%d],data[%d] not swap",i ,j); } printf("\nThe %d time is :",i+1); show(data); printf("\n");

void show(int *data) { int i; for(i=0;i< n;i++) printf("%d,",*(data+i)); }

快速排序法 (Quick Sort)

定義 由C. A. R. Hoare 所創的快速排序法。 其主要的原理是利用遞迴概念，將陣列分成二部份： 第一部分中的所有元素的值都小於某一個預先選定的基準值(pivot)， 第二部分中的所有元素的值都大於基準值； 這二部分的資料再根據同樣的方式，再分別作快速排序。

基本運算 假設要排序的元素如下： K(1),K(2),……,K(n) 則快速排序法的一個步驟是將串列分割成兩個子串列

其演算的步驟： 若n=1，則return； 令分隔點K(p)為第一筆資料的值 由左向右找出一筆資料K(i)，使得K(i)＞K(p)； 由右向左找出一筆資料K(j)，使得K(j)＜K(p)； 若i＜j則K(i)與K(j)交換，並回到步驟２； 若i≧j，則將K(j)與K(p)交換，並以j為基點將資料分割成左右兩半，然後分別針對左右兩半進行步驟１～５。

演算法 ＝＞C語言程式碼 quick_sort(int a[ ], int l, int r) { int p, i, j, t ; if ( l < r) i = l +1 j = r ; p = a [ l ];

do { while (a [ i ] < p) i + +; while (a [ j ] > p) j - - ; if ( i < j ) { t = a [ i ]; a [ i ] = a [ j ] ; a [ j ] = t; }

while ( i < j ); a [ l ] = a [ j ]; a [ j ] = p ; qsort ( a, l, j – 1) ; qsort ( a, j + 1, r ) ; }

＝＞時間複雜度分析 最差情況： 若所選的pivot每次皆最小值，則執行時間

平均分析 假設所選的pivot將串列分成兩個子串列，其平均執行時間分別 為T(j)，和T(n-j-1)，j之值可能由1到n且機率皆相等，因此 T(n) = O(nlogn)

程式實例 #include <studio.h> void quick_sort ( int [ ], int ) ; void main ( ) { int data [20] ; int size = 0, i; printf ( “\nPlease enter number to sort (enter 0 when end):\n ) ; printf ( “Number : “ ) do { scanf ( “%d “, &data [size] ); } while (data [size ++] != 0 ) ; for ( i = 0; i < 60 ; i ++ ) printf ( “－” ) ; printf ( “\nSorting : “ ); for ( I = 0; I < size ; i ++) printf ( “%d “, data [i] ); }

void quick_sort (int data[ ], int left, int right, int size ) { int lbase, rbase, compare, temp, i; for (base = 1; base < size ; base ++) temp = data [base] ; compare = base ; while ( compare > 0 && data [compare – 1] > temp) data [compare] = data [compare – 1]; compare - -; } data [compare] = temp ; printf ( “Access : “) ; for ( I = 0; i < size ; i ++) printf ( “%d “, data [i]) ; printf ( “\n” ) ;