【help】c++實現快排出現錯誤，help排出現錯誤

【help】c++實現快排出現錯誤，help排出現錯誤

 1 #include"header_file.h"
 2 using namespace std;
 3 
 4 void swap(int a,int b)
 5 {
 6     int t;
 7     t=a;
 8     a=b;
 9     b=t;
10 }
11 
12 void quick_sort(int a[7],int low,int high)
13 {
14     
15     int mid;
16     int x;
17     mid=(low+high)/2;
18     x=a[x];
19     
20     while(low<high)
21     {
22         while(a[low]<x)
23             low++;
24         while(a[high]>x)
25             high--;
26         swap(a[low],a[high]);
27     }
28     quick_sort(a,0,low);
29     quick_sort(a,low+1,6);
30 }
31 
32 int main(void)
33 {
34     int a[7]={4,3,6,7,2,1,5};
35     quick_sort(a,0,6);
36     
37     for(int i=0;i<7;i++)
38         cout<<a[i]<<" ";
39 }

運行出現c4717錯誤，看msdn解釋如下：

“function”: 遞歸所有控件路徑，函數將導致運行時堆棧溢出

每個涉及函數的路徑都包含對該函數的調用。因為無法在沒有首次遞歸調用函數本身的情況下退出該函數，所以函數將永遠不退出。

下面的示例生成 C4717：

 1 // C4717.cpp
 2 // compile with: /W1 /c
 3 // C4717 expected
 4 int func(int x) {
 5    if (x > 1)
 6       return func(x - 1); // recursive call
 7    else {
 8       int y = func(0) + 1; // recursive call
 9       return y;
10    }
11 }
12 
13 int main(){
14    func(1);
15 }

可以看出來是重復調用func（0），而這個func(0)並沒有一個返回值，所以會導致永遠卡在這裡，永不退出。

回過頭看我們的函數： 當low=high的時候根本沒有返回，就會一直調用，產生同樣的錯誤，在前邊排序函數中加入

1 if(low>=high)
2     return;

就不會報錯了，不過還是會產生棧溢出的問題。

stackoverflow上的一個一樣的問題：http://stackoverflow.com/questions/8770081/segfault-with-a-quicksort-implementation-in-c/8770117#8770117

看了之後改成了：

 1 void quick_sort(int a[], int low, int high)
 2 {
 3 
 4     if (low >= high)
 5         return ;
 6     
 7     int first;
 8     int last;
 9     first = low;
10     last = high;
11 
12     int mid;
13     int x;
14     mid = (first + last) / 2;
15     x = a[mid];
16 
17     first++;
18     while (first<last)
19     {
20         while ((first <= last) && (a[first] <= x)  )
21             first++;
22     //    a[first] = a[last];
23         while ((first <= last) && (a[last] >= x)  )
24             last--;
25         swap(a[last], a[first]);
26     }
27 
28     quick_sort(a, low, first - 1);
29     quick_sort(a, first + 1, high);
30 }

然後程序運行之後沒有任何翻譯。原因不清楚，求人解答

看看正確的應該怎麼寫：

 1 #include <iostream>
 2  
 3 using namespace std;
 4  
 5 void Qsort(int a[], int low, int high)
 6 {
 7     if(low >= high)
 8     {
 9         return;
10     }
11     int first = low;
12     int last = high;
13     int key = a[first];/*ÓÃ×Ö±íµÄµÚÒ»¸ö¼Ç¼×÷ΪÊàÖá*/
14  
15     while(first < last)
16     {
17         while(first < last && a[last] >= key)
18         {
19             --last;
20         }
21  
22         a[first] = a[last];/*½«±ÈµÚÒ»¸öСµÄÒƵ½µÍ¶Ë*/
23  
24         while(first < last && a[first] <= key)
25         {
26             ++first;
27         }
28          
29         a[last] = a[first];    
30 /*½«±ÈµÚÒ»¸ö´óµÄÒƵ½¸ß¶Ë*/
31     }
32     a[first] = key;/*ÊàÖá¼Ç¼µ½Î»*/
33     Qsort(a, low, first-1);
34     Qsort(a, first+1, high);
35 }
36 int main()
37 {
38     int a[] = {57, 68, 59, 52, 72, 28, 96, 33, 24};
39  
40     Qsort(a, 0, sizeof(a) / sizeof(a[0]) - 1);/*ÕâÀïÔ­ÎĵÚÈý¸ö²ÎÊýÒª¼õ1·ñÔòÄÚ´æÔ½½ç*/
41  
42     for(int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
43     {
44         cout << a[i] << " ";
45     }
46      
47     return 0;
48 }