一、引言
字符串排序是计算机编程中常见的问题之一。在C语言中，可以使用不同的算法和数据结构来实现字符串的排序。本篇文章将介绍如何使用C语言实现字符串的排序，并给出相应的代码示例。
二、字符串排序算法
- 冒泡排序
冒泡排序是一种简单的排序算法，它重复地遍历待排序的字符串，比较相邻的两个字符，如果它们的顺序错误就交换它们，直到没有需要交换的字符为止。
- 选择排序
选择排序也是一种简单直观的排序算法。它的工作原理是每一次从待排序的字符串中选择最小（或最大）的一个字符，存放在序列的起始位置，直到全部待排序的字符排完。
- 插入排序
插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
- 快速排序
快速排序采用分治法策略，通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序，整个过程可以递归进行，以此达到整个数据变成有序序列。
三、代码实现
以下是使用C语言实现上述四种字符串排序算法的代码示例：
- 冒泡排序
#include <stdio.h> #include <string.h> void bubbleSort(char arr[][50], int n) { int i, j; char temp[50]; for (i = 0; i < n-1; i++) { for (j = 0; j < n-i-1; j++) { if (strcmp(arr[j], arr[j+1]) > 0) { strcpy(temp, arr[j]); strcpy(arr[j], arr[j+1]); strcpy(arr[j+1], temp); } } } } int main() { char arr[5][50] = {"C", "A", "B", "D", "E"}; int n = sizeof(arr)/sizeof(arr[0]); bubbleSort(arr, n); printf("Sorted array: \n"); for (int i=0; i<n; i++) { printf("%s ", arr[i]); } return 0; }
- 选择排序
#include <stdio.h> #include <string.h> void selectionSort(char arr[][50], int n) { int i, j, min_idx; char temp[50]; for (i = 0; i < n-1; i++) { min_idx = i; for (j = i+1; j < n; j++) { if (strcmp(arr[j], arr[min_idx]) < 0) { min_idx = j; } } strcpy(temp, arr[min_idx]); strcpy(arr[min_idx], arr[i]); strcpy(arr[i], temp); } } int main() { char arr[5][50] = {"C", "A", "B", "D", "E"}; int n = sizeof(arr)/sizeof(arr[0]); selectionSort(arr, n); printf("Sorted array: \n"); for (int i=0; i<n; i++) { printf("%s ", arr[i]); } return 0; }
- 插入排序
#include <stdio.h> #include <string.h> void insertionSort(char arr[][50], int n) { int i, key, j; char temp[50]; for (i = 1; i < n; i++) { key = strcmp(arr[i], arr[i-1]); j = i - 1; while (j >= 0 && strcmp(arr[j], arr[j+1]) > key) { strcpy(temp, arr[j]); strcpy(arr[j], arr[j+1]); strcpy(arr[j+1], temp); j = j - 1; } } } int main() { char arr[5][50] = {"C", "A", "B", "D", "E"}; int n = sizeof(arr)/sizeof(arr[0]); insertionSort(arr, n); printf("Sorted array: \n"); for (int i=0; i<n; i++) { printf("%s ", arr[i]); } return 0; }
- 快速排序
#include <stdio.h> #include <string.h> void swap(char *a, char *b) { char temp[50]; strcpy(temp, a); strcpy(a, b); strcpy(b, temp); } char* partition (char arr[][50], int low, int high) { char pivot = arr[high][0]; // pivot element on the last row char i = (low - 1); // Index of smaller element found so far for (int j = low; j <= high- 1; j++) { if (strcmp(arr[j], pivot) < 0) { // If current element is smaller than pivot i++; // increment index of smaller element found so far swap(&arr[i][0], &arr[j][0]); // swap current element with the index of smaller element found so far } } swap(&arr[i + 1][0], &arr[high][0]); // At the end of this loop, swap the pivot element to its correct position return &arr[i + 1][0]; // return the pointer to the first element of the pivot's new position } void quickSort(char arr[][50], int low, int high) { if (low < high) { // If the subarray has more than one element char *pi = partition(arr, low, high); // Partition the subarray into two subarrays. One containing elements smaller than the pivot and the other containing elements greater than the pivot. quickSort(arr, low, pi - 1); // Sort the subarray on the left side of the pivot quickSort(arr, pi + 1, high); // Sort the subarray on the right side of the pivot } } int main() { // Driver program to test above functions char arr[5][50] = {"C", "A", "B", "D", "E"}; // Test data int n = sizeof(arr)/sizeof(arr[0]); // Number of elements in the array quickSort(arr, 0, n - 1); // Sort the array using quickSort() function printf("Sorted array: \n"); // Print the sorted array for (int i=0; i<n; i++) { // Print each element of array after sorting it using %s format specifier and its index (%d) as prefix. printf("%d %s\n", i, arr[i]); } return 0; }
