請(qǐng)教大家一個(gè)關(guān)于快速排序的問題。

sublx

庫(kù)里面自帶的 qsort為 ：

void qsort(void *base,int nelem,int width,int (*fcmp)(const void *,const void *));

我想問的是，如果對(duì)于內(nèi)建的類型，比如int/char/long/double之類的，能不能不用定義那個(gè)比較函數(shù) ？因?yàn)槟莻�(gè)比較函數(shù)調(diào)用的非常頻繁，這樣效率會(huì)低很多的。我自己寫了一個(gè)qsort比庫(kù)里面那個(gè)非常之多，我覺得應(yīng)該是庫(kù)自帶的那個(gè)qsort每次都調(diào)用fcmp這個(gè)函數(shù)進(jìn)行比較帶來的開銷。
謝謝 。

sublx

怎么一個(gè)人都沒有的 ？？

folklore

這個(gè)不行啊，qsort不知道類型噬。

sublx

回復(fù) 3# folklore


    內(nèi)建的那些類型 直接用 > <號(hào)就行了啊。又不是struct這些 。如果每次都要調(diào)用那個(gè)比較函數(shù) 速度非常慢 。

cokeboL

qsort,你自己直接寫個(gè)不就行了

crazyhadoop

其實(shí)沒慢多少，你就別操心了

sublx

回復(fù) 6# crazyhadoop

慢很、 非常多、慢 N倍。。。剛測(cè)試完。100W的數(shù)據(jù)，T1是我自己寫的，T2是直接掉系統(tǒng)的。1000W相差更大。我寫那個(gè)都沒經(jīng)過優(yōu)化。因?yàn)閝sort起碼有2個(gè)地方是可以優(yōu)化的。

inpput size:1000003
input times:10
t1 = 0.713seconds
t2 = 2.242seconds

t1 = 0.721seconds
t2 = 2.231seconds

t1 = 0.718seconds
t2 = 2.234seconds

t1 = 0.716seconds
t2 = 2.294seconds

t1 = 0.71seconds
t2 = 2.281seconds

請(qǐng)按任意鍵繼續(xù). . .
   

sublx

回復(fù) 5# cokeboL


我是自己寫了。因?yàn)槲矣浀肣sort有2個(gè)地方是可以優(yōu)化的，我想看我寫的沒有優(yōu)化過的 跟系統(tǒng)的有優(yōu)化的 性能差多少，沒想到系統(tǒng)的那個(gè)比我寫的還慢很多...估計(jì)是因?yàn)槊看味颊{(diào)用哪個(gè)cmp函數(shù)的開銷。所以想問下，對(duì)于這種內(nèi)建的類型，完全不需要那個(gè)比較函數(shù)啊 ，能不能不定義。（或者說 不使用）

   

crazyhadoop

回復(fù) 7# sublx


    把你的代碼傳上來看一下撒

sublx

1. int partition(int *array, int low, int high)
   
2. {
   
3.         int prov = array[low];
   
4.         while(low < high)
   
5.         {
   
6.                 while(low < high && array[high] >= prov) high--;
   
7.                 array[low] = array[high];
   
8.                 while(low < high && array[low] <= prov) low++;
   
9.                 array[high] = array[low];
   
10.         }
    
11.         array[low] = prov;
    
12.         return low;
    
13. }
    
14. 
    
15. void qsort(int *array, int low, int high)
    
16. {
    
17.         if (low < high)
    
18.         {
    
19.                 int p = partition(array, low, high);
    
20.                 qsort(array, low, p - 1);
    
21.                 qsort(array, p + 1, high);
    
22.         }
    
23. }
    
24. 
    
25. 
    
26. 
    
27. int num;
    
28.         cout << "inpput size:";
    
29.         cin >> num;
    
30.         int times = 0;
    
31.         cout << "input times:";
    
32.         cin>>times;
    
33.         int *a = new int[num];
    
34.         int *b = new int[num];
    
35. 
    
36.         clock_t m_start;
    
37.         unsigned long t1, t2;
    
38. 
    
39.         srand((unsigned int)time(NULL));
    
40.        
    
41.         int i = 0;
    
42.         while(++i < times)
    
43.         {
    
44.                 for (int i = 0; i < num; ++i)
    
45.                 {
    
46.                         int temp = rand()%10000000;
    
47.                         b[i] = a[i] = temp;
    
48.                 }
    
49.                 m_start = clock();
    
50.                 //MergeSort(a, num);
    
51.                 qsort(a, 0, num - 1);                //
    
52.         //        qsort(a, num, sizeof(int), compare);//
    
53.                 t1 = clock() - m_start;
    
54.                 cout << "t1 = " << (double)(t1)/CLOCKS_PER_SEC << "seconds" <<endl;
    
55.                 m_start = clock();
    
56.                 //HeapSort(b, num);
    
57.                 qsort(b, num, sizeof(int), compare);
    
58.                 t2 = clock() - m_start;
    
59.                 cout << "t2 = " << (double)(t2)/CLOCKS_PER_SEC << "seconds" <<endl;
    
60.                 //show_array(a, num);
    
61.                 //show_array(b, num);
    
62.                 if (!isthesame(a, b, num)) break;
    
63.                 else cout << "two arrays is the same.diff = " << (long)(t2 - t1) << endl;
    
64.                 Sleep(300);
    
65.         }
    
66.         delete [] a;
    
67.         delete [] b

復(fù)制代碼