2

I want to sort a string in C according to the ASCII value of each char in the string. I write a quick sort to do this. My code is as following:

#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");
}

But it can only work when the string is very short, say "bac". When the string is longer, the result is wrong. It would be helpful if anyone could give me any ideas.

4

1 回答 1

3

您的分区算法是有损的。

当条件为真时，如下：

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

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

另一个也是如此if。

于 2013-05-12T08:01:45.003 回答