[問題] quicksort swap pivot時出現問題

看板C_and_CPP作者nasty1122 (阿寶)時間6年前 (2019/04/08 21:59)推噓4(4推 0噓 7→)

留言11則, 3人參與討論串1/3 (看更多)

完整程式碼： #include <stdio.h> #include <stdlib.h> void swap(int *a, int *b){ int temp = *a; *a = *b; *b = temp; } int Partition(int *arr, int front, int end){ int pivot = arr[(end+front)/2]; int i = front -1, j; //i denotes the position of the key where all the elements in the front are smaller than pivot. for (j = front; j < end+1; j++) { if (arr[j] < pivot) { i++; swap(&arr[i], &arr[j]); } } i++; swap(&arr[i], &pivot); //put pivot into the middle of the two subarrays return i; } void QuickSort(int *arr, int front, int end){ if (front < end) { int p = Partition(arr, front, end); QuickSort(arr, front, p - 1); QuickSort(arr, p + 1, end); } } int main() { int n,i; scanf("%d",&n); int arr[n]; for(i=0;i<n;i++){ scanf("%d",&arr[i]); } QuickSort(arr, 0, n-1); for (i = 0; i < n; i++) { printf("%d ",arr[i]); } return 0; } 這是一個以array中間為pivot的quicksort，第一個輸入的數字表示有幾個數字要排序，但我的輸出結果卻是這樣：假設輸入:10 4 8 7 2 3 5 6 9 10 1 輸出結果： 1 2 3 3 3 5 6 7 8 9 10 有些數字莫名其妙就被換掉了，好像是在Partition迴圈結束那邊swap arr[i]跟pivot的地方出問題，但我怎麼看都看不出原因，求各位大神指教，感謝~~ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.171.201.122 ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1554731979.A.52E.html ※ 編輯: nasty1122 (118.171.201.122), 04/08/2019 22:03:55 ※ 編輯: nasty1122 (118.171.201.122), 04/08/2019 22:04:35 ※ 編輯: nasty1122 (118.171.201.122), 04/08/2019 22:05:30

推

LPH66

04/08 22:24, 6年前 , 1^F

04/08 22:24, 1^F

推

james80351

04/08 22:54, 6年前 , 2^F

04/08 22:54, 2^F

→

james80351

04/08 22:58, 6年前 , 3^F

04/08 22:58, 3^F