我在快速排序方面遇到了一些问题。我所做的算法执行并在最后打印数字。但没有订购。你能看看能不能发现任何缺陷吗?你能帮我一下吗?
#include <stdio.h>
#include <stdlib.h>
int partition (int numbers[], int arrayStart, int arrayEnd) {
int pivot = numbers[arrayEnd];
int partitionIndex = arrayStart;
for (int i = arrayStart; i < arrayEnd; i++) {
if (numbers[i] <= pivot) {
int temp = numbers[partitionIndex];
numbers[partitionIndex] = numbers[i];
numbers[i] = temp;
partitionIndex = partitionIndex + 1;
}
int temp2 = numbers[partitionIndex];
numbers[partitionIndex] = numbers[arrayEnd];
numbers[arrayEnd] = temp2;
return partitionIndex;
}
}
void QuickSort (int numbers[], int arrayStart, int arrayEnd) {
if (arrayStart < arrayEnd) {
int partitionIndex = partition (numbers, arrayStart, arrayEnd);
QuickSort(numbers, arrayStart, partitionIndex - 1);
QuickSort(numbers, partitionIndex + 1, arrayEnd);
}
else {
return;
}
}
int main() {
int numbers[6] = {2, 5, 1, 6, 3, 4};
int arrayStart = 0;
int arrayEnd = 5;
QuickSort(numbers, arrayStart, arrayEnd);
for (int i = 0; i < 6; i++) {
printf("%d ", numbers[i]);
}
}
最佳答案
问题出在你的分区函数上。你在for循环中返回了partitionIndex
更正逻辑
int partition (int numbers[], int arrayStart, int arrayEnd)
{
int pivot = numbers[arrayEnd];
int partitionIndex = arrayStart;
for (int i = arrayStart; i < arrayEnd; i++)
{
if (numbers[i] <= pivot)
{
int temp = numbers[partitionIndex];
numbers[partitionIndex] = numbers[i];
numbers[i] = temp;
partitionIndex = partitionIndex + 1;
}
}
int temp2 = numbers[partitionIndex];
numbers[partitionIndex] = numbers[arrayEnd];
numbers[arrayEnd] = temp2;
return partitionIndex;
}
完整代码
#include <stdio.h>
#include <stdlib.h>
int partition (int numbers[], int arrayStart, int arrayEnd)
{
int pivot = numbers[arrayEnd];
int partitionIndex = arrayStart;
for (int i = arrayStart; i < arrayEnd; i++)
{
if (numbers[i] <= pivot)
{
int temp = numbers[partitionIndex];
numbers[partitionIndex] = numbers[i];
numbers[i] = temp;
partitionIndex = partitionIndex + 1;
}
}
int temp2 = numbers[partitionIndex];
numbers[partitionIndex] = numbers[arrayEnd];
numbers[arrayEnd] = temp2;
return partitionIndex;
}
void QuickSort (int numbers[], int arrayStart, int arrayEnd)
{
if (arrayStart < arrayEnd)
{
int partitionIndex = partition (numbers, arrayStart, arrayEnd);
QuickSort(numbers, arrayStart, partitionIndex - 1);
QuickSort(numbers, partitionIndex + 1, arrayEnd);
}
else
{
return;
}
}
int main() {
int numbers[6] = {2, 5, 1, 6, 3, 4};
int arrayStart = 0;
int arrayEnd = 5;
QuickSort(numbers, arrayStart, arrayEnd);
for (int i = 0; i < 6; i++) {
printf("%d ", numbers[i]);
}
}
输出
1 2 3 4 5 6 Program ended with exit code: 0
关于c - 快速排序的问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45826933/