我对这个快速排序算法有一个问题:
void swap(int *x, int *y) {
int tmp;
tmp = *x;
*x = *y;
*y = tmp;
}
int partition (int *arr, int min, int max) {
int x = arr[min];
int i = min - 1;
int j = max + 1;
while (1) {
do {
j--;
} while (i < j && arr[j] < x);
do {
i++;
} while (arr[i] > x);
if (i < j)
swap(&arr[i], &arr[j]);
else
return j + 1;
}
}
void quickSort(int *arr, int inf, int sup) {
if (arr) {
if (inf < sup) {
int pivot = partition(arr, inf, sup);
//printf("pivot = %d", pivot);
quickSort(arr, inf, pivot - 1);
quickSort(arr, pivot + 1, sup);
}
}
}
int main() {
int array[] = { 151, 153, 134, 137, -1, -1, -1, -1, -1, 158, 158, -1, -1, 133, 127, 158, 158 };
int dim = sizeof(array) / sizeof(int);
quickSort(array, 0, dim - 1);
for (int i = 0; i < dim; i++) {
printf("%d ", array[i]);
}
printf("\n");
return 0;
}
它应该返回一个降序排序的数组,但由于某些原因,它没有。
输入:(512个元素长度的数组的其余部分由-1组成)
151 153 134 137 -1 -1 -1 -1 -1 158 158 -1 -1 133 127 158 158
输出:
158 158 158 153 158 -1 151 134 137 133 127 -1 -1 -1 -1 -1 -1
预期输出:
158 158 158 158 153 151 137 134 133 127 -1 -1 -1 -1 -1 -1 -1
我期望算法返回一个降序排序的数组。我试着切换输入,但似乎没有什么工作。
3条答案
按热度按时间pvcm50d11#
首先,你需要仔细调试你的分区函数。返回值应为
j
你可以使用gdb或任何ide调试主流程,你可以得到逻辑。对于quickSort函数,应该使用inf->pivot,pivot + 1 -> sup;而不是忽略数组透视索引。
希望能有所帮助。谢谢
mspsb9vt2#
https://en.wikipedia.org/wiki/Quicksort表示Hoare分区方案使用中间的元素作为枢轴元素。所以
int x=arr[min];
应该是int x=arr[(min+max)/2];
。partition
应该是return j;
,而不是j+1;
。第一个
quicksort
调用应该包含pivot元素。quicksort
函数中的if
也不完整。下面是工作代码(至少使用您的示例数据):
https://godbolt.org/z/54W6j145e
xzabzqsa3#
从维基百科页面关于霍尔分区方案的快速排序(强调我的):
Tony Hoare描述的原始分区方案使用两个指针(范围内的索引),它们从被分区数组的两端开始,然后彼此移动,直到它们检测到反转:一对元素,一个大于第一指针处的界限(枢轴值的霍尔项),一个小于第二指针处的界限;如果此时第一指针仍在第二指针之前,则这些元素相对于彼此的顺序错误,然后交换它们。在此之后,指针向内移动,并且重复对反转的搜索;当指针最终交叉时(第一个指针在第二个指针之后),不执行交换;找到有效的分区**,其具有交叉指针之间的划分点**(可能严格地在交叉指针之间的任何条目等于主元,并且可以从形成的两个子范围中排除)。利用该公式,一个子范围可能变成整个原始范围,这将阻止算法前进。因此,Hoare规定,在结束时,在(如果必要的话)将其与最接近分隔的子范围元素交换之后,通过排除该枢轴**,可以减小包含枢轴元素(其仍然处于其原始位置)的子范围的大小;从而确保快速排序的终止。
同一页显示了一个伪代码实现:
与OP的代码不同,对
quicksort
* 的第一次递归调用包括 * pivot,partition
返回j
而不是j + 1
。