C 语言实现所有排序算法

冒泡排序（Bubble Sort）

原理

冒泡排序是一种简单的比较排序算法。它重复地走访要排序的数列，一次比较两个数据元素，如果顺序不对则进行交换，并一直重复这样的走访操作，直到没有要交换的数据元素为止。这个算法的名字由来是因为越小（或越大）的元素会经由交换慢慢“浮”到数列的顶端，就如同水中的气泡最终会上浮到水面一样，故而得名。

在每一轮比较中，最大（或最小）的元素会被移动到数组的末尾（或开头）。每一轮过后，需要比较的元素个数就会减少一个，因为已经确定了一个最大（或最小）的元素。

代码实现

#include <stdio.h>

// 交换两个整数
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 冒泡排序函数
void bubbleSort(int arr[], int n) {
    int i, j;
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
            }
        }
    }
}

// 打印数组
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("原始数组: ");
    printArray(arr, n);
    bubbleSort(arr, n);
    printf("排序后的数组: ");
    printArray(arr, n);
    return 0;
}

分析

1. 时间复杂度：在最坏和平均情况下，冒泡排序的时间复杂度为 (O(n^2))，其中 (n) 是数组的长度。这是因为它需要进行 (n - 1) 轮比较，每一轮比较的次数依次递减，总的比较次数约为 (n(n - 1)/2)。在最好情况下（数组已经有序），时间复杂度为 (O(n))，因为只需要进行一轮比较且没有交换操作。
2. 空间复杂度：冒泡排序是一种原地排序算法，除了存储原始数组和一些临时变量外，不需要额外的大量空间，空间复杂度为 (O(1))。

选择排序（Selection Sort）

原理

选择排序是一种简单直观的排序算法。它的工作原理是每一趟从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

具体过程是，在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

代码实现

#include <stdio.h>

// 交换两个整数
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 选择排序函数
void selectionSort(int arr[], int n) {
    int i, j, minIndex;
    for (i = 0; i < n - 1; i++) {
        minIndex = i;
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            swap(&arr[i], &arr[minIndex]);
        }
    }
}

// 打印数组
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("原始数组: ");
    printArray(arr, n);
    selectionSort(arr, n);
    printf("排序后的数组: ");
    printArray(arr, n);
    return 0;
}

分析

1. 时间复杂度：无论数组初始状态如何，选择排序都需要进行 (n(n - 1)/2) 次比较，所以它的时间复杂度在最坏、平均和最好情况下均为 (O(n^2))，其中 (n) 是数组的长度。
2. 空间复杂度：选择排序同样是原地排序算法，空间复杂度为 (O(1))，因为它只需要有限的额外空间来进行交换操作。

插入排序（Insertion Sort）

原理

插入排序是一种简单的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序在实现上，通常采用 in - place 排序（即只需用到 (O(1)) 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

代码实现

#include <stdio.h>

// 插入排序函数
void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

// 打印数组
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("原始数组: ");
    printArray(arr, n);
    insertionSort(arr, n);
    printf("排序后的数组: ");
    printArray(arr, n);
    return 0;
}

分析

1. 时间复杂度：在最坏情况下，即数组是逆序的，插入排序需要比较和移动 (n(n - 1)/2) 次，时间复杂度为 (O(n^2))。在平均情况下，时间复杂度也为 (O(n^2))。而在最好情况下，数组已经有序，只需要进行 (n - 1) 次比较，时间复杂度为 (O(n))。
2. 空间复杂度：插入排序是原地排序算法，空间复杂度为 (O(1))，因为它只需要几个临时变量来进行比较和移动操作。

希尔排序（Shell Sort）

原理

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序的基本思想是将数组按照一定的间隔（称为增量）分成若干个子序列，对每个子序列分别进行插入排序。随着增量逐渐减小，子序列的长度逐渐增加，当增量减为 1 时，整个数组被作为一个子序列进行插入排序，此时数组基本已经接近有序，插入排序的效率会大大提高。

代码实现

#include <stdio.h>

// 希尔排序函数
void shellSort(int arr[], int n) {
    int gap, i, j, temp;
    for (gap = n / 2; gap > 0; gap /= 2) {
        for (i = gap; i < n; i++) {
            temp = arr[i];
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

// 打印数组
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {12, 34, 54, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("原始数组: ");
    printArray(arr, n);
    shellSort(arr, n);
    printf("排序后的数组: ");
    printArray(arr, n);
    return 0;
}

分析

1. 时间复杂度：希尔排序的时间复杂度依赖于增量序列的选择。常见的增量序列有 Knuth 序列等。一般来说，希尔排序的时间复杂度在 (O(n^{1.3})) 到 (O(n^2)) 之间，比插入排序在大规模数据时效率更高。
2. 空间复杂度：希尔排序是原地排序算法，空间复杂度为 (O(1))，因为它只需要有限的额外空间来进行交换和临时存储。

归并排序（Merge Sort）

原理

归并排序是建立在归并操作上的一种有效、稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

归并排序的基本思想是将一个序列分成两个子序列，分别对这两个子序列进行排序，然后将排好序的子序列合并成一个最终的有序序列。这个过程是递归进行的，直到子序列长度为 1，此时子序列本身就是有序的。

代码实现

#include <stdio.h>

// 合并两个子数组
void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    // 创建临时数组
    int L[n1], R[n2];

    // 复制数据到临时数组 L[] 和 R[]
    for (i = 0; i < n1; i++) {
        L[i] = arr[l + i];
    }
    for (j = 0; j < n2; j++) {
        R[j] = arr[m + 1 + j];
    }

    // 合并临时数组回到 arr[l..r]
    i = 0; // 初始化第一个子数组的索引
    j = 0; // 初始化第二个子数组的索引
    k = l; // 初始化合并数组的索引
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // 复制 L[] 中剩余的元素
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // 复制 R[] 中剩余的元素
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// 归并排序函数
void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;

        // 递归地对左右子数组进行排序
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        // 合并两个子数组
        merge(arr, l, m, r);
    }
}

// 打印数组
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("原始数组: ");
    printArray(arr, n);
    mergeSort(arr, 0, n - 1);
    printf("排序后的数组: ");
    printArray(arr, n);
    return 0;
}

分析

1. 时间复杂度：归并排序的时间复杂度在最坏、平均和最好情况下均为 (O(n \log n))，其中 (n) 是数组的长度。这是因为每次递归将数组分成两部分，共需要 (\log n) 层递归，每层递归的合并操作需要 (O(n)) 的时间。
2. 空间复杂度：归并排序需要额外的空间来存储临时数组，空间复杂度为 (O(n))，因为在合并过程中需要创建与原数组长度相同的临时数组。

快速排序（Quick Sort）

原理

快速排序是一种高效的排序算法，采用了分治法的思想。它的基本思想是通过选择一个基准元素（pivot），将数组分为两部分，使得左边部分的元素都小于等于基准元素，右边部分的元素都大于等于基准元素。然后分别对左右两部分进行递归排序，最终将排序好的左右两部分和基准元素合并起来，得到一个有序的数组。

代码实现

#include <stdio.h>

// 交换两个整数
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 划分函数
int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j < high; 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 - 1);
        quickSort(arr, pi + 1, high);
    }
}

// 打印数组
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("原始数组: ");
    printArray(arr, n);
    quickSort(arr, 0, n - 1);
    printf("排序后的数组: ");
    printArray(arr, n);
    return 0;
}

分析

1. 时间复杂度：在平均情况下，快速排序的时间复杂度为 (O(n \log n))，因为每次划分都能将数组大致分成两等份，共需要 (\log n) 层递归，每层递归的划分操作需要 (O(n)) 的时间。在最坏情况下（例如每次选择的基准元素都是数组中的最大或最小元素），时间复杂度为 (O(n^2))。
2. 空间复杂度：快速排序的空间复杂度主要取决于递归调用的深度。在平均情况下，空间复杂度为 (O(\log n))，因为递归深度为 (\log n)。在最坏情况下，空间复杂度为 (O(n))，当每次划分都偏向一边时，递归深度为 (n)。

堆排序（Heap Sort）

原理

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

堆排序的基本步骤如下：

1. 把无序数组构建成一个堆，根据升序或降序需求选择大顶堆或小顶堆。
2. 把堆顶元素与堆尾元素交换，此时堆尾元素就是最大（或最小）元素。
3. 对剩余的 (n - 1) 个元素重新调整为堆，重复上述步骤，直到整个数组有序。

代码实现

#include <stdio.h>

// 调整堆
void heapify(int arr[], int n, int i) {
    int largest = i; // 初始化最大元素为根节点
    int left = 2 * i + 1; // 左子节点
    int right = 2 * i + 2; // 右子节点

    // 如果左子节点比根节点大
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    // 如果右子节点比最大元素大
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    // 如果最大元素不是根节点
    if (largest != i) {
        int swap = arr[i];
        arr[i] = arr[largest];
        arr[largest] = swap;

        // 递归地调整受影响的子树
        heapify(arr, n, largest);
    }
}

// 堆排序函数
void heapSort(int arr[], int n) {
    // 构建大顶堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // 一个个从堆顶取出元素
    for (int i = n - 1; i > 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // 调用 heapify 函数对剩余元素重新调整为堆
        heapify(arr, i, 0);
    }
}

// 打印数组
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("原始数组: ");
    printArray(arr, n);
    heapSort(arr, n);
    printf("排序后的数组: ");
    printArray(arr, n);
    return 0;
}

分析

1. 时间复杂度：堆排序的时间复杂度在最坏、平均和最好情况下均为 (O(n \log n))。构建堆的时间复杂度为 (O(n))，每次调整堆的时间复杂度为 (O(\log n))，一共需要调整 (n - 1) 次，所以总的时间复杂度为 (O(n \log n))。
2. 空间复杂度：堆排序是原地排序算法，空间复杂度为 (O(1))，因为它只需要有限的额外空间来进行交换操作。

计数排序（Counting Sort）

原理

计数排序是一种非比较排序算法，它适用于一定范围内的整数排序。其原理是通过统计每个整数在数组中出现的次数，然后根据统计结果将整数按顺序放回数组中，从而实现排序。

具体步骤如下：

1. 找出待排序数组中的最大值和最小值，确定计数数组的范围。
2. 初始化一个计数数组，其长度为最大值与最小值的差值加 1，用于统计每个整数出现的次数。
3. 遍历待排序数组，统计每个整数出现的次数并记录在计数数组中。
4. 对计数数组进行累加，得到每个整数在排序后数组中的最终位置。
5. 从后往前遍历待排序数组，根据计数数组中的位置信息将整数放回原数组中。

代码实现

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

// 计数排序函数
void countingSort(int arr[], int n, int max) {
    int *count = (int *)malloc((max + 1) * sizeof(int));
    int *output = (int *)malloc(n * sizeof(int));

    // 初始化计数数组
    for (int i = 0; i <= max; i++) {
        count[i] = 0;
    }

    // 统计每个元素出现的次数
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }

    // 对计数数组进行累加
    for (int i = 1; i <= max; i++) {
        count[i] += count[i - 1];
    }

    // 将元素放回原数组
    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    // 将排序后的结果复制回原数组
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }

    free(count);
    free(output);
}

// 打印数组
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int max = 8;
    printf("原始数组: ");
    printArray(arr, n);
    countingSort(arr, n, max);
    printf("排序后的数组: ");
    printArray(arr, n);
    return 0;
}

分析

1. 时间复杂度：计数排序的时间复杂度为 (O(n + k))，其中 (n) 是数组的长度，(k) 是数组中元素的取值范围。如果 (k) 与 (n) 同阶，那么时间复杂度可以近似看作 (O(n))。
2. 空间复杂度：计数排序需要额外的空间来存储计数数组和临时输出数组，空间复杂度为 (O(k + n))。当 (k) 远大于 (n) 时，空间复杂度主要由 (k) 决定。

桶排序（Bucket Sort）

原理

桶排序是一种分布式排序算法，它假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别进行排序（可以使用其他排序算法，如插入排序），最后将各个桶中的数据依次取出，得到有序序列。

具体步骤如下：

1. 确定桶的数量，通常根据数据范围和分布情况来决定。
2. 将数据分配到各个桶中。
3. 对每个桶内的数据进行排序。
4. 按顺序将各个桶中的数据收集起来，形成有序数组。

代码实现

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

// 插入排序函数，用于桶内排序
void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

// 桶排序函数
void bucketSort(float arr[], int n) {
    // 创建桶
    int bucket_num = 10;
    float **buckets = (float **)malloc(bucket_num * sizeof(float *));
    int *bucket_sizes = (int *)malloc(bucket_num * sizeof(int));

    // 初始化桶
    for (int i = 0; i < bucket_num; i++) {
        buckets[i] = (float *)malloc(n * sizeof(float));
        bucket_sizes[i] = 0;
    }

    // 分配数据到桶
    for (int i = 0; i < n; i++) {
        int bucket_index = (int)(arr[i] * bucket_num);
        buckets[bucket_index][bucket_sizes[bucket_index]++] = arr[i];
    }

    // 对每个桶进行排序
    for (int i = 0; i < bucket_num; i++) {
        insertionSort(buckets[i], bucket_sizes[i]);
    }

    // 收集数据
    int index = 0;
    for (int i = 0; i < bucket_num; i++) {
        for (int j = 0; j < bucket_sizes[i]; j++) {
            arr[index++] = buckets[i][j];
        }
        free(buckets[i]);
    }

    free(buckets);
    free(bucket_sizes);
}

// 打印数组
void printArray(float arr[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%.2f ", arr[i]);
    }
    printf("\n");
}

int main() {
    float arr[] = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("原始数组: ");
    printArray(arr, n);
    bucketSort(arr, n);
    printf("排序后的数组: ");
    printArray(arr, n);
    return 0;
}

分析

1. 时间复杂度：在平均情况下，桶排序的时间复杂度为 (O(n + k))，其中 (n) 是数组的长度，(k) 是桶的数量。如果数据分布均匀且桶的数量选择合适，桶内的数据量较少，排序时间可以忽略不计，此时时间复杂度接近 (O(n))。在最坏情况下，当所有数据都分配到一个桶中时，时间复杂度退化为 (O(n^2))，与插入排序的最坏情况相同。
2. 空间复杂度：桶排序需要额外的空间来存储桶和桶内的数据，空间复杂度为 (O(n + k))，其中 (n) 是原始数组的长度，(k) 是桶的数量。

基数排序（Radix Sort）

原理

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

基数排序有两种方法：

1. LSD（Least Significant Digit）：从最低有效位开始排序。
2. MSD（Most Significant Digit）：从最高有效位开始排序。

这里以 LSD 为例，具体步骤如下：

1. 找到数组中的最大数，确定其位数。
2. 从最低位到最高位，依次对数组进行排序，每次排序根据当前位的数字将数据分配到不同的桶中，然后按顺序收集桶中的数据。

代码实现

#include <stdio.h>

// 获取数组中的最大数
int getMax(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

// 计数排序，用于基数排序的每一步
void countingSort(int arr[], int n, int exp) {
    int output[n];
    int i, count[10] = {0};

    // 统计每个数字在当前位出现的次数
    for (i = 0; i < n; i++) {
        count[(arr[i] / exp) % 10]++;
    }

    // 计算每个数字在输出数组中的最终位置
    for (i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    // 构建输出数组
    for (i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    // 将输出数组复制回原数组
    for (i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

// 基数排序函数
void radixSort(int arr[], int n) {
    int max = getMax(arr, n);

    // 对每个数位进行计数排序
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSort(arr, n, exp);
    }
}

// 打印数组
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("原始数组: ");
    printArray(arr, n);
    radixSort(arr, n);
    printf("排序后的数组: ");
    printArray(arr, n);
    return 0;
}

分析

1. 时间复杂度：基数排序的时间复杂度为 (O(d(n + k)))，其中 (n) 是数组的长度，(d) 是数字的最大位数，(k) 是基数（对于十进制数，(k = 10)）。如果 (d) 和 (k) 相对 (n) 较小且稳定，基数排序的时间复杂度可以近似看作 (O(n))。
2. 空间复杂度：基数排序需要额外的空间来存储临时数组和计数数组，空间复杂度为 (O(n + k))，其中 (n) 是原始数组的长度，(k) 是基数。

通过以上对各种排序算法在 C 语言中的实现及分析，开发者可以根据不同的应用场景和数据特点选择合适的排序算法，以达到最优的性能和效率。