自己实现的qsort 出现段错误，请大家帮忙看看。

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. 
    

复制代码

lenovo

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

这句会导致数组越界吧？
我不知道这个算法是不是你独创的，
我很难看懂。

fannyth

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

这句会导致数组越界吧？
我不知道这个算法是不是你独创的，
我很难看懂。

这是我根据数据结构上快速排序的伪代码自己实现的。

lenovo

原帖由 fannyth 于 2007-3-12 10:37 发表


这是我根据数据结构上快速排序的伪代码自己实现的。

我给你指出错误了，
结果你说你根据伪码自己实现的，
你还让我怎么说呢？

cugb_cat

楼主还是用gdb调试一下吧，呵呵，数据结构的练习题～～