作者nasty1122 (阿宝)
看板C_and_CPP
标题[问题] quicksort swap pivot时出现问题
时间Mon Apr 8 21:59:37 2019
完整程式码：
#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://webptt.com/cn.aspx?n=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
1F：推 LPH66: 因为你的那个对换不是阵列元素对换04/08 22:24
2F：推 james80351: 那个地方是要和前面pivot代表的元素做交换04/08 22:54
3F：→ james80351: arr[(front + end) / 2]04/08 22:58
但因为pivot是middle的话在回圈内就会一直被换来换去，所以最後那边不能写arr
[(front+end)/2]，有其他方式可以表示pivot最後在的位置吗?
※ 编辑: nasty1122 (118.171.201.122), 04/08/2019 23:47:52
4F：推 LPH66: 所以一个常见的方法其实是先把 pivot 放在阵列"开头"04/09 07:17
5F：→ LPH66: 接着用你的方法维护成 [pv][<pv ... <pv][>pv ... >pv]04/09 07:18
6F：→ LPH66: 最後再用你这一步想做的交换把 [pv] 摆在两块中间04/09 07:18
7F：→ LPH66: 概念上其实和你已经写好的差不多, 只是不是另起变数存 pv04/09 07:19
8F：→ LPH66: 重点在於这一步既然要是阵列元素对换, 那就把 pv 也摆进去04/09 07:20
9F：→ LPH66: 定位问题就先找个好定位的地方放就好 (例如阵列开头)04/09 07:21
感谢回答，其实我原本写的就是把pivot放最後的，这样交换不会有问题没错，但就是想
试试看把pivot放中间，有没有方法可以追踪pivot最後换到的位子呢?
※ 编辑: nasty1122 (101.9.7.42), 04/09/2019 15:09:44
10F：推 goddbird: 其实在swap里改成&arr[你的pivot_idx]就会对了吧？小弟04/11 20:43
11F：→ goddbird: 也弱弱的还麻烦分享一下结果04/11 20:43
後来再加一个变数存pivot index就可以了，感谢你~~
※ 编辑: nasty1122 (115.82.133.211), 04/12/2019 12:59:23
※ 编辑: nasty1122 (101.8.162.223), 04/14/2019 13:08:51