【C语言】常见的数据排序算法

目录

一、概述

二、常见的排序算法

2.1 冒泡排序

2.1.1 定义

2.1.2 C语言实现

2.2 快速排序

2.2.1 定义

2.2.2 C语言实现

2.3 插入排序

2.3.1 定义

2.3.2 C语言实现

2.4 希尔排序

2.4.1 定义

2.4.2 C语言实现

2.5 归并排序

2.5.1 定义

2.5.2 C语言实现

2.6 基数排序

2.6.1 定义

2.6.2 C语言实现

三、排序算法的空间、时间复杂度、稳定性

---

一、概述

        排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。

二、常见的排序算法

2.1 冒泡排序

2.1.1 定义

       冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。重复进行直到没有再需要交换的元素，这意味着数列已经排序完成。

2.1.2 C语言实现

        这段代码首先定义了一个冒泡排序函数bubble_sort，它接受一个整型数组和数组的长度作为参数。然后定义了两个辅助函数print_array用于打印数组和main函数作为程序的入口。在main函数中，我们首先打印原始数组，然后调用冒泡排序函数进行排序，并再次打印排序后的数组。

#include <stdio.h>
 
void bubble_sort(int arr[], int len) {
    int i, j, temp;
    for (i = 0; i < len - 1; i++)
        for (j = 0; j < len - 1 - i; j++)
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
}
 
void print_array(int arr[], int len) {
    int i;
    for (i = 0; i < len; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
 
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int len = (int) sizeof(arr) / sizeof(*arr);
 
    printf("Original array: ");
    print_array(arr, len);
 
    bubble_sort(arr, len);
 
    printf("Sorted array: ");
    print_array(arr, len);
 
    return 0;
}

2.2 快速排序

2.2.1 定义

        快速排序作为多种排序方法中效率最高的一种，其底层原理被广泛运用，他的核心思想与二叉树结构中的递归逻辑相似，首先标记一个元素作为基准点，然后利用该基准点把数组分成左右两个区间，并且使小于该基准点的元素放在左区间，大于该基准点的元素放在右区间，如此反复递归，直到数组为一个有序数组。

2.2.2 C语言实现

        这段代码首先定义了一个辅助函数swap用于交换数组中的元素。然后定义了partition函数来选择一个基准点并重新排列数组，使得比基准点小的元素都在它的左侧，比基准点大的元素都在它的右侧。最后，quickSort函数递归地对数组的左右部分进行排序。printArray函数用于打印排序后的数组。在main函数中，我们定义了一个数组并对它进行排序，然后打印排序结果。

#include <stdio.h>
 
void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}
 
int partition (int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
 
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}
 
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
 
        quickSort(arr, low, pi