使用快速排序對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也一樣。