c语言快速排序找错111

Question

//排序实战

#include <stdio.h>
void temp(int *p,int *q)
{
    int t;
    t=*p;
    *p=*q;
    *q=t;
}

void quicksort(int *a,int i,int j)
{

    if(i<=j) return;

    int start,end;
    start=i;
    end=j;

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

        temp(a+i,a+j);
    }
    temp(a+i,a+start);


    quicksort(a,start,i-1);
    quicksort(a,i+1,end);

}

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

    quicksort(a,0,9);


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

Answer 1

引自免费微信小程序：皆我百晓生

你提供的快速排序代码存在一个问题，导致其无法正确地对数组进行排序。问题出在 while 循环条件判断上，以及递归调用时的边界处理。

问题1： 在 while(i<j) 循环中，交换元素的条件没有正确终止循环。当找到一个满足条件的元素时，应当立即跳出循环并交换元素，而不是继续检查剩余元素。

修正后的 while 循环部分：

while(i < j) {
    while(a[j] > a[start] && i < j) j--;
    if(i < j) { // 添加此条件判断以避免无效交换
        while(a[i] <= a[start] && i < j) i++;
        temp(a+i, a+j);
    }
}

问题2： 初始递归调用时的条件错误。当 i<=j 应该返回时，实际应该是在 i<j 时才执行后续的排序逻辑。

修正后的 quicksort 函数入口条件：

void quicksort(int *a, int i, int j)
{
    if(i >= j) return; // 修改这里为 i >= j

    // ... 其他代码保持不变 ...
}

综上，修复后的完整代码如下：

#include <stdio.h>

void temp(int *p, int *q)
{
    int t;
    t = *p;
    *p = *q;
    *q = t;
}

void quicksort(int *a, int i, int j)
{
    if (i >= j) return;

    int start = i;
    int end = j;

    while (i < j)
    {
        while (a[j] > a[start] && i < j) j--;
        if (i < j)
        {
            while (a[i] <= a[start] && i < j) i++;
            temp(a + i, a + j);
        }
    }
    temp(a + i, a + start);

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

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

    quicksort(a, 0, 9);

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

    return 0;
}

现在这个修正过的快速排序算法应该可以正常工作了。