这是一个家庭作业。我最终会将这段代码翻译成 MIPS 程序集，但这对我来说是容易的部分。我一直在调试这段代码好几个小时，并且一直在我的教授办公时间，但我仍然无法让我的快速排序算法工作。这是代码以及我对我认为问题区域所在位置的一些评论：
// This struct is in my .h file
typedef struct {
// v0 points to the first element in the array equal to the pivot
int *v0;
// v1 points to the first element in the array greater than the pivot (one past the end of the pivot sub-array)
int *v1;
} PartRet;
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
PartRet partition(int *lo, int *hi) {
// Will later be translating this to MIPS where 2 values can be returned. I am using a PartRet struct to simulate this.
PartRet retval;
// We must use the last item as the pivot
int pivot = *hi;
int *left = lo;
// Take the last value before the pivot
int *right = hi - 1;
while (left < right) {
while((left < hi) && (*left <= pivot)) {
++left;
}
while((right > lo) && (*right > pivot)) {
--right;
}
if (left < right) {
swap(left++, right--);
}
}
// Is this correct? left will always be >= right after the while loop
if (*hi < *left) {
swap(left, hi);
}
// MADE CHANGE HERE
int *v0 = hi;
int *v1;
// Starting at the left pointer, find the beginning of the sub-array where the elements are equal to the pivot
// MADE CHANGE HERE
while (v0 > lo && *(v0 - 1) >= pivot) {
--v0;
}
v1 = v0;
// Starting at the beginning of the sub-array where the elements are equal to the pivot, find the element after the end of this array.
while (v1 < hi && *v1 == pivot) {
++v1;
}
if (v1 <= v0) {
v1 = hi + 1;
}
// Simulating returning two values
retval.v0 = v0;
retval.v1 = v1;
return retval;
}
void quicksort(int *array, int length) {
if (length < 2) {
return;
}
PartRet part = partition(array, array + length - 1);
// I *think* this first call is correct, but I'm not sure.
int firstHalfLength = (int)(part.v0 - array);
quicksort(array, firstHalfLength);
int *onePastEnd = array + length;
int secondHalfLength = (int)(onePastEnd - part.v1);
// I have a feeling that this isn't correct
quicksort(part.v1, secondHalfLength);
}
我什至尝试使用在线代码示例重写代码，但要求是使用 lo 和 hi 指针，但我发现没有代码示例使用它。当我调试代码时，我最终只使代码适用于某些数组，而不是其他数组，尤其是当枢轴是数组中的最小元素时。