c - 用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也是如此。