使用C语言实现字符串排序

简介: 使用C语言实现字符串排序

一、引言

字符串排序是计算机编程中常见的问题之一。在C语言中,可以使用不同的算法和数据结构来实现字符串的排序。本篇文章将介绍如何使用C语言实现字符串的排序,并给出相应的代码示例。

二、字符串排序算法

  1. 冒泡排序

冒泡排序是一种简单的排序算法,它重复地遍历待排序的字符串,比较相邻的两个字符,如果它们的顺序错误就交换它们,直到没有需要交换的字符为止。

  1. 选择排序

选择排序也是一种简单直观的排序算法。它的工作原理是每一次从待排序的字符串中选择最小(或最大)的一个字符,存放在序列的起始位置,直到全部待排序的字符排完。

  1. 插入排序

插入排序的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

  1. 快速排序

快速排序采用分治法策略,通过一趟排序将待排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分的所有数据要小,然后再按此方法对这两部分数据分别进行快速排序,整个过程可以递归进行,以此达到整个数据变成有序序列。

三、代码实现

以下是使用C语言实现上述四种字符串排序算法的代码示例:

  1. 冒泡排序
#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;
}
  1. 选择排序
#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;
}
  1. 插入排序
#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;
}
  1. 快速排序
#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; 
}
相关文章
|
29天前
|
安全 程序员 C语言
探索C语言库函数:字符串拷贝函数strcpy
探索C语言库函数:字符串拷贝函数strcpy
19 0
C4.
|
1月前
|
存储 程序员 C语言
C语言中如何通过指针引用字符串
C语言中如何通过指针引用字符串
C4.
14 0
|
1月前
|
存储 编译器 C语言
在C语言中的数组和字符串
在C语言中的数组和字符串
|
1月前
|
存储 Serverless C语言
C语言字符串长度居然可以这样轻松掌握,后悔现在才知道!
C语言字符串长度居然可以这样轻松掌握,后悔现在才知道!
|
1月前
|
存储 C语言
【绝绝子】C语言字符串拷贝,小白必看的科普教程!
【绝绝子】C语言字符串拷贝,小白必看的科普教程!
|
16天前
|
存储 C语言
【我爱C语言】详解字符函数isdigit和字符串转换函数(atoi和snprintf实现互相转换字符串)&&三种strlen模拟实现1
【我爱C语言】详解字符函数isdigit和字符串转换函数(atoi和snprintf实现互相转换字符串)&&三种strlen模拟实现
|
16天前
|
C语言
【C语言】第三回 关于字符串,语句和注释的使用2
【C语言】第三回 关于字符串,语句和注释的使用
|
21天前
|
搜索推荐 算法 编译器
【C语言】qsort()函数详解:能给万物排序的神奇函数
【C语言】qsort()函数详解:能给万物排序的神奇函数
41 0
|
29天前
|
安全 程序员 C语言
探索C语言库函数:字符串拷贝函数strcpy()
探索C语言库函数:字符串拷贝函数strcpy()
9 0
|
29天前
|
存储 C语言
C语言字符串
C语言字符串
18 0
C语言字符串