1 #include <iostream> 2 #include <cstdio> 3 #include <iomanip> 4 #include <algorithm> 5 #include <map> 6 #include <set> 7 #include <string> 8 #include <vector> 9 #include <ctime> 10 #include <cstdlib> 11 12 using namespace std; 13 14 15 #define MAX 10000000 16 int a[MAX]; 17 18 int cmp(const void *a ,const void *b) 19 { 20 return (*(int*)a) - (*(int*)b); 21 } 22 int b[MAX]; 23 void radixsort(int *a, int n) 24 { 25 int i, m = a[0], exp = 1; 26 for (i = 1; i < n; i++) 27 { 28 if (a[i] > m) 29 m = a[i]; 30 } 31 32 while (m / exp > 0) 33 { 34 int bucket[10] ={ 0 }; 35 for (i = 0; i < n; i++) 36 bucket[(a[i] / exp) % 10]++; 37 for (i = 1; i < 10; i++) 38 bucket[i] += bucket[i - 1]; 39 for (i = n - 1; i >= 0; i--) 40 b[--bucket[(a[i] / exp) % 10]] = a[i]; 41 for (i = 0; i < n; i++) 42 a[i] = b[i]; 43 exp *= 10; 44 } 45 } 46 int main() 47 { 48 int n ; 49 clock_t start,end; 50 freopen("input.txt","r",stdin); 51 scanf("%d",&n); 52 for(int i = 0;i< n;i ++) 53 { 54 scanf("%d",&a[i]); 55 } 56 start=clock(); 57 qsort(a,n,sizeof(int),cmp); 58 //sort(a,a+n); 59 //radixsort(a,n); 60 end=clock(); 61 printf("%d ",end - start); 62 return 0 ; 63 }
这里比较奇怪的是，在数据量大，数据范围小的时候，qsort比sort快！