如何将这个快速排序(用C语言编码)算法调整为字符串数组

Question

我需要对内容进行排序(使用字符串数组的strcmp()按字母顺序排序，但不允许使用函数qsort()。使用此代码，我设法对数值进行排序，但我很难调整它来对字符串进行排序。

/* A utility function to swap two elements */
void swap(int* a, int* b) 
{ 
int t = *a; 
*a = *b; 
*b = t; 
} 
void swap_string(char c[63], char d[63]){
char temp[63];
strcpy(temp, c);
strcpy(c, d);
strcpy(d, temp);
}
/* This function takes last element as pivot, places 
the pivot element at its correct position in sorted 
array, and places all smaller (smaller than pivot) 
to left of pivot and all greater elements to right 
of pivot */
int partition (int arr[], int low, int high) 
{ 
int pivot = arr[high];    /* pivot */
int i = (low - 1);  /* Index of smaller element */
for (j = low; j <= high- 1; j++) 
{ 
/* If current element is smaller than the pivot */
if (arr[j] < pivot) 
{ 
i++;    /* increment index of smaller element */
swap(&arr[i], &arr[j]); 
} 
} 
swap(&arr[i + 1], &arr[high]); 
return (i + 1); 
} 
/* The main function that implements QuickSort 
arr[] --> Array to be sorted, 
low  --> Starting index, 
high  --> Ending index */
void quickSort(int arr[], int low, int high) 
{ 
if (low < high) 
{ 
/* pi is partitioning index, arr[p] is now 
at right place */
int pi = partition(arr, low, high); 
/* Separately sort elements before */
/* partition and after partition */
quickSort(arr, low, pi - 1); 
quickSort(arr, pi + 1, high); 
} 
}

Answer 1

首先，您只需要为字符串创建一个交换函数，而不需要为int创建

void swap(char ** a, char ** b) { 
char * t = *a;
*a = *b;
*b = t;
}

因为，您对字符串数组进行排序，所以使用输入** arr而不是arr[]这里，分区函数：

int partition (char ** arr, int low, int high) { 
char * pivot = arr[high];    // pivot 
int i = (low - 1);  // Index of smaller element 
for (int j = low; j <= high- 1; j++) { 
// If current element is smaller than the pivot 
if (strcmp(arr[j],pivot) < 0) { 
i++;    // increment index of smaller element 
swap(&arr[i], &arr[j]); 
} 
} 
swap(&arr[i + 1], &arr[high]); 
return (i + 1); 
}

快速排序功能：

void quickSort(char **arr, int low, int high) { 
if (low < high) { 
/* pi is partitioning index, arr[p] is now 
at right place */
int pi = partition(arr, low, high); 

quickSort(arr, low, pi - 1); 
quickSort(arr, pi + 1, high); 
} 
}

然后测试的主要功能：

int main(){
char *a = "abc";
char *b = "cdf";
swap(&a, &b);
printf("a = %s, b= %sn", a, b);
char * data[10]={"something2", "something0", "something1", "something6", "something8", "something4", "something5","something7", "something3", "something9"};
quickSort(data, 0, 9);
for(int i = 0; i < 10; i++) {
printf("%s, ", data[i]);
}
return 0;
}

更新：

如果您想要的正是一个数组producer[100][63]。您可以更改函数的声明。在本例中，我使用一个数组data[10][63]进行测试。事实上，你可以用100而不是10。

交换功能：

void swap(char a[63], char b[63]) { 
char t[63];
strcpy(t, a);
strcpy(a, b);
strcpy(b, t);
}

然后，分区函数：

int partition (char arr[10][63], int low, int high) { 
char * pivot = arr[high];    // pivot 
int i = (low - 1);  // Index of smaller element 
for (int j = low; j <= high- 1; j++) { 
// If current element is smaller than the pivot 
if (strcmp(arr[j],pivot) < 0) { 
i++;   
swap(arr[i], arr[j]); 
} 
} 
swap(arr[i + 1], arr[high]); 
return (i + 1); 
}

最后，quickSort函数：

void quickSort(char arr[10][63], int low, int high) { 
if (low < high) { 
/* pi is partitioning index, arr[p] is now 
at right place */
int pi = partition(arr, low, high); 
// Separately sort elements before 
// partition and after partition 
quickSort(arr, low, pi - 1); 
quickSort(arr, pi + 1, high); 
} 
} 

主要用于测试：

int main(){
char data[10][63]={"something2", "something0", "something1", "something6", "something8", "something4", "something5","something7", "something3", "something9"};
quickSort(data, 0, 9);
for(int i = 0; i < 10; i++) {
printf("%s, ", data[i]);
}
return 0;
}