[已解决]小甲鱼 S1E36快速排序 中的代码，用于排序字符串出现了奇怪的问题

GaoKui

代码的目的是把输入的字符串按照字母顺序进行排序，如下

#include <stdio.h>
#include <string.h>

#define MAX 101

void QuickSort_c(char[], int, int);// 用于排序字符数组

void QuickSort_c(char a[], int left, int right)// 快速排序 
{
        int i = left, j = right;
        char temp; 
        int middle = (left + right) / 2;
        while (i <= j)
        {
                // 从左往右找到大于等于中间数字的第一个数
                while (a[i] < a[middle])
                {
                        i++;
                } 
                // 从右往左找到小于等于中间数字的第一个数
                while (a[j] > a[middle])
                {
                        j--;
                }
                // 如果 i <= j，则互换
                if (i <= j)
                {
                        temp = a[i];
                        a[i] = a[j];
                        a[j] = temp;
                        i++;
                        j--; 
                }
        }
        // 如果 i 没走到最右边，递归 
        if (i < right)// 是 right不是length！ 
        {
                QuickSort_c(a, i, right);
        }
        // 如果 j 没走到最左边，递归
        if (j > left)// 是 left不是 0！ 
        {
                QuickSort_c(a, left, j);
        }
}

int main(void)
{
        char a[MAX];// 用于输入 
        int i;
        for (i = 0; i < MAX; i++)
        {
                a[i] = '\0';// 初始化 
        }
        
        gets(a);// 输入 
        
        int length;
        length = strlen(a);// length的值是字符串长度，并且不包含结束符 
        
        QuickSort_c(a, 0, length - 1);// 将单词中的字母当成数值大小排序
        
        putchar('\n');
        printf("%s\n", a);
        
        return 0;
}

结果：
当输入：qazwsxedcrfvtgbyhnujmikolp
会输出：abcdeflghikopqrsjmnutvwxyz

为什么没有完全排序正确呢？

最佳答案

月排行榜 / 总排行榜

jhq999

2022-3-17 11:21:00

GaoKui 发表于 2022-3-17 09:46
虽然好像并不是那个字符串没有完全排序正确的原因，但这么说的话也就是说小甲鱼那一节的代码是有问题的是 ...

我看错了，到9，i就停在3了，
我自己鼓捣的你看看

void QuickSort_c(char a[], int left, int right)// 快速排序 
{
        if (right<=left)
        {
                return ;
        }
        int i = left+1, j = right;
        char temp; 
        //int middle = (left + right) / 2;
        int flag=0;
        while (i <j)
        {
                if(a[i]>=a[left])
                {
                        flag=1;
                        if(a[j]<a[left])
                        {
                                temp=a[i];
                                a[i]=a[j];
                                a[j]=temp;
                                flag=0;
                        }
                }
                if (flag)j--;
                else i++;

        }
 
                if (a[left]>a[i])
                {
                        temp=a[i];
                        a[i]=a[left];
                        a[left]=temp;
                }
       QuickSort_c(a, left, i-1);
       QuickSort_c(a, i, right);
      
       
                
     
}

跳转到最佳答案楼层

jhq999

3，1，7，9，2，5，4
middle=3//a[3]=9;
//跑到这里（// 如果 i 没走到最右边，递归）时
i=j=length-1=right;
i==right;
j>left;
QuickSort_c(a, left, j);//j==right;
无限递归

GaoKui

jhq999 发表于 2022-3-17 07:37
3，1，7，9，2，5，4
middle=3//a[3]=9;
//跑到这里（// 如果 i 没走到最右边，递归）时

虽然好像并不是那个字符串没有完全排序正确的原因，但这么说的话也就是说小甲鱼那一节的代码是有问题的是吗

jhq999

GaoKui 发表于 2022-3-17 09:46
虽然好像并不是那个字符串没有完全排序正确的原因，但这么说的话也就是说小甲鱼那一节的代码是有问题的是 ...

我看错了，到9，i就停在3了，
我自己鼓捣的你看看

void QuickSort_c(char a[], int left, int right)// 快速排序 
{
        if (right<=left)
        {
                return ;
        }
        int i = left+1, j = right;
        char temp; 
        //int middle = (left + right) / 2;
        int flag=0;
        while (i <j)
        {
                if(a[i]>=a[left])
                {
                        flag=1;
                        if(a[j]<a[left])
                        {
                                temp=a[i];
                                a[i]=a[j];
                                a[j]=temp;
                                flag=0;
                        }
                }
                if (flag)j--;
                else i++;

        }
 
                if (a[left]>a[i])
                {
                        temp=a[i];
                        a[i]=a[left];
                        a[left]=temp;
                }
       QuickSort_c(a, left, i-1);
       QuickSort_c(a, i, right);
      
       
                
     
}