C语言字符串排序详解：从qsort到快速排序

创作时间:

作者:

@小白创作中心

C语言字符串排序详解：从qsort到快速排序

引用

来源

https://docs.pingcode.com/baike/1038174

在C语言中对字符串进行排序是一个常见的编程需求，无论是处理项目管理中的任务名称，还是对数据进行整理，掌握字符串排序的方法都能显著提升程序的效率和可读性。本文将详细介绍几种常用的字符串排序方法，包括使用标准库函数qsort、冒泡排序、选择排序和快速排序，并分析它们各自的优缺点。

一、使用标准库函数qsort

C语言的标准库提供了qsort函数，它是一个通用的排序函数，可以对各种数据类型进行排序，只需要提供一个合适的比较函数即可。使用qsort函数进行字符串排序，不仅代码简洁，而且性能优越。以下是使用qsort排序字符串的详细步骤：

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

// 自定义的比较函数，用于qsort
int compare(const void *a, const void *b) {
    return strcmp(*(const char **)a, *(const char **)b);
}

int main() {
    // 定义字符串数组
    const char *arr[] = {"banana", "apple", "cherry", "mango", "grape"};
    int n = sizeof(arr) / sizeof(arr[0]);

    // 使用qsort进行排序
    qsort(arr, n, sizeof(const char *), compare);

    // 输出排序后的结果
    for (int i = 0; i < n; i++) {
        printf("%s\n", arr[i]);
    }
    return 0;
}

通过上述代码，我们定义了一个字符串数组，并使用qsort函数对其进行了排序。自定义的比较函数compare使用了strcmp函数来比较两个字符串的大小，从而实现排序功能。

二、实现自定义比较函数

在使用qsort函数进行排序时，比较函数是关键。我们可以根据实际需求，自定义比较函数，从而实现不同的排序效果。比较函数的签名应该与

int compare(const void *a, const void *b)

一致，返回值为负数表示a小于b，返回值为零表示a等于b，返回值为正数表示a大于b。

三、使用冒泡排序

冒泡排序是一种简单的排序算法，通过重复地遍历待排序的元素，并依次比较相邻的两个元素，如果它们的顺序错误就交换它们的位置。以下是使用冒泡排序对字符串进行排序的实现：

#include <stdio.h>
#include <string.h>

void bubbleSort(char *arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (strcmp(arr[j], arr[j+1]) > 0) {
                char *temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

int main() {
    char *arr[] = {"banana", "apple", "cherry", "mango", "grape"};
    int n = sizeof(arr) / sizeof(arr[0]);

    bubbleSort(arr, n);

    for (int i = 0; i < n; i++) {
        printf("%s\n", arr[i]);
    }
    return 0;
}

四、利用选择排序

选择排序是一种简单但效率相对较低的排序算法。它的基本思想是每次从未排序部分选择最小（或最大）的元素，放到已排序部分的末尾。以下是选择排序对字符串进行排序的实现：

#include <stdio.h>
#include <string.h>

void selectionSort(char *arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int minIndex = i;
        for (int j = i+1; j < n; j++) {
            if (strcmp(arr[j], arr[minIndex]) < 0) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            char *temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

int main() {
    char *arr[] = {"banana", "apple", "cherry", "mango", "grape"};
    int n = sizeof(arr) / sizeof(arr[0]);

    selectionSort(arr, n);

    for (int i = 0; i < n; i++) {
        printf("%s\n", arr[i]);
    }
    return 0;
}

五、实现快速排序

快速排序是一种高效的排序算法，通常优于冒泡排序和选择排序。它的基本思想是通过递归地将数组划分为两个子数组，使得每个子数组的元素都比另一个子数组的元素要小（或大）。以下是快速排序对字符串进行排序的实现：

#include <stdio.h>
#include <string.h>

void quickSort(char *arr[], int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

int partition(char *arr[], int low, int high) {
    char *pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (strcmp(arr[j], pivot) < 0) {
            i++;
            char *temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    char *temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

int main() {
    char *arr[] = {"banana", "apple", "cherry", "mango", "grape"};
    int n = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, n - 1);

    for (int i = 0; i < n; i++) {
        printf("%s\n", arr[i]);
    }
    return 0;
}