c - 使用分区和交换按字母顺序排序

Question

所以我的程序使用分区排序将 10 个用户输入的名称按字母顺序重新打印。我以前从未使用过分区排序，所以在解决这个问题时我完全没有经验。

我正在使用数字分区排序的示例，并尝试使用 strcmp 对其进行操作以进行排序。

下面我的大部分代码都是我的代码，除了分区函数，这是我遇到问题的地方。有人可以帮助我了解这种排序的工作原理以及如何操作它以按字母顺序对 10 个名字进行排序吗？

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define DEBUG_LEVEL 0

int partition(int a[], int left, int right);
void swap(int *a, int *b);

#define SIZE    10

int main(int argc, const char * argv[]) {

char Names[10][10];
int count = 10;
int i;
int a[SIZE];

printf("Enter 10 names:");
for (i=0; i < count; ++i)
{
    gets(Names[i]);
}
printf("\n\n");
partition(a, 0, SIZE -1);
printf("The names in alphabetical order are\n");
for (i=0; i< count; ++i)
{
    printf("%s\n",Names[i]);
}
getchar();
}

 int partition(int a[], int left, int right) {
int i, j, key;

key = a[left];
i = left + 1;
j = right;
   while (strcmp(i, j) <0) {
while (i <= right && a[i] <= key)
 ++i;
 while (j >= left && a[j] > key)
 --j;
 if (i < j)
 swap(&a[i], &a[j]);
    }
    swap(&a[left], &a[j]);
    return j;
 }

void swap(int *a, int *b)   {
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

Answer 1

可以找到此分区排序方法的简短说明以及长文章的链接。 G。在维基百科上:Quicksort .

由于 chux 所说的原因以及子分区的递归调用丢失，显示的代码无法工作。这是一个工作版本:

void swap(char a[10], char b[10])
{
    char temp[10];
    strcpy(temp, a);
    strcpy(a, b);
    strcpy(b, temp);
}

void partition(char Names[][10], int left, int right)
{
    int i, j;
    char *key;
    if (right <= left) return;

    key = Names[left];
    i = left+1;
    j = right;
    for (; ; )
    {
        while (i <= right && strcmp(Names[i], key) <= 0) ++i;
        while (j >= left  && strcmp(Names[j], key) >  0) --j;
        if (i < j) swap(Names[i], Names[j]);
        else     { swap(     key, Names[j]); break; }
    }
    partition(Names, left, j-1);
    partition(Names, i, right);
}