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

GaoKui

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

1. #include <stdio.h>
   
2. #include <string.h>
   
3. 
   
4. #define MAX 101
   
5. 
   
6. void QuickSort_c(char[], int, int);// 用于排序字符数组
   
7. 
   
8. void QuickSort_c(char a[], int left, int right)// 快速排序
   
9. {
   
10.         int i = left, j = right;
    
11.         char temp;
    
12.         int middle = (left + right) / 2;
    
13.         while (i <= j)
    
14.         {
    
15.                 // 从左往右找到大于等于中间数字的第一个数
    
16.                 while (a[i] < a[middle])
    
17.                 {
    
18.                         i++;
    
19.                 }
    
20.                 // 从右往左找到小于等于中间数字的第一个数
    
21.                 while (a[j] > a[middle])
    
22.                 {
    
23.                         j--;
    
24.                 }
    
25.                 // 如果 i <= j，则互换
    
26.                 if (i <= j)
    
27.                 {
    
28.                         temp = a[i];
    
29.                         a[i] = a[j];
    
30.                         a[j] = temp;
    
31.                         i++;
    
32.                         j--;
    
33.                 }
    
34.         }
    
35.         // 如果 i 没走到最右边，递归
    
36.         if (i < right)// 是 right不是length！
    
37.         {
    
38.                 QuickSort_c(a, i, right);
    
39.         }
    
40.         // 如果 j 没走到最左边，递归
    
41.         if (j > left)// 是 left不是 0！
    
42.         {
    
43.                 QuickSort_c(a, left, j);
    
44.         }
    
45. }
    
46. 
    
47. int main(void)
    
48. {
    
49.         char a[MAX];// 用于输入
    
50.         int i;
    
51.         for (i = 0; i < MAX; i++)
    
52.         {
    
53.                 a[i] = '\0';// 初始化
    
54.         }
    
55.        
    
56.         gets(a);// 输入
    
57.        
    
58.         int length;
    
59.         length = strlen(a);// length的值是字符串长度，并且不包含结束符
    
60.        
    
61.         QuickSort_c(a, 0, length - 1);// 将单词中的字母当成数值大小排序
    
62.        
    
63.         putchar('\n');
    
64.         printf("%s\n", a);
    
65.        
    
66.         return 0;
    
67. }

复制代码

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

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

最佳答案

月排行榜 / 总排行榜

jhq999

2022-3-17 11:21:00

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

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

1. void QuickSort_c(char a[], int left, int right)// 快速排序
   
2. {
   
3.         if (right<=left)
   
4.         {
   
5.                 return ;
   
6.         }
   
7.         int i = left+1, j = right;
   
8.         char temp;
   
9.         //int middle = (left + right) / 2;
   
10.         int flag=0;
    
11.         while (i <j)
    
12.         {
    
13.                 if(a[i]>=a[left])
    
14.                 {
    
15.                         flag=1;
    
16.                         if(a[j]<a[left])
    
17.                         {
    
18.                                 temp=a[i];
    
19.                                 a[i]=a[j];
    
20.                                 a[j]=temp;
    
21.                                 flag=0;
    
22.                         }
    
23.                 }
    
24.                 if (flag)j--;
    
25.                 else i++;
    
26. 
    
27.         }
    
28. 
    
29.                 if (a[left]>a[i])
    
30.                 {
    
31.                         temp=a[i];
    
32.                         a[i]=a[left];
    
33.                         a[left]=temp;
    
34.                 }
    
35.        QuickSort_c(a, left, i-1);
    
36.        QuickSort_c(a, i, right);
    
37.       
    
38.       
    
39.                
    
40.      
    
41. }

复制代码

跳转到最佳答案楼层

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了，
我自己鼓捣的你看看

1. void QuickSort_c(char a[], int left, int right)// 快速排序
   
2. {
   
3.         if (right<=left)
   
4.         {
   
5.                 return ;
   
6.         }
   
7.         int i = left+1, j = right;
   
8.         char temp;
   
9.         //int middle = (left + right) / 2;
   
10.         int flag=0;
    
11.         while (i <j)
    
12.         {
    
13.                 if(a[i]>=a[left])
    
14.                 {
    
15.                         flag=1;
    
16.                         if(a[j]<a[left])
    
17.                         {
    
18.                                 temp=a[i];
    
19.                                 a[i]=a[j];
    
20.                                 a[j]=temp;
    
21.                                 flag=0;
    
22.                         }
    
23.                 }
    
24.                 if (flag)j--;
    
25.                 else i++;
    
26. 
    
27.         }
    
28. 
    
29.                 if (a[left]>a[i])
    
30.                 {
    
31.                         temp=a[i];
    
32.                         a[i]=a[left];
    
33.                         a[left]=temp;
    
34.                 }
    
35.        QuickSort_c(a, left, i-1);
    
36.        QuickSort_c(a, i, right);
    
37.       
    
38.       
    
39.                
    
40.      
    
41. }

复制代码