C语言中的Quicksort字符串数组

分配quicksort的理由为零，实际上，对于您的情况，该函数可以通过使用quick-math（char * arr []，unsigned int len）的简单接口（对于子序列调用使用pointer-math）就足够了。

提供用于交换指针的交换算法：

void swap_str_ptrs(char const **arg1, char const **arg2)
{
    const char *tmp = *arg1;
    *arg1 = *arg2;
    *arg2 = tmp;
}

那么算法是：

void quicksort_strs(char const *args[], unsigned int len)
{
    unsigned int i, pvt=0;

    if (len <= 1)
        return;

    // swap a randomly selected value to the last node
    swap_str_ptrs(args+((unsigned int)rand() % len), args+len-1);

    // reset the pivot index to zero, then scan
    for (i=0;i<len-1;++i)
    {
        if (strcmp(args[i], args[len-1]) < 0)
            swap_str_ptrs(args+i, args+pvt++);
    }

    // move the pivot value into its place
    swap_str_ptrs(args+pvt, args+len-1);

    // and invoke on the subsequences. does NOT include the pivot-slot
    quicksort_strs(args, pvt++);
    quicksort_strs(args+pvt, len - pvt);
}

那就是一切。包括分区。

怎么运行的

有两种通用的递归快速排序算法：挤压和扫描。这是扫描算法。我们按顺序前进，将小于“小于”枢轴值（在循环开始前交换到序列末尾）的任何元素交换到目标位置，该位置的索引最初是序列的开始，并随着每个交换操作。完成“扫描”后，pvt索引就是枢轴值所属的位置，因为该插槽下方的所有内容都“小于”该值。因此，又进行了一次交换以将枢轴值放入位置。之后，我们有两个分区，它们是递归的。不包含在这些分区中的任何一个中。这是我们知道的唯一价值在于它的最终安息之地。

测试哈纳斯

包括上面的代码，我们用一组基本的字符串进行测试，这些字符串有意地乱序：

void print_list(char const *args[], unsigned len)
{
    unsigned i=0;
    for (;i<len;++i)
        puts(args[i]);
}

int main()
{
    char const *args[] =
    {
        "this", "is", "a", "test", "of", "quicksort", "with", "strings"
    };

    srand((unsigned)time(NULL));
    quicksort_strs(args, sizeof(args)/sizeof(*args));
    print_list(args, sizeof(args)/sizeof(*args));
    return 0;
}

输出

a
is
of
quicksort
strings
test
this
with

非递归实现

应当指出的是，上述算法使其本身精美的非递归实现。本地动态堆栈用于保存数据对：指针和长度。经过优化，不会将琐碎的段（长度为1或0的段）压入堆栈，一种实现方式是这样的：

void quicksort_strs(char const *args[], unsigned int len)
{
    // holds our non-recursive stack of segments
    struct segment
    {
        char const **arr;
        unsigned int len;
        struct segment* next;
    } *stack = NULL;

    stack = malloc(sizeof(*stack));
    stack->arr = args;
    stack->len = len;
    stack->next = NULL;

    while (stack != NULL)
    {
        unsigned int i, pvt=0;
        struct segment *tmp = stack;
        stack = stack->next;

        // pull values and delete segment record
        args = tmp->arr;
        len = tmp->len;
        free(tmp);

        // nothing to unary segments
        if (len <= 1)
            continue;

        // swap a randomly selected value to the last node
        swap_str_ptrs(args+((unsigned int)rand() % len), args+len-1);

        // reset the pivot index to zero, then scan
        for (i=0;i<len-1;++i)
        {
            if (strcmp(args[i], args[len-1]) < 0)
                swap_str_ptrs(args+i, args+pvt++);
        }

        // move the pivot value into its place
        swap_str_ptrs(args+pvt, args+len-1);

        // lhs segment push
        if (pvt > 1)
        {
            tmp = malloc(sizeof(*tmp));
            tmp->arr = args;
            tmp->len = pvt;
            tmp->next = stack;
            stack = tmp;
        }

        // rhs segment push
        if ((len - ++pvt) > 1)
        {
            tmp = malloc(sizeof(*tmp));
            tmp->arr = args+pvt;
            tmp->len = len-pvt;
            tmp->next = stack;
            stack = tmp;
        }
    }
}

显然，使用固定的节点堆栈实现将大大缩短此过程，但是这个想法应该显而易见。将realloc()节点保存在“堆栈”的末尾而不是开始的模式同样会很有趣，因为它将消除对next指针管理的需求，而将其替换为top索引。

无论如何，祝您好运，希望对您有所帮助。