使用快速排序对C中的字符串进行排序

Question

我想根据字符串中每个字符的ASCII值对C中的字符串进行排序。我写了一个快速排序来做到这一点。我的代码如下：

#include<stdio.h> 
#include<stdlib.h> 
void quick_sort(char* str, int l, int r){ 
    if(l < r){ 
     int left = l; 
     int right = r; 
     char x = *str; 
     while(left < right){ 
      while(left < right && *(str+right) > x) 
       right--; 
      if(left < right) 
       *(str+(left++)) = *(str+right); 
      while(left < right && *(str+left) < x) 
       left++; 
      if(left < right) 
       *(str+(right--)) = *(str+left); 
     } 
     *(str+left) = x; 
     quick_sort(str, l, left-1); 
     quick_sort(str, right+1, r);  
    } 
} 

main(){ 
    char* str = (char*)malloc(sizeof(char)*100); 
    printf("please input a string: "); 
    scanf("%s", str); 
    printf("the original string is: %s\n", str); 
    quick_sort(str, 0, strlen(str)-1); 
    printf("the sorted string is: %s\n",str); 
    free(str); 
    system("pause"); 
} 

但它只能在字符串很短的时候才起作用，说“bac”。当字符串更长时，结果是错误的。如果有人能给我任何想法，这将是有益的。

Answer 1

您的分区算法是有损的。

当条件为真，以下内容：

 if(left < right) 
      *(str+(left++)) = *(str+right); 

覆盖str[left]。一旦发生这种情况，角色就会不可逆转地丢失。

其他if也一样。