排序 Sorting.

Presentation on theme: "排序 Sorting."— Presentation transcript:

1 排序 Sorting

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

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

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

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

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

7 插入排序法 (Insertion Sort)

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

9 基本運算 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的位置

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

11 ＝＞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]插入適當位置*/ } } }

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

13 程式範例－插入排序 # 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 : “ )

14 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] ); }

15 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)

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

17 氣泡排序法 (Bubble Sort)

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

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

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

21 演算法 ＝＞虛擬程式碼 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 ] }

22 ＝＞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; }

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

24 程式範例 #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);              // 印出答案 }

25 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++; }

26 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;

27 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));

28 選擇排序法 (Selection Sort)

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

30 原選擇排序

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

32 改良後的選擇排序

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

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

35 演算法 ＝＞虛擬程式碼 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 ]的資料互換 ;

36 ＝＞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 + +)

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

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

39 選擇排序程式範例 #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 :"); }

40 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]時不交換

41 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");

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

43 快速排序法 (Quick Sort)

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

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

46 其演算的步驟： 若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為基點將資料分割成左右兩半，然後分別針對左右兩半進行步驟１～５。

47 演算法 ＝＞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 ];

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

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

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

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

52 程式實例 #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] ); }

53 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” ) ;