|
以下的程式包含四種內部搜尋法:Bubble Sort、Selection Sort、Insertion Sort、Quick Sort
程式開始會先以亂數產生十萬個數字
( #define _mexlen 100000 )
並讓使用者選擇排序使用的搜尋法
另外
因數字過多
排序的結果沒有印出
但是可以自己把 out(copy) 前面的註解拿掉
排序時
程式會自動紀錄系統時間
在排序後顯示花掉的時間
方便大家比較各種排序法的快慢
語言:C 語言
編譯器: DevC++ 4.9.9.2
- #include <stdio.h>
- #include <stdlib.h>
- #include <time.h>
- #define _maxlen 100000
- void out(int* in){
- int a;
- for(a=0;a<_maxlen;a++){
- printf("%4d",in[a]);
- if(a%19==18)
- printf("\n");
- }
- }
- void selectionSort(int* in){
- int a=0,b=0,min=0,tmp=0;;
- for(a=0;a<_maxlen;a++){
- for(b=a;b<_maxlen;b++){
- if(in[b]<in[min])
- min = b;
- }
- tmp = in[a];
- in[a] = in[min];
- in[min] = tmp;
- }
- }
- void insertionSort(int* in)
- {
- int first=0,last=_maxlen-1;
- int i,j,a;
- int temp;
- for (i = first+1; i<=last;i++){
- temp = in[i];
- j=i-1;
- while((j>=first) && (in[j] > temp)){
- in[j+1] = in[j];
- j--;
- }
- in[j+1] = temp;
- }
- }
- void bubbleSort(int* in){
- int a=0,b=0,tmp=0;
- for(a=0;a<_maxlen;a++){
- for(b=0;b<_maxlen-1;b++){
- if(in[b]>in[b+1]){
- tmp = in[b];
- in[b] = in[b+1];
- in[b+1] = tmp;
- }
- }
- }
- }
- void swap(int *a, int *b)
- {
- int t=*a; *a=*b; *b=t;
- }
- void quickSort(int number[], int left, int right) {
- int i, j, s;
- if(left < right) {
- s = number[left];
- i = left;
- j = right + 1;
- while(1) {
- // ¦V¥k§ä
- while(i + 1 < _maxlen && number[++i] < s) ;
- // ¦V¥ª§ä
- while(j -1 > -1 && number[--j] > s) ;
- if(i >= j)
- break;
- swap(&number[i], &number[j]);
- }
- number[left] = number[j];
- number[j] = s;
- quickSort(number, left, j-1);
- quickSort(number, j+1, right);
- }
- }
- int main(){
- int array[_maxlen];
- int copy[_maxlen];
- int a=0,b=0;
- int selection=0;
- int run=1;
- srand(time(NULL));
- clock_t start, finish;
-
- for(a=0;a<_maxlen;a++){
- array[a]=(rand()+1)%100;
- copy[a] = array[a];
- }
-
- for(a=0;a<_maxlen;a++){
- printf("%4d",array[a]);
- if(a%19==18)
- printf("\n");
- }
-
- while( run==1 ){
-
- for(a=0;a<_maxlen;a++)
- copy[a]=array[a];
-
- printf("\n\n(1)Selection sort\n(2)Insertion sort\n(3)Bubble sort\n(4)Quick Sort\n(5)Quit\n");
- printf("\nEnter your choise:");
- scanf("%d",&selection);
-
- switch(selection){
- case 1:
- start = clock();
- selectionSort(copy);
- finish = clock();
- //out(copy);
- printf("\n\n費時:%.3f\n",(double)(finish - start) / CLOCKS_PER_SEC );
- break;
- case 2:
- start = clock();
- insertionSort(copy);
- finish = clock();
- //out(copy);
- printf("\n\n費時:%.3f\n",(double)(finish - start) / CLOCKS_PER_SEC );
- break;
- case 3:
- start = clock();
- bubbleSort(copy);
- finish = clock();
- //out(copy);
- printf("\n\n費時:%.3f\n",(double)(finish - start) / CLOCKS_PER_SEC );
- break;
- case 4:
- start = clock();
- quickSort(copy, 0, _maxlen-1);
- finish = clock();
- //out(copy);
- printf("\n\n費時:%.3f\n",(double)(finish - start) / CLOCKS_PER_SEC );
- break;
- default:
- run=0;
- break;
- }
- }
-
- printf("\n\n");
- return 0;
- }
複製代碼
|
|