首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >如何使这个QuickSort (用C语言编写)算法适应字符串数组?

问如何使这个QuickSort (用C语言编写)算法适应字符串数组?
EN

Stack Overflow用户
提问于 2020-04-06 22:03:44
回答 1查看 68关注 0票数 0

我需要使用字符串数组的strcmp()按字母顺序对内容进行排序,但不允许使用qsort()函数。通过这段代码,我成功地对数值进行了排序,但为了对字符串进行排序,我很难对其进行调整。

代码语言:javascript
复制
/* 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); 
    } 
}
EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2020-04-06 23:02:06

首先,您只需要为string创建交换函数,而不需要为int创建交换函数

代码语言:javascript
复制
void swap(char ** a, char ** b) { 
    char * t = *a;
    *a = *b;
    *b = t;
}

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

代码语言:javascript
复制
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); 
}

和,quickSort函数:

代码语言:javascript
复制
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); 
    } 
}

然后进行测试的main函数:

代码语言:javascript
复制
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。

交换功能:

代码语言:javascript
复制
void swap(char a[63], char b[63]) { 
    char t[63];
    strcpy(t, a);
    strcpy(a, b);
    strcpy(b, t);
}

然后,划分函数:

代码语言:javascript
复制
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函数:

代码语言:javascript
复制
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); 
    } 
} 

测试的主要内容:

代码语言:javascript
复制
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;
}
票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/61061639

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档