- 選擇排序
排序前:70 80 31 37 10 1 48 60 33 80
- [1] 80 31 37 10 70 48 60 33 80 選出最小值1
- [1 10] 31 37 80 70 48 60 33 80 選出最小值10
- [1 10 31] 37 80 70 48 60 33 80 選出最小值31
- [1 10 31 33] 80 70 48 60 37 80 ......
- [1 10 31 33 37] 70 48 60 80 80 ......
- [1 10 31 33 37 48] 70 60 80 80 ......
- [1 10 31 33 37 48 60] 70 80 80 ......
- [1 10 31 33 37 48 60 70] 80 80 ......
- [1 10 31 33 37 48 60 70 80] 80 ......
- 氣泡排序法
基本的氣泡排序法可以利用旗標的方式稍微減少一些比較的時間,當尋訪完陣列後都沒有發生任何的交換動作,表示排序已經完成,而無需再進行之後的迴圈比較與交換動作,例如:
排序前:95 27 90 49 80 58 6 9 18 50
- 27 90 49 80 58 6 9 18 50 [95] 95浮出
- 27 49 80 58 6 9 18 50 [90 95] 90浮出
- 27 49 58 6 9 18 50 [80 90 95] 80浮出
- 27 49 6 9 18 50 [58 80 90 95] ......
- 27 6 9 18 49 [50 58 80 90 95] ......
- 6 9 18 27 [49 50 58 80 90 95] ......
- 6 9 18 [27 49 50 58 80 90 95] 由於接下來不會再發生交換動作,排序提早結束
概念大致了解了之後,實作看看吧:
#include <stdio.h> #include <stdlib.h> #include <time.h> #define SWAP(x,y) {int t; t = x; x = y; y = t;} //交換 void selectionSort(int number[]); // 選擇排序 void bubbleSort(int number[]); // 氣泡排序 int main(void) { int number[10], i, a; srand((unsigned)time(NULL)); printf("排序前:"); for(i=0; i<10; i++) { number[i]=rand()%100; printf("%d ", number[i]); } printf("\n選擇排序方式:\n"); printf("(1)選擇排序 (2)氣泡排序\n"); scanf("%d", &a); switch(a) { case 1: selectionSort(number); break; case 2: bubbleSort(number); break; default: return 0; break; } for(i=0; i<10; i++) printf("%d ", number[i]); printf("\n"); system("pause"); return 0; } void selectionSort(int number[]) { int i, j, m; for(i=0; i<9; i++) { m=i; for(j=i+1; j<10; j++) if(number[j]<number[m]) m=j; if(i!=m) SWAP(number[i], number[m]); } } void bubbleSort(int number[]) { int flag=1, i, j; for(i=0; i<9 && flag==1; i++) { flag=0; for(j=0; j<9-i; j++) if(number[j]>number[j+1]) { SWAP(number[j+1], number[j]); flag=1; } } }
沒有留言:
張貼留言