关于快排的测试代码问题

Question

函数部分是拿的别人网课的，应该没问题，但为什么就得不出正确的结果，我写的主函数不知哪里有错，求教
#include
#include
#define ElementType int
void Swap(ElementType * a, ElementType* b)
{
ElementType t = a; *a = *b; *b = t;
}
//选出一个不大不小的数
ElementType Median3(ElementType A[], int Left, int Right)
{
int Center = (Left + Right) / 2;
if (A[Left] > A[Center])
Swap(&A[Left], &A[Center]);
if (A[Left] > A[Right])
Swap(&A[Left], &A[Right]);
if (A[Center] > A[Right])
Swap(&A[Center], &A[Right]);
/ 此时A[Left] <= A[Center] <= A[Right] /
Swap(&A[Center], &A[Right - 1]); / 将基准Pivot藏到右边*/
/* 只需要考虑A[Left+1] … A[Right-2] /
return A[Right - 1]; / 返回基准Pivot /
}
//快排实现过程
void Qsort(ElementType A[], int Left, int Right)
{ / 核心递归函数 */
int Pivot, Cutoff, Low, High;

    Pivot = Median3(A, Left, Right); /* 选基准 */
    Low = Left; High = Right - 1;
    while (1) { /*将序列中比基准小的移到基准左边，大的移到右边*/
        while (A[++Low] < Pivot);
        while (A[--High] > Pivot);
        if (Low < High) Swap(&A[Low], &A[High]);
        else break;
    }
    Swap(&A[Low], &A[Right - 1]);   /* 将基准换到正确的位置 */
    Qsort(A, Left, Low - 1);    /* 递归解决左边 */
    Qsort(A, Low + 1, Right);   /* 递归解决右边 */

}
//优化接口
void QuickSort(ElementType A[], int N)
{ /* 统一接口 */
Qsort(A, 0, N - 1);
}
//输出函数
void print_array(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = { 34,65,12,43,67,5,78,10,3,70 };
int len = sizeof(arr) / sizeof(int);
//输出 原来的序列
printf("First array is \n");
print_array(arr, 10);

QuickSort(arr, 10);

//输出排序完的序列
printf("\nSorted array is \n");
print_array(arr, 10);
return 0;
}

Answer 1

你可以把排版整理一下，我再帮你看看， 你这个太乱了

下面这个代码应该看着清晰一点 。 看懂就行了吧，可以把partion自己实现一下加深印象

#include <stdio.h>

//交换两个数
void swap(int* a, int* b) {
    int tmp = *a; 
    *a = *b; 
    *b = tmp;
}

//array中选择一个基准，所有小于基准放左边，大于基准放右边，返回基准值
int partion(int* array, int low, int high) {
    int pivot = array[high];    //基准

    int i = low;
    int j = high - 1;

    //while循环将所有小于基准的放i前面，大于基准的放i后面
    while (1) {
        while (array[i] <= pivot && i != j) {
            i++;
        }   

        while(array[j] >= pivot && i != j) {
            j--;
        }   

        if (i != j) {
            swap(&array[i], &array[j]);
        } else {
            break;
        }   
    }   

    if (array[i] > pivot) {
        swap(&array[i], &array[high]);
    } else {
        swap(&array[i + 1], &array[high]);
    }   
    return i;
}

/*
 * quickSort的思想 ： 在一个数组中选一个基准数， 将所有小于基准的数放基准前面，大于基准的数放基准后面
 */
int quickSort(int* array, int low, int high) {
    if (low < high) {
        int pi = partion(array, low, high);

        quickSort(array, low, pi - 1);
        quickSort(array, pi + 1, high);
    }
}

//数组打印
void printArray(int* arr, int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main()
{
    int arr[] = {17, 7, 8, 9, 1, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    printArray(arr, n);
    quickSort(arr, 0, n-1);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}