我想搞清楚的運行時間使用的選擇排序算法來排序的已排序陣列(例如, 1,2,3,4,5,..)以及使用它排序反向數組的時間(例如5,4,3,2 ..)。 我發現的奇怪的事情是,在我的計算機上,排序已排序的數組需要更多的時間,而不是排序反向數組。從我所瞭解的情況來看,我認爲它應該是相反的。爲一個已排序陣列的運行時間由選擇排序算法進行排序Vs的時間爲反轉排序的數組進行排序
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void selectionsort(int A[], int n) {
int min;
for (int i = 0; i < n - 1; i++) {
min = i;
for (int k = i + 1; k < n; k++) {
if (A[k] < A[min]) {
min = k;
}
}
int temp = A[i];
A[i] = A[min];
A[min] = temp;
}
}
void sort(int A[], int n) {
for (int i = 0; i < n; i++) {
A[i] = i + 1;
}
}
void resver_sort(int A[], int n) {
for (int i = 0; i < n; i++) {
A[i] = n - i;
}
}
int main() {
clock_t start, end;
double cpu_time_used;
int A[20000] = { 0 };
int B[40000] = {0};
int C[100000] = {0};
printf("Selection Sort, Sorted Array\n");
sort(A, 20000);
start = clock(); // start the clock
selectionsort(A, 20000);
end = clock(); // stop the clock
cpu_time_used = ((double)(end - start))/CLOCKS_PER_SEC; // calculate the actual time used
printf("array size:20000 time:%f\n", cpu_time_used);
sort(B, 40000);
start = clock();
selectionsort(B, 40000);
end = clock();
cpu_time_used = ((double)(end - start))/CLOCKS_PER_SEC;
printf("array size:40000 time:%f\n", cpu_time_used);
sort(C, 100000);
start = clock();
selectionsort(C, 100000);
end = clock();
cpu_time_used = ((double)(end - start))/CLOCKS_PER_SEC;
printf("array size:100000 time:%f\n", cpu_time_used);
printf("Selection Sort, reverse sorted Array\n");
resver_sort(A, 20000);
start = clock();
selectionsort(A, 20000);
end = clock();
cpu_time_used = ((double)(end - start))/CLOCKS_PER_SEC;
printf("array size:20000 time:%f\n", cpu_time_used);
resver_sort(B, 40000);
start = clock();
selectionsort(B, 40000);
end = clock();
cpu_time_used = ((double)(end - start))/CLOCKS_PER_SEC;
printf("array size:40000 time:%f\n", cpu_time_used);
resver_sort(C, 100000);
start = clock();
selectionsort(C,100000);
end = clock();
cpu_time_used = ((double)(end - start))/CLOCKS_PER_SEC;
printf("array size:100000 time:%f\n", cpu_time_used);
}
結果是
Selection Sort, Sorted Array
array size:20000 time:0.530281
array size:40000 time:2.109836
array size:100000 time:13.197117
Selection Sort, reverse sorted Array
array size:20000 time:0.500338
array size:40000 time:2.016468
array size:100000 time:12.830447
Program ended with exit code: 0
第一個是一個已排序陣列需要更多的時間。這沒有意義。我花了很多時間調試並嘗試打印這些數組以查看它們,但沒有弄明白。
就做幾千次,並獲得* *平均時間。對優化版本也做這種測量。 –
你能否考慮重新加入你的代碼,以便它可以被實際讀取。 –
@Antti Haapala抱歉,我不知道它對你來說是不可讀的。我修改了它。:) –