中央論壇 - CENTER BBS

標題: 內部搜尋法 [打印本頁]

---

作者: f66666602    時間: 2007-8-13 02:15
標題: 內部搜尋法
以下的程式包含四種內部搜尋法：Bubble Sort、Selection Sort、Insertion Sort、Quick Sort

程式開始會先以亂數產生十萬個數字
( #define _mexlen 100000 )
並讓使用者選擇排序使用的搜尋法

另外
因數字過多
排序的結果沒有印出
但是可以自己把 out(copy) 前面的註解拿掉

排序時
程式會自動紀錄系統時間
在排序後顯示花掉的時間
方便大家比較各種排序法的快慢

語言：C 語言
編譯器： DevC++ 4.9.9.2

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <time.h>
   
4. 
   
5. #define _maxlen 100000
   
6. 
   
7. void out(int* in){
   
8.   int a;
   
9.   for(a=0;a<_maxlen;a++){
   
10.     printf("%4d",in[a]);
    
11.     if(a%19==18)
    
12.       printf("\n");
    
13.   }
    
14. }
    
15. 
    
16. void selectionSort(int* in){
    
17.   int a=0,b=0,min=0,tmp=0;;
    
18.   for(a=0;a<_maxlen;a++){
    
19.     for(b=a;b<_maxlen;b++){
    
20.       if(in[b]<in[min])
    
21.         min = b;
    
22.     }
    
23.     tmp = in[a];
    
24.     in[a] = in[min];
    
25.     in[min] = tmp;
    
26.   }
    
27. }
    
28. 
    
29. 
    
30. void insertionSort(int* in)
    
31. {
    
32.   int first=0,last=_maxlen-1;
    
33.   int i,j,a;
    
34.   int temp;
    
35.   for (i = first+1; i<=last;i++){
    
36.   temp = in[i];
    
37.     j=i-1;
    
38.     while((j>=first) && (in[j] > temp)){
    
39.       in[j+1] = in[j];
    
40.       j--;
    
41.     }
    
42.     in[j+1] = temp;     
    
43.   }
    
44. }
    
45. 
    
46. 
    
47. void bubbleSort(int* in){
    
48.   int a=0,b=0,tmp=0;
    
49.   for(a=0;a<_maxlen;a++){
    
50.     for(b=0;b<_maxlen-1;b++){
    
51.       if(in[b]>in[b+1]){
    
52.         tmp = in[b];
    
53.         in[b] = in[b+1];
    
54.         in[b+1] = tmp;
    
55.       }
    
56.     }
    
57.   }
    
58. }
    
59. 
    
60. void swap(int *a, int *b)
    
61. {
    
62. int t=*a; *a=*b; *b=t;
    
63. }
    
64. 
    
65. void quickSort(int number[], int left, int right) {
    
66.   int i, j, s;
    
67. 
    
68.   if(left < right) {
    
69.     s = number[left];
    
70.     i = left;
    
71.     j = right + 1;
    
72. 
    
73.     while(1) {
    
74.         // &brvbar;V&yen;k§&auml;
    
75.         while(i + 1 < _maxlen && number[++i] < s) ;
    
76.         // &brvbar;V&yen;&ordf;§&auml;
    
77.         while(j -1 > -1 && number[--j] > s) ;
    
78.         if(i >= j)
    
79.           break;
    
80.         swap(&number[i], &number[j]);
    
81.     }
    
82. 
    
83.     number[left] = number[j];
    
84.     number[j] = s;
    
85. 
    
86.     quickSort(number, left, j-1);
    
87.     quickSort(number, j+1, right);
    
88.   }
    
89. }
    
90. 
    
91. 
    
92. int main(){
    
93.   int array[_maxlen];
    
94.   int copy[_maxlen];
    
95.   int a=0,b=0;
    
96.   int selection=0;
    
97.   int run=1;
    
98.   srand(time(NULL));
    
99.   clock_t start, finish;
    
100.   
     
101.   for(a=0;a<_maxlen;a++){
     
102.     array[a]=(rand()+1)%100;
     
103.     copy[a] = array[a];
     
104.   }
     
105.   
     
106.   for(a=0;a<_maxlen;a++){
     
107.     printf("%4d",array[a]);
     
108.     if(a%19==18)
     
109.       printf("\n");
     
110.   }
     
111.   
     
112.   while( run==1 ){
     
113.    
     
114.     for(a=0;a<_maxlen;a++)
     
115.       copy[a]=array[a];
     
116.       
     
117.     printf("\n\n(1)Selection sort\n(2)Insertion sort\n(3)Bubble sort\n(4)Quick Sort\n(5)Quit\n");
     
118.     printf("\nEnter your choise:");
     
119.     scanf("%d",&selection);
     
120.   
     
121. 
     
122.     switch(selection){
     
123.       case 1:
     
124.         start = clock();
     
125.         selectionSort(copy);
     
126.         finish = clock();
     
127.         //out(copy);
     
128.         printf("\n\n費時：%.3f\n",(double)(finish - start) / CLOCKS_PER_SEC );
     
129.         break;
     
130.       case 2:
     
131.         start = clock();
     
132.         insertionSort(copy);
     
133.         finish = clock();
     
134.         //out(copy);
     
135.         printf("\n\n費時：%.3f\n",(double)(finish - start) / CLOCKS_PER_SEC );
     
136.         break;
     
137.       case 3:
     
138.         start = clock();
     
139.         bubbleSort(copy);
     
140.         finish = clock();
     
141.         //out(copy);
     
142.         printf("\n\n費時：%.3f\n",(double)(finish - start) / CLOCKS_PER_SEC );
     
143.         break;
     
144.       case 4:
     
145.         start = clock();
     
146.         quickSort(copy, 0, _maxlen-1);
     
147.         finish = clock();
     
148.         //out(copy);
     
149.         printf("\n\n費時：%.3f\n",(double)(finish - start) / CLOCKS_PER_SEC );
     
150.         break;
     
151.       default:
     
152.         run=0;
     
153.         break;
     
154.     }
     
155.   }
     
156.   
     
157.   printf("\n\n");
     
158.   return 0;
     
159. }
     
160. 
     
161. 
     

複製代碼

---

歡迎光臨 中央論壇 - CENTER BBS (https://www.centerbbs.com/)

Powered by Discuz! X3