c语言快速排序找问题

Question

#include <stdio.h>

void temp(int *a,int *b)
{
    int t;
    t=*a;
    *a=*b;
    *b=t;
}


void quicksort(int *a,int left,int right)
{
    int f,start,end;

    start=left;
    end=right;

    f=left;

    while(left<right)
    {
        while(a[right]>=a[f]&&right>left)
            right--;
        while(a[left]<=a[f]&&left<right)
            left++;

        temp(a+left,a+right);
    }

    temp(a+left,a+f);

    quicksort(a,start,left-1);
    quicksort(a,left+1,end);
}


int main()
{
    int a[10]={7,4,1,2,5,8,3,6,9,10};

    quicksort(a,0,9);

    for(int i=0;i<10;i++)
        printf("%d ",a[i]);
}

Answer 1

此回答引用GPT4,由博主鑫宝Code参考后得出

您提供的C语言代码实现了一个快速排序算法，但其中存在一个逻辑错误。在while(left<right)循环中，你没有正确更新枢轴（pivot）的位置。以下是修正后的代码：

#include <stdio.h>

void swap(int *a, int *b) {
    int t;
    t = *a;
    *a = *b;
    *b = t;
}

void quicksort(int *a, int left, int right) {
    if (left >= right) return; // 如果left已经大于等于right，说明数组只有一个或零个元素，无需继续分割

    int f = a[left]; // 将最左边的元素作为初始枢轴
    int i = left, j = right;

    while (i < j) {
        while (a[j] >= f && i < j) {
            j--;
        }
        while (a[i] <= f && i < j) {
            i++;
        }

        if (i < j) { // 防止在i和j交叉时依然交换
            swap(a + i, a + j);
        }
    }

    // 将枢轴元素放到最终位置
    a[left] = a[i];
    a[i] = f;

    // 递归对左右两边进行快速排序
    quicksort(a, left, i - 1);
    quicksort(a, i + 1, right);
}

int main() {
    int a[10] = {7, 4, 1, 2, 5, 8, 3, 6, 9, 10};

    quicksort(a, 0, 9);

    for (int i = 0; i < 10; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");

    return 0;
}

主要修改点：

1. 添加了当left >= right时直接返回的条件，以避免处理单个或零个元素的情况。
2. 在while循环外部移动枢轴元素到其最终位置。
3. 修改swap函数名称为swap，使其更具可读性。

现在这段代码应该能正确地对数组进行快速排序了。