自己實(shí)現(xiàn)的qsort 出現(xiàn)段錯(cuò)誤，請(qǐng)大家?guī)兔�看看�?/a>

fannyth

1. 
   
2. #include <cstdio>
   
3. 
   
4. void swap(int & a, int &b)
   
5. {
   
6.         int t = a;
   
7.         a = b;
   
8.         b = t;
   
9. }
   
10. 
    
11. void quicksort(int data[], int first, int last)
    
12. {
    
13.         int lower = first+1;
    
14.         int upper = last;
    
15.         swap(data[first], data[(first+last)/2]);
    
16.         int bound = data[first];
    
17.         while(lower <= upper)
    
18.         {
    
19.                 while(data[lower]<bound)
    
20.                         lower--;
    
21.                 while(bound < data[upper])
    
22.                         upper++;
    
23.                 if (lower < upper)
    
24.                         swap(data[lower++], data[upper--]);
    
25.                 else
    
26.                         lower++;
    
27.         }
    
28.         swap(data[upper], data[first]);
    
29.         if (first < upper-1)
    
30.                 quicksort(data, first, upper-1);
    
31.         if (upper+1 < last)
    
32.                 quicksort(data, upper+1, last);
    
33. }
    
34. 
    
35. void quicksort(int data[],int n)
    
36. {
    
37.         if (n < 2)
    
38.                 return;
    
39.         int max_ =0 ;               
    
40.         for (int i=0; i<n; i++)
    
41.         {
    
42.                 if (data[max_]<data[i])
    
43.                         max_ = i;
    
44.         }
    
45.         swap(data[n-1], data[max_]);
    
46.         quicksort(data, 0, n-2);
    
47. }
    
48. 
    
49. int main(int argc, char*argv[])
    
50. {
    
51.         int a[]={4, 6, 1, 7, 3, 0, 5};
    
52.        
    
53.         quicksort(a, 7);
    
54.         return 0;
    
55. }
    
56. 
    

復(fù)制代碼

lenovo

while(bound < data[upper])
       upper++;

這句會(huì)導(dǎo)致數(shù)組越界吧？
我不知道這個(gè)算法是不是你獨(dú)創(chuàng)的，
我很難看懂。

fannyth

原帖由 lenovo 于 2007-3-12 10:30 發(fā)表
while(bound < data[upper])
       upper++;

這句會(huì)導(dǎo)致數(shù)組越界吧？
我不知道這個(gè)算法是不是你獨(dú)創(chuàng)的，
我很難看懂。

這是我根據(jù)數(shù)據(jù)結(jié)構(gòu)上快速排序的偽代碼自己實(shí)現(xiàn)的。

lenovo

原帖由 fannyth 于 2007-3-12 10:37 發(fā)表


這是我根據(jù)數(shù)據(jù)結(jié)構(gòu)上快速排序的偽代碼自己實(shí)現(xiàn)的。

我給你指出錯(cuò)誤了，
結(jié)果你說(shuō)你根據(jù)偽碼自己實(shí)現(xiàn)的，
你還讓我怎么說(shuō)呢？

cugb_cat

樓主還是用gdb調(diào)試一下吧，呵呵，數(shù)據(jù)結(jié)構(gòu)的練習(xí)題～～