我试图在c语言中实现快速排序,但排序并不像预期的那样发生。
#include <stdio.h>
void quickSort(int arr[], int length);
void qSrtRec(int arr[], int low, int high);
void swap(int* x, int* y);
int partition(int arr[], int low, int high);
int main() {
int arr[] = { 5,3,7,0,1,4,8,9,6,2 }; // test array
quickSort(arr, sizeof(arr) / sizeof(arr[0]));
for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
printf("%d, ", arr[i]);
printf("\n");
return 0;
}
void swap(int* x, int* y) {
*x += *y;
*y = *x - *y;
*x -= *y;
}
void quickSort(int arr[], int length) {
qSrtRec(arr, 0, length - 1);
}
void qSrtRec(int arr[], int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high);
qSrtRec(arr, low, pivot - 1);
qSrtRec(arr, pivot + 1, high);
}
}
int partition(int arr[], int low, int high) {
int i = low, pivotValue = arr[high];
for (int j = low; j < high; j++)
if (arr[j] <= pivotValue) {
swap(&arr[i], &arr[j]);
i++;
}
swap(&arr[high], &arr[i]);
return i;
}
与测试数组相比,我得到的输出为0,0,2,0,0,0,0,7,0,0。交换函数工作正常,但我不确定分区函数。
1条答案
按热度按时间t3psigkw1#
Swap
函数是问题所在。如果将其替换为以下内容,它将工作:程序现在输出
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,