如何使这个 QuickSort（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= %s\n", 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); 
}

最后，快速排序函数：

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;
}

如何使这个 QuickSort（C 语言代码）算法适用于字符串数组？

How to adapt this QuickSort (coded in C language) algortim to an array of strings?

c

arrays

sorting

string

quicksort

更新：