伊莉討論區

標題: 快速排序~問題 [打印本頁]

---

作者: aa627097    時間: 2013-6-1 01:34 PM     標題: 快速排序~問題

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. void Swap(int *x,int *y)
   
5. {
   
6. int z;
   
7.   z=*x;
   
8.   *x=*y;
   
9.   *y=z;
   
10. }
    
11. 
    
12. 
    
13. void QSort(int a[],int h,int r)
    
14. {
    
15.      int i,j,m;
    
16.      i=h+1;
    
17.      j=r;
    
18.      if ((h==r)||(h>r))  return;
    
19.      while(i<j)
    
20.      {
    
21.                
    
22.        while (a[h]>a[i])
    
23.           i++;
    
24.        while (a[h]<a[j])
    
25.           j--;
    
26.       
    
27.       if(i >= j) break;
    
28. 
    
29.           Swap(&(a[i]),&(a[j]));
    
30.      }        
    
31.      
    
32.      Swap(&(a[h]),&(a[j]));
    
33. 
    
34.      QSort(a,h,j-1);
    
35.      QSort(a,i,r);
    
36. 
    
37. }
    
38. 
    
39. main()
    
40. {
    
41.       int a[10]={5,8,11,4,6,17,3,2,19,1},i;
    
42.       
    
43.       QSort(a,0,9);
    
44.       
    
45.       for(i=0;i<10;i++)
    
46.          cout << a[i] << " ";
    
47.          
    
48.       cout << endl;   
    
49.       system("pause");
    
50. }

複製代碼

在練習快速排序時~寫成這樣~
感覺程序怪怪的~改數字就錯了~誰能告訴我哪裡出錯嗎?萬分感謝><

---

作者: aa627097    時間: 2013-6-1 06:18 PM

因為這組數字帶進去的答案會是:1,2,3,4,5,6,8,11,17,19
但是我把int a[10]={5,8,11,4,6,17,3,2,19,1}改成int a[10]={5,8,1,4,6,17,3,2,19,11}
答案會變成 2,1,3,4,5,6,8,11,17,19

---

作者: snowflying    時間: 2013-6-1 06:45 PM

aa627097 發表於 2013-6-1 06:18 PM
因為這組數字帶進去的答案會是:1,2,3,4,5,6,8,11,17,19
但是我把int a[10]={5,8,11,4,6,17,3,2,19,1}改成in ...

某一次 1 2 3 4 5 17 6 8 19 11
接下來呼叫 Qsort(a , 0 , 1)
因為 i >= j 所以迴圈沒進去
但離開迴圈後有個 swap()
導致 2 被換到 1 的前面了

---

作者: aa627097    時間: 2013-6-1 07:05 PM

snowflying 發表於 2013-6-1 06:45 PM
某一次 1 2 3 4 5 17 6 8 19 11
接下來呼叫 Qsort(a , 0 , 1)
因為 i >= j 所以迴圈沒進去

所以我要怎麼改阿><我還是新手QQ

---

作者: snowflying    時間: 2013-6-1 09:56 PM

aa627097 發表於 2013-6-1 07:05 PM
所以我要怎麼改阿>

我不保證我的 code 沒有 BUG 唷
參考用，比較一下兩份的差異

1. void QSort(int a[] , int left , int right)
   
2. {
   
3.         if(left >= right)
   
4.             return;
   
5.         int x = left + 1;
   
6.         int y = right;
   
7.         int pivot = a[left];
   
8.        
   
9.         while(x <= y)
   
10.         {
    
11.                 while(a[x] < pivot && x <= right) ++x;
    
12.                 while(a[y] >= pivot && y > left) --y;
    
13.                 if(x < y)
    
14.                         swap(a[x] , a[y]);
    
15.         }
    
16.         swap(a[left] , a[y]);
    
17.         QSort(a , left , y - 1);
    
18.         QSort(a , x , right);
    
19. }

複製代碼

---

歡迎光臨 伊莉討論區 (http://a401.file-static.com/)

Powered by Discuz!