[已解决]C语言关于调用时间库计算排序时间的问题

hanviry

1. # include <stdio.h>
   
2. # include <stdlib.h>
   
3. # include <time.h>
   
4. 
   
5. #define WIDTH 20
   
6. #define MAXK 10
   
7. 
   
8. int n=0;
   
9. long num;
   
10. int da[2000000];
    
11. int dd[2000000];
    
12. void myhead(){
    
13.         printf("**     排序算法比较      **\n");
    
14.         printf("===========================\n");
    
15.         printf("**     1 ---冒泡排序     **\n");
    
16.         printf("**     2 ---选择排序     **\n");
    
17.         printf("**     3 ---直接插入排序 **\n");
    
18.         printf("**     4 ---希尔排序     **\n");
    
19.         printf("**     5 ---快速排序     **\n");
    
20.         printf("**     6 ---堆排序       **\n");
    
21.         printf("**     7 ---归并排序     **\n");
    
22.         printf("**     8 ---基数排序     **\n");
    
23.         printf("**     9 ---退出程序     **\n");
    
24.         printf("===========================\n");
    
25.         printf("\n");
    
26. }
    
27. 
    
28. void myrand(){
    
29.         int i;
    
30.         srand((unsigned)time(NULL)); /*随机种子*/
    
31.         for(i = 0; i < n; i ++) dd[ i ] = rand();
    
32. }
    
33. 
    
34. void myinit(){
    
35.         int i;
    
36.         for(i = 0; i < n; i ++) da[ i ] = dd[ i ];
    
37.         num=0;
    
38. }
    
39. 
    
40. inline void swap(int *a,int *b){
    
41. int temp;
    
42. temp=*a;
    
43. *a=*b;
    
44. *b=temp;
    
45. num++;
    
46. }
    
47. void mymaopao(){
    
48.         clock_t t1 = clock();
    
49.         int i,j;
    
50.         for(i=0;i<n-1;i++)
    
51.                 for(j=n-1;j>i;j--){
    
52.                         if(da[j]<da[j-1])
    
53.                         swap(&da[j],&da[j-1]);
    
54.                 }
    
55.         clock_t t2 = clock();
    
56.         long sec = (t2-t1) / CLOCKS_PER_SEC;
    
57.         printf("冒泡排序所用时间：        %ld秒\n",sec);
    
58.         printf("冒泡排序所用交换次数：    %ld\n",num);
    
59. }
    
60. 
    
61. void myxuanzhe(){
    
62.         clock_t t1 = clock();
    
63.         int i,j,temp;
    
64.         for(i=0;i<n-1;i++){
    
65.                 temp=i;
    
66.                 for(j=i+1;j<n;j++){
    
67.                         if(da[j]<da[temp]){temp=j;num++;}
    
68.                 }
    
69.                 if(temp!=i)swap(&da[temp],&da[i]);
    
70.         }
    
71.         clock_t t2 = clock();
    
72.         long sec = (t2-t1) / CLOCKS_PER_SEC;
    
73.         printf("选择排序所用时间：        %ld秒\n",sec);
    
74.         printf("选择排序所用交换次数：    %ld\n",num);
    
75. }
    
76. 
    
77. void mycharu(){
    
78.         clock_t t1 = clock();
    
79.         int i,j;
    
80.         int temp=0;
    
81.         for(i = 1; i < n ; i++){
    
82.                 temp = da[i];
    
83.                 for(j = i; j > 0&& temp < da[j - 1]; j--){
    
84.                         if(temp < da[j - 1])
    
85.                                 swap(&da[j],&da[j-1]);
    
86.                 }
    
87.                 da[j] = temp;
    
88.         }       
    
89.         clock_t t2 = clock();
    
90.         long sec = (t2-t1) / CLOCKS_PER_SEC;
    
91.         printf("插入排序所用时间：        %ld秒\n",sec);
    
92.         printf("插入排序所用交换次数：    %ld\n",num);
    
93. }
    
94. 
    
95. void myxier(){
    
96.         clock_t t1 = clock();
    
97.         int i, j, k;
    
98.         int temp, gap;  
    
99.         for (gap = n / 2; gap > 0; gap /= 2){
    
100.                 for (i = 0; i < gap; i++){
     
101.                         for (j = i + gap; j < n; j += gap)
     
102.                                 if (da[j] < da[j - gap]){
     
103.                                         temp = da[j];  
     
104.                                         k = j - gap;
     
105.                                         while (k >= 0 && da[k] > temp){
     
106.                                                 da[k + gap] = da[k];
     
107.                                                 k -= gap;
     
108.                                         }
     
109.                                         da[k + gap] = temp;
     
110.                                         num++;
     
111.                                 }
     
112.                 }
     
113.         }
     
114.         clock_t t2 = clock();
     
115.         long sec = (t2-t1) / CLOCKS_PER_SEC;
     
116.         printf("希尔排序所用时间：        %ld秒\n",sec);
     
117.         printf("希尔排序所用交换次数：    %ld\n",num);
     
118. }
     
119. 
     
120. void myqsort(int l,int r) {
     
121.         int i, j, x;
     
122.         if (l < r){
     
123.                 i = l;
     
124.                 j = r;
     
125.                 x = da[i];
     
126.                 while (i < j){
     
127.                         while(i < j && da[j] > x) j--;
     
128.                         if(i < j) da[i++] = da[j];
     
129.                         while(i < j && da[i] < x) i++;
     
130.                         if(i < j) da[j--] = da[i];
     
131.                 }
     
132.                 da[i] = x;
     
133.                 num++;
     
134.                 myqsort(l, i-1);
     
135.                 myqsort(i+1, r);
     
136.         }
     
137. }
     
138. void mykuaisu(){
     
139.         clock_t t1 = clock();
     
140.         myqsort(0,n);       
     
141.         clock_t t2 = clock();
     
142.         long sec = (t2-t1) / CLOCKS_PER_SEC;
     
143.         printf("希尔排序所用时间：        %ld秒\n",sec);
     
144.         printf("希尔排序所用交换次数：    %ld\n",num);
     
145. }
     
146. void HeapAdjust(int i, int nLength){
     
147.         int nChild, nTemp;
     
148.         for (nTemp = da[i]; 2 * i + 1 < nLength; i = nChild){
     
149.                 nChild = 2 * i + 1;
     
150.                 if (nChild != nLength - 1 && da[nChild + 1] > da[nChild])
     
151.                     ++nChild;
     
152.                 if (nTemp < da[nChild]){
     
153.                         da[i] = da[nChild];
     
154.                         num++;
     
155.                 }else{
     
156.                         break;
     
157.                 }
     
158.         }
     
159.         da[i] = nTemp;
     
160. }
     
161. void mydui(){
     
162.         clock_t t1 = clock();
     
163.         int i;
     
164.         for (i = n / 2 - 1; i >= 0; --i){
     
165.                 HeapAdjust(i, n);
     
166.         }
     
167.         for (i = n - 1; i > 0; --i){
     
168.                 swap(&da[0], &da[i]);
     
169.         HeapAdjust(0, i);
     
170.         }
     
171.         clock_t t2 = clock();
     
172.         long sec = (t2-t1) / CLOCKS_PER_SEC;
     
173.         printf("堆排序所用时间：        %ld秒\n",sec);
     
174.         printf("堆排序所用交换次数：    %ld\n",num);
     
175. }
     
176. void Merge(int left, int m, int right){
     
177.         int aux[200000] = {0};
     
178.             int i;
     
179.             int j;
     
180.             int k;
     
181.    
     
182.             for (i = left, j = m+1, k = 0; k <= right-left; k++){
     
183.                 num++;
     
184.                 if (i == m+1){
     
185.                             aux[k] = da[j++];
     
186.                            continue;
     
187.                 }
     
188.                 if (j == right+1){
     
189.                             aux[k] = da[i++];
     
190.                             continue;
     
191.                 }
     
192.                 if (da[i] < da[j]){
     
193.                             aux[k] = da[i++];
     
194.                 }else{
     
195.                             aux[k] = da[j++];
     
196.                 }
     
197.             }
     
198.         for (i = left, j = 0; i <= right; i++, j++){
     
199.                 da[i] = aux[j];
     
200.         }
     
201. }
     
202. void MergeSort(int start,int end){
     
203.         if (start < end){
     
204.                 int i;
     
205.                 i = (end + start) / 2;
     
206.                 MergeSort(start, i);
     
207.                 MergeSort(i + 1, end);
     
208.                 Merge(start, i, end);
     
209.     }
     
210. }
     
211. void myguibing(){
     
212.         clock_t t1 = clock();
     
213.         MergeSort(0,n-1);
     
214.         clock_t t2 = clock();
     
215.         long sec = (t2-t1) / CLOCKS_PER_SEC;
     
216.         printf("归并排序所用时间：        %ld秒\n",sec);
     
217.         printf("归并排序所用交换次数：    %ld\n",num);
     
218. }
     
219. int getDValue(int value, int d) {
     
220.         for (;d > 0 && value > 0; d--) {
     
221.                 value = value / MAXK;
     
222.         }
     
223.         return value % MAXK;
     
224. }
     
225. void myjishu(){
     
226.         clock_t t1 = clock();
     
227.         int i;
     
228.         void innerCountingSort(int d);
     
229.         for (i = 0; i < WIDTH; i++) {
     
230.                 innerCountingSort(i);
     
231.         }
     
232.         clock_t t2 = clock();
     
233.         long sec = (t2-t1) / CLOCKS_PER_SEC;
     
234.         printf("基数排序所用时间：        %ld秒\n",sec);
     
235.         printf("基数排序所用交换次数：    %ld\n",num);
     
236. }
     
237. 
     
238. void innerCountingSort(int d) {
     
239.         int i, j, x, k[MAXK] = {0};
     
240.         int *ip = (int *)malloc(n * sizeof(int));
     
241.         int *bp = (int *)malloc(n * sizeof(int));
     
242.         int getDValue(int value, int d);
     
243.         for (i = 0; i < n; i++) {
     
244.                 ip[i] = getDValue(da[i], d);
     
245.                 k[ip[i]]++;
     
246.         }
     
247. 
     
248.         for (j = 1; j < MAXK; j++) {
     
249.                 k[j] = k[j] + k[j-1];
     
250.         }
     
251. 
     
252.         for (i = n - 1; i >= 0; i--) {
     
253.                 bp[k[ip[i]] - 1] = da[i];
     
254.                 k[ip[i]]--;
     
255.         }
     
256. 
     
257.         for (i = 0; i < n; i++) {
     
258.                 da[i] = bp[i];
     
259.         }
     
260. 
     
261.         free(ip);
     
262.         free(bp);
     
263. }
     
264. 
     
265. 
     
266. int main()
     
267. {
     
268.         myhead();
     
269.         printf("请输入要产生的随机数的个数（不超过10000）：");
     
270.         scanf("%d",&n);
     
271.         myrand(n);
     
272.         printf("\n");
     
273.         int flag = 1;
     
274.         while (flag){       
     
275.                 myinit();       
     
276.                 printf("\n");       
     
277.                 printf("请选择排序算法：");
     
278.                 int ch;
     
279.                 scanf("%d", &ch);
     
280.                 switch(ch){
     
281.                         case 1 : mymaopao(); break;
     
282.                         case 2 : myxuanzhe(); break;
     
283.                         case 3 : mycharu(); break;
     
284.                         case 4 : myxier(); break;
     
285.                         case 5 : mykuaisu(); break;
     
286.                         case 6 : mydui(); break;
     
287.                         case 7 : myguibing(); break;
     
288.                         case 8 : myjishu(); break;
     
289.                         case 9 : flag = 0;       
     
290.                 }
     
291.         }
     
292.         return 0;
     
293. }

复制代码

有一个问题就是，每个排序算法算出来的时间都是0，不知道哪里出错了，
希望有大神能够帮忙看看，感谢！

最佳答案

月排行榜 / 总排行榜

sunrise085

2019-12-25 17:37:10

刚刚看了一下你的程序。先说你提出的问题。问题应该是出在这句程序上了
long sec = (t2-t1) / CLOCKS_PER_SEC;
这里是因为t1和t2差距太小，排序时间不足一秒，整数除法结果当然是零啦。应该把sec改为float，最好是double，另外(t2-t1) 进行强制类型转换。double sec = (double)(t2-t1) / CLOCKS_PER_SEC;
修改之后，printf中也应该修改。

此外你的程序还有一个错误。第二个函数myrand(),在定义的时候没有参数，调用的时候有个参数int。

1. # include <stdio.h>
   
2. # include <stdlib.h>
   
3. # include <time.h>
   
4. 
   
5. #define WIDTH 20
   
6. #define MAXK 10
   
7. 
   
8. int n=0;
   
9. long num;
   
10. int da[2000000];
    
11. int dd[2000000];
    
12. void myhead(){
    
13.         printf("**     排序算法比较      **\n");
    
14.         printf("===========================\n");
    
15.         printf("**     1 ---冒泡排序     **\n");
    
16.         printf("**     2 ---选择排序     **\n");
    
17.         printf("**     3 ---直接插入排序 **\n");
    
18.         printf("**     4 ---希尔排序     **\n");
    
19.         printf("**     5 ---快速排序     **\n");
    
20.         printf("**     6 ---堆排序       **\n");
    
21.         printf("**     7 ---归并排序     **\n");
    
22.         printf("**     8 ---基数排序     **\n");
    
23.         printf("**     9 ---退出程序     **\n");
    
24.         printf("===========================\n");
    
25.         printf("\n");
    
26. }
    
27. 
    
28. void myrand(int i){
    
29.         //int i;
    
30.         srand((unsigned)time(NULL)); /*随机种子*/
    
31.         for(i = 0; i < n; i ++) dd[ i ] = rand();
    
32. }
    
33. 
    
34. void myinit(){
    
35.         int i;
    
36.         for(i = 0; i < n; i ++) da[ i ] = dd[ i ];
    
37.         num=0;
    
38. }
    
39. 
    
40. inline void swap(int *a,int *b){
    
41. int temp;
    
42. temp=*a;
    
43. *a=*b;
    
44. *b=temp;
    
45. num++;
    
46. }
    
47. void mymaopao(){
    
48.         clock_t t1 = clock();
    
49.         int i,j;
    
50.         for(i=0;i<n-1;i++)
    
51.                 for(j=n-1;j>i;j--){
    
52.                         if(da[j]<da[j-1])
    
53.                         swap(&da[j],&da[j-1]);
    
54.                 }
    
55.         clock_t t2 = clock();
    
56.         double sec = (double)(t2-t1) / CLOCKS_PER_SEC;
    
57.         printf("冒泡排序所用时间：        %f秒\n",sec);
    
58.         printf("冒泡排序所用交换次数：    %ld\n",num);
    
59. }
    
60. 
    
61. void myxuanzhe(){
    
62.         clock_t t1 = clock();
    
63.         int i,j,temp;
    
64.         for(i=0;i<n-1;i++){
    
65.                 temp=i;
    
66.                 for(j=i+1;j<n;j++){
    
67.                         if(da[j]<da[temp]){temp=j;num++;}
    
68.                 }
    
69.                 if(temp!=i)swap(&da[temp],&da[i]);
    
70.         }
    
71.         clock_t t2 = clock();
    
72.         double sec = (double)(t2-t1) / CLOCKS_PER_SEC;
    
73.         printf("选择排序所用时间：        %f秒\n",sec);
    
74.         printf("选择排序所用交换次数：    %ld\n",num);
    
75. }
    
76. 
    
77. void mycharu(){
    
78.         clock_t t1 = clock();
    
79.         int i,j;
    
80.         int temp=0;
    
81.         for(i = 1; i < n ; i++){
    
82.                 temp = da[i];
    
83.                 for(j = i; j > 0&& temp < da[j - 1]; j--){
    
84.                         if(temp < da[j - 1])
    
85.                                 swap(&da[j],&da[j-1]);
    
86.                 }
    
87.                 da[j] = temp;
    
88.         }        
    
89.         clock_t t2 = clock();
    
90.         double sec = (double)(t2-t1) / CLOCKS_PER_SEC;
    
91.         printf("插入排序所用时间：        %f秒\n",sec);
    
92.         printf("插入排序所用交换次数：    %ld\n",num);
    
93. }
    
94. 
    
95. void myxier(){
    
96.         clock_t t1 = clock();
    
97.         int i, j, k;
    
98.         int temp, gap;  
    
99.         for (gap = n / 2; gap > 0; gap /= 2){
    
100.                 for (i = 0; i < gap; i++){
     
101.                         for (j = i + gap; j < n; j += gap)
     
102.                                 if (da[j] < da[j - gap]){
     
103.                                         temp = da[j];  
     
104.                                         k = j - gap;
     
105.                                         while (k >= 0 && da[k] > temp){
     
106.                                                 da[k + gap] = da[k];
     
107.                                                 k -= gap;
     
108.                                         }
     
109.                                         da[k + gap] = temp;
     
110.                                         num++;
     
111.                                 }
     
112.                 }
     
113.         }
     
114.         clock_t t2 = clock();
     
115.         double sec = (double)(t2-t1) / CLOCKS_PER_SEC;
     
116.         printf("希尔排序所用时间：        %f秒\n",sec);
     
117.         printf("希尔排序所用交换次数：    %ld\n",num);
     
118. }
     
119. 
     
120. void myqsort(int l,int r) {
     
121.         int i, j, x;
     
122.         if (l < r){
     
123.                 i = l;
     
124.                 j = r;
     
125.                 x = da[i];
     
126.                 while (i < j){
     
127.                         while(i < j && da[j] > x) j--;
     
128.                         if(i < j) da[i++] = da[j];
     
129.                         while(i < j && da[i] < x) i++;
     
130.                         if(i < j) da[j--] = da[i];
     
131.                 }
     
132.                 da[i] = x;
     
133.                 num++;
     
134.                 myqsort(l, i-1);
     
135.                 myqsort(i+1, r);
     
136.         }
     
137. }
     
138. void mykuaisu(){
     
139.         clock_t t1 = clock();
     
140.         myqsort(0,n);        
     
141.         clock_t t2 = clock();
     
142.         double sec = (double)(t2-t1) / CLOCKS_PER_SEC;
     
143.         printf("希尔排序所用时间：        %f秒\n",sec);
     
144.         printf("希尔排序所用交换次数：    %ld\n",num);
     
145. }
     
146. void HeapAdjust(int i, int nLength){
     
147.         int nChild, nTemp;
     
148.         for (nTemp = da[i]; 2 * i + 1 < nLength; i = nChild){
     
149.                 nChild = 2 * i + 1;
     
150.                 if (nChild != nLength - 1 && da[nChild + 1] > da[nChild])
     
151.                     ++nChild;
     
152.                 if (nTemp < da[nChild]){
     
153.                         da[i] = da[nChild];
     
154.                         num++;
     
155.                 }else{
     
156.                         break;
     
157.                 }
     
158.         }
     
159.         da[i] = nTemp;
     
160. }
     
161. void mydui(){
     
162.         clock_t t1 = clock();
     
163.         int i;
     
164.         for (i = n / 2 - 1; i >= 0; --i){
     
165.                 HeapAdjust(i, n);
     
166.         }
     
167.         for (i = n - 1; i > 0; --i){
     
168.                 swap(&da[0], &da[i]);
     
169.         HeapAdjust(0, i);
     
170.         }
     
171.         clock_t t2 = clock();
     
172.         double sec = (double)(t2-t1) / CLOCKS_PER_SEC;
     
173.         printf("堆排序所用时间：        %f秒\n",sec);
     
174.         printf("堆排序所用交换次数：    %ld\n",num);
     
175. }
     
176. void Merge(int left, int m, int right){
     
177.         int aux[200000] = {0};
     
178.             int i;
     
179.             int j;
     
180.             int k;
     
181.    
     
182.             for (i = left, j = m+1, k = 0; k <= right-left; k++){
     
183.                 num++;
     
184.                 if (i == m+1){
     
185.                             aux[k] = da[j++];
     
186.                            continue;
     
187.                 }
     
188.                 if (j == right+1){
     
189.                             aux[k] = da[i++];
     
190.                             continue;
     
191.                 }
     
192.                 if (da[i] < da[j]){
     
193.                             aux[k] = da[i++];
     
194.                 }else{
     
195.                             aux[k] = da[j++];
     
196.                 }
     
197.             }
     
198.         for (i = left, j = 0; i <= right; i++, j++){
     
199.                 da[i] = aux[j];
     
200.         }
     
201. }
     
202. void MergeSort(int start,int end){
     
203.         if (start < end){
     
204.                 int i;
     
205.                 i = (end + start) / 2;
     
206.                 MergeSort(start, i);
     
207.                 MergeSort(i + 1, end);
     
208.                 Merge(start, i, end);
     
209.     }
     
210. }
     
211. void myguibing(){
     
212.         clock_t t1 = clock();
     
213.         MergeSort(0,n-1);
     
214.         clock_t t2 = clock();
     
215.         double sec = (double)(t2-t1) / CLOCKS_PER_SEC;
     
216.         printf("归并排序所用时间：        %f秒\n",sec);
     
217.         printf("归并排序所用交换次数：    %ld\n",num);
     
218. }
     
219. int getDValue(int value, int d) {
     
220.         for (;d > 0 && value > 0; d--) {
     
221.                 value = value / MAXK;
     
222.         }
     
223.         return value % MAXK;
     
224. }
     
225. void myjishu(){
     
226.         clock_t t1 = clock();
     
227.         int i;
     
228.         void innerCountingSort(int d);
     
229.         for (i = 0; i < WIDTH; i++) {
     
230.                 innerCountingSort(i);
     
231.         }
     
232.         clock_t t2 = clock();
     
233.         double sec = (double)(t2-t1) / CLOCKS_PER_SEC;
     
234.         printf("基数排序所用时间：        %f秒\n",sec);
     
235.         printf("基数排序所用交换次数：    %ld\n",num);
     
236. }
     
237. 
     
238. void innerCountingSort(int d) {
     
239.         int i, j, x, k[MAXK] = {0};
     
240.         int *ip = (int *)malloc(n * sizeof(int));
     
241.         int *bp = (int *)malloc(n * sizeof(int));
     
242.         int getDValue(int value, int d);
     
243.         for (i = 0; i < n; i++) {
     
244.                 ip[i] = getDValue(da[i], d);
     
245.                 k[ip[i]]++;
     
246.         }
     
247. 
     
248.         for (j = 1; j < MAXK; j++) {
     
249.                 k[j] = k[j] + k[j-1];
     
250.         }
     
251. 
     
252.         for (i = n - 1; i >= 0; i--) {
     
253.                 bp[k[ip[i]] - 1] = da[i];
     
254.                 k[ip[i]]--;
     
255.         }
     
256. 
     
257.         for (i = 0; i < n; i++) {
     
258.                 da[i] = bp[i];
     
259.         }
     
260. 
     
261.         free(ip);
     
262.         free(bp);
     
263. }
     
264. 
     
265. 
     
266. int main()
     
267. {
     
268.         myhead();
     
269.         printf("请输入要产生的随机数的个数（不超过10000）：");
     
270.         scanf("%d",&n);
     
271.         myrand(n);
     
272.         printf("\n");
     
273.         int flag = 1;
     
274.         while (flag){        
     
275.                 myinit();        
     
276.                 printf("\n");        
     
277.                 printf("请选择排序算法：");
     
278.                 int ch;
     
279.                 scanf("%d", &ch);
     
280.                 switch(ch){
     
281.                         case 1 : mymaopao(); break;
     
282.                         case 2 : myxuanzhe(); break;
     
283.                         case 3 : mycharu(); break;
     
284.                         case 4 : myxier(); break;
     
285.                         case 5 : mykuaisu(); break;
     
286.                         case 6 : mydui(); break;
     
287.                         case 7 : myguibing(); break;
     
288.                         case 8 : myjishu(); break;
     
289.                         case 9 : flag = 0;        
     
290.                 }
     
291.         }
     
292.         return 0;
     
293. }

复制代码

跳转到最佳答案楼层

sunrise085

刚刚看了一下你的程序。先说你提出的问题。问题应该是出在这句程序上了
long sec = (t2-t1) / CLOCKS_PER_SEC;
这里是因为t1和t2差距太小，排序时间不足一秒，整数除法结果当然是零啦。应该把sec改为float，最好是double，另外(t2-t1) 进行强制类型转换。double sec = (double)(t2-t1) / CLOCKS_PER_SEC;
修改之后，printf中也应该修改。

此外你的程序还有一个错误。第二个函数myrand(),在定义的时候没有参数，调用的时候有个参数int。

1. # include <stdio.h>
   
2. # include <stdlib.h>
   
3. # include <time.h>
   
4. 
   
5. #define WIDTH 20
   
6. #define MAXK 10
   
7. 
   
8. int n=0;
   
9. long num;
   
10. int da[2000000];
    
11. int dd[2000000];
    
12. void myhead(){
    
13.         printf("**     排序算法比较      **\n");
    
14.         printf("===========================\n");
    
15.         printf("**     1 ---冒泡排序     **\n");
    
16.         printf("**     2 ---选择排序     **\n");
    
17.         printf("**     3 ---直接插入排序 **\n");
    
18.         printf("**     4 ---希尔排序     **\n");
    
19.         printf("**     5 ---快速排序     **\n");
    
20.         printf("**     6 ---堆排序       **\n");
    
21.         printf("**     7 ---归并排序     **\n");
    
22.         printf("**     8 ---基数排序     **\n");
    
23.         printf("**     9 ---退出程序     **\n");
    
24.         printf("===========================\n");
    
25.         printf("\n");
    
26. }
    
27. 
    
28. void myrand(int i){
    
29.         //int i;
    
30.         srand((unsigned)time(NULL)); /*随机种子*/
    
31.         for(i = 0; i < n; i ++) dd[ i ] = rand();
    
32. }
    
33. 
    
34. void myinit(){
    
35.         int i;
    
36.         for(i = 0; i < n; i ++) da[ i ] = dd[ i ];
    
37.         num=0;
    
38. }
    
39. 
    
40. inline void swap(int *a,int *b){
    
41. int temp;
    
42. temp=*a;
    
43. *a=*b;
    
44. *b=temp;
    
45. num++;
    
46. }
    
47. void mymaopao(){
    
48.         clock_t t1 = clock();
    
49.         int i,j;
    
50.         for(i=0;i<n-1;i++)
    
51.                 for(j=n-1;j>i;j--){
    
52.                         if(da[j]<da[j-1])
    
53.                         swap(&da[j],&da[j-1]);
    
54.                 }
    
55.         clock_t t2 = clock();
    
56.         double sec = (double)(t2-t1) / CLOCKS_PER_SEC;
    
57.         printf("冒泡排序所用时间：        %f秒\n",sec);
    
58.         printf("冒泡排序所用交换次数：    %ld\n",num);
    
59. }
    
60. 
    
61. void myxuanzhe(){
    
62.         clock_t t1 = clock();
    
63.         int i,j,temp;
    
64.         for(i=0;i<n-1;i++){
    
65.                 temp=i;
    
66.                 for(j=i+1;j<n;j++){
    
67.                         if(da[j]<da[temp]){temp=j;num++;}
    
68.                 }
    
69.                 if(temp!=i)swap(&da[temp],&da[i]);
    
70.         }
    
71.         clock_t t2 = clock();
    
72.         double sec = (double)(t2-t1) / CLOCKS_PER_SEC;
    
73.         printf("选择排序所用时间：        %f秒\n",sec);
    
74.         printf("选择排序所用交换次数：    %ld\n",num);
    
75. }
    
76. 
    
77. void mycharu(){
    
78.         clock_t t1 = clock();
    
79.         int i,j;
    
80.         int temp=0;
    
81.         for(i = 1; i < n ; i++){
    
82.                 temp = da[i];
    
83.                 for(j = i; j > 0&& temp < da[j - 1]; j--){
    
84.                         if(temp < da[j - 1])
    
85.                                 swap(&da[j],&da[j-1]);
    
86.                 }
    
87.                 da[j] = temp;
    
88.         }        
    
89.         clock_t t2 = clock();
    
90.         double sec = (double)(t2-t1) / CLOCKS_PER_SEC;
    
91.         printf("插入排序所用时间：        %f秒\n",sec);
    
92.         printf("插入排序所用交换次数：    %ld\n",num);
    
93. }
    
94. 
    
95. void myxier(){
    
96.         clock_t t1 = clock();
    
97.         int i, j, k;
    
98.         int temp, gap;  
    
99.         for (gap = n / 2; gap > 0; gap /= 2){
    
100.                 for (i = 0; i < gap; i++){
     
101.                         for (j = i + gap; j < n; j += gap)
     
102.                                 if (da[j] < da[j - gap]){
     
103.                                         temp = da[j];  
     
104.                                         k = j - gap;
     
105.                                         while (k >= 0 && da[k] > temp){
     
106.                                                 da[k + gap] = da[k];
     
107.                                                 k -= gap;
     
108.                                         }
     
109.                                         da[k + gap] = temp;
     
110.                                         num++;
     
111.                                 }
     
112.                 }
     
113.         }
     
114.         clock_t t2 = clock();
     
115.         double sec = (double)(t2-t1) / CLOCKS_PER_SEC;
     
116.         printf("希尔排序所用时间：        %f秒\n",sec);
     
117.         printf("希尔排序所用交换次数：    %ld\n",num);
     
118. }
     
119. 
     
120. void myqsort(int l,int r) {
     
121.         int i, j, x;
     
122.         if (l < r){
     
123.                 i = l;
     
124.                 j = r;
     
125.                 x = da[i];
     
126.                 while (i < j){
     
127.                         while(i < j && da[j] > x) j--;
     
128.                         if(i < j) da[i++] = da[j];
     
129.                         while(i < j && da[i] < x) i++;
     
130.                         if(i < j) da[j--] = da[i];
     
131.                 }
     
132.                 da[i] = x;
     
133.                 num++;
     
134.                 myqsort(l, i-1);
     
135.                 myqsort(i+1, r);
     
136.         }
     
137. }
     
138. void mykuaisu(){
     
139.         clock_t t1 = clock();
     
140.         myqsort(0,n);        
     
141.         clock_t t2 = clock();
     
142.         double sec = (double)(t2-t1) / CLOCKS_PER_SEC;
     
143.         printf("希尔排序所用时间：        %f秒\n",sec);
     
144.         printf("希尔排序所用交换次数：    %ld\n",num);
     
145. }
     
146. void HeapAdjust(int i, int nLength){
     
147.         int nChild, nTemp;
     
148.         for (nTemp = da[i]; 2 * i + 1 < nLength; i = nChild){
     
149.                 nChild = 2 * i + 1;
     
150.                 if (nChild != nLength - 1 && da[nChild + 1] > da[nChild])
     
151.                     ++nChild;
     
152.                 if (nTemp < da[nChild]){
     
153.                         da[i] = da[nChild];
     
154.                         num++;
     
155.                 }else{
     
156.                         break;
     
157.                 }
     
158.         }
     
159.         da[i] = nTemp;
     
160. }
     
161. void mydui(){
     
162.         clock_t t1 = clock();
     
163.         int i;
     
164.         for (i = n / 2 - 1; i >= 0; --i){
     
165.                 HeapAdjust(i, n);
     
166.         }
     
167.         for (i = n - 1; i > 0; --i){
     
168.                 swap(&da[0], &da[i]);
     
169.         HeapAdjust(0, i);
     
170.         }
     
171.         clock_t t2 = clock();
     
172.         double sec = (double)(t2-t1) / CLOCKS_PER_SEC;
     
173.         printf("堆排序所用时间：        %f秒\n",sec);
     
174.         printf("堆排序所用交换次数：    %ld\n",num);
     
175. }
     
176. void Merge(int left, int m, int right){
     
177.         int aux[200000] = {0};
     
178.             int i;
     
179.             int j;
     
180.             int k;
     
181.    
     
182.             for (i = left, j = m+1, k = 0; k <= right-left; k++){
     
183.                 num++;
     
184.                 if (i == m+1){
     
185.                             aux[k] = da[j++];
     
186.                            continue;
     
187.                 }
     
188.                 if (j == right+1){
     
189.                             aux[k] = da[i++];
     
190.                             continue;
     
191.                 }
     
192.                 if (da[i] < da[j]){
     
193.                             aux[k] = da[i++];
     
194.                 }else{
     
195.                             aux[k] = da[j++];
     
196.                 }
     
197.             }
     
198.         for (i = left, j = 0; i <= right; i++, j++){
     
199.                 da[i] = aux[j];
     
200.         }
     
201. }
     
202. void MergeSort(int start,int end){
     
203.         if (start < end){
     
204.                 int i;
     
205.                 i = (end + start) / 2;
     
206.                 MergeSort(start, i);
     
207.                 MergeSort(i + 1, end);
     
208.                 Merge(start, i, end);
     
209.     }
     
210. }
     
211. void myguibing(){
     
212.         clock_t t1 = clock();
     
213.         MergeSort(0,n-1);
     
214.         clock_t t2 = clock();
     
215.         double sec = (double)(t2-t1) / CLOCKS_PER_SEC;
     
216.         printf("归并排序所用时间：        %f秒\n",sec);
     
217.         printf("归并排序所用交换次数：    %ld\n",num);
     
218. }
     
219. int getDValue(int value, int d) {
     
220.         for (;d > 0 && value > 0; d--) {
     
221.                 value = value / MAXK;
     
222.         }
     
223.         return value % MAXK;
     
224. }
     
225. void myjishu(){
     
226.         clock_t t1 = clock();
     
227.         int i;
     
228.         void innerCountingSort(int d);
     
229.         for (i = 0; i < WIDTH; i++) {
     
230.                 innerCountingSort(i);
     
231.         }
     
232.         clock_t t2 = clock();
     
233.         double sec = (double)(t2-t1) / CLOCKS_PER_SEC;
     
234.         printf("基数排序所用时间：        %f秒\n",sec);
     
235.         printf("基数排序所用交换次数：    %ld\n",num);
     
236. }
     
237. 
     
238. void innerCountingSort(int d) {
     
239.         int i, j, x, k[MAXK] = {0};
     
240.         int *ip = (int *)malloc(n * sizeof(int));
     
241.         int *bp = (int *)malloc(n * sizeof(int));
     
242.         int getDValue(int value, int d);
     
243.         for (i = 0; i < n; i++) {
     
244.                 ip[i] = getDValue(da[i], d);
     
245.                 k[ip[i]]++;
     
246.         }
     
247. 
     
248.         for (j = 1; j < MAXK; j++) {
     
249.                 k[j] = k[j] + k[j-1];
     
250.         }
     
251. 
     
252.         for (i = n - 1; i >= 0; i--) {
     
253.                 bp[k[ip[i]] - 1] = da[i];
     
254.                 k[ip[i]]--;
     
255.         }
     
256. 
     
257.         for (i = 0; i < n; i++) {
     
258.                 da[i] = bp[i];
     
259.         }
     
260. 
     
261.         free(ip);
     
262.         free(bp);
     
263. }
     
264. 
     
265. 
     
266. int main()
     
267. {
     
268.         myhead();
     
269.         printf("请输入要产生的随机数的个数（不超过10000）：");
     
270.         scanf("%d",&n);
     
271.         myrand(n);
     
272.         printf("\n");
     
273.         int flag = 1;
     
274.         while (flag){        
     
275.                 myinit();        
     
276.                 printf("\n");        
     
277.                 printf("请选择排序算法：");
     
278.                 int ch;
     
279.                 scanf("%d", &ch);
     
280.                 switch(ch){
     
281.                         case 1 : mymaopao(); break;
     
282.                         case 2 : myxuanzhe(); break;
     
283.                         case 3 : mycharu(); break;
     
284.                         case 4 : myxier(); break;
     
285.                         case 5 : mykuaisu(); break;
     
286.                         case 6 : mydui(); break;
     
287.                         case 7 : myguibing(); break;
     
288.                         case 8 : myjishu(); break;
     
289.                         case 9 : flag = 0;        
     
290.                 }
     
291.         }
     
292.         return 0;
     
293. }

复制代码

Croper

不要以秒做单位，你的电脑没有那么烂，一个不到10000长度的排序算法用不了1秒的，
用毫秒做单位

hanviry

sunrise085 发表于 2019-12-25 17:37
刚刚看了一下你的程序。先说你提出的问题。问题应该是出在这句程序上了
long sec = (t2-t1) / CLOCKS_PER_ ...

嗯好的！明白啦，谢谢！

hanviry

Croper 发表于 2019-12-25 17:43
不要以秒做单位，你的电脑没有那么烂，一个不到10000长度的排序算法用不了1秒的，
用毫秒做单位

嗯嗯，明白了，谢谢啦