C语言中数组排序浅析

前言

在C语言中，数组排序是一项非常基础且实用的技能。它可以帮助我们将一个未排序的数组变为有序的，这样方便我们进行各种操作，比如查找、去重、统计频率等等。在本文中，我们将浅析C语言中数组排序的几种方法以及它们的优缺点。

冒泡排序

冒泡排序是一种比较简单易懂的排序方法，在很多初学者的教程中都有涉及。该算法的基本思想是将相邻的元素比较，如果第一个比第二个大，则交换它们的位置，一次遍历之后，最大的元素就被排到了数组的末尾。这个过程就像一颗气泡从数组底部一直浮到了数组顶部，因此得名。

以下是C语言中冒泡排序的代码示例：

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;
            }
        }
    }
}

该函数接受两个参数，第一个参数是待排序的数组，第二个参数是该数组的长度。在函数中，我们使用两个嵌套的循环来实现排序，外层循环负责遍历整个数组，内层循环负责比较相邻的元素并交换它们的位置。在一次遍历结束后，最大的元素就被交换到了数组末尾，因此在下一次遍历中，我们只需比较前 len-i 个元素即可。

冒泡排序的时间复杂度为 O(n^2)，因此对于大规模数据的排序效率不高，但它可以轻松处理小规模数据的排序。

下面是冒泡排序的演示过程，我们以一组随机生成的数组为例：

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

void bubble_sort(int arr[], int len);

int main() {
    int arr[10], i;

    srand((unsigned int) time(NULL));
    printf("Original Array:\n");
    for (i = 0; i < 10; i++) {
        arr[i] = rand() % 100;
        printf("%d ", arr[i]);
    }

    bubble_sort(arr, 10);

    printf("\nSorted Array:\n");
    for (i = 0; i < 10; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}

运行结果：

Original Array:
80 91 44 44 89 5 44 39 11 9 
Sorted Array:
5 9 11 39 44 44 44 80 89 91 

快速排序

快速排序是一种效率很高的排序方法，它的核心思想是分治思想，将待排序的数组分为两个子序列，然后递归地对子序列进行排序。在分割过程中，通过选定一个分割元素，将序列分割成两个子序列，其中一部分元素都要比分割元素小，另一部分元素都要比分割元素大。对于每个子序列，重复执行这个过程，直到整个序列都被排序完成。

以下是C语言中快速排序的代码示例：

void quick_sort(int arr[], int left, int right) {
    int i, j, temp, pivot;
    if (left >= right) {
        return;
    }
    i = left;
    j = right;
    pivot = arr[left];
    while (i < j) {
        while (i < j && arr[j] >= pivot) {
            j--;
        }
        while (i < j && arr[i] <= pivot) {
            i++;
        }
        if (i < j) {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    arr[left] = arr[i];
    arr[i] = pivot;
    quick_sort(arr, left, i - 1);
    quick_sort(arr, i + 1, right);
}

该函数接受三个参数，第一个参数是待排序的数组，第二个参数是该数组的左端点下标，第三个参数是该数组的右端点下标。在函数中，我们选定左端点的元素作为分割元素，然后使用两个指针 i 和 j 分别指向数组的左端点和右端点，开始在数组中找到一个分割点，使得 i 左侧的元素都比该分割点小，j 右侧的元素都比该分割点大。在找到这个分割点之后，我们将其与左端点的元素进行交换，并递归排序该分割点左侧和右侧的数组。

快速排序的时间复杂度为 O(nlogn)，在大规模数据的排序任务中表现优秀，但它不保证最坏情况的时间复杂度，因此在某些场景下可能会表现较差。

下面是快速排序的演示过程，我们以一组随机生成的数组为例：

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

void quick_sort(int arr[], int left, int right);

int main() {
    int arr[10], i;

    srand((unsigned int) time(NULL));
    printf("Original Array:\n");
    for (i = 0; i < 10; i++) {
        arr[i] = rand() % 100;
        printf("%d ", arr[i]);
    }

    quick_sort(arr, 0, 9);

    printf("\nSorted Array:\n");
    for (i = 0; i < 10; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}

运行结果：

Original Array:
37 25 84 17 95 87 30 86 15 39 
Sorted Array:
15 17 25 30 37 39 84 86 87 95 

总结

本文简要介绍了C语言中的冒泡排序和快速排序两种排序方法，并给出了相应的示例代码以及排序演示过程。在实现数组排序时，需要考虑到数据规模的大小以及性能要求，选择最适合的排序算法有助于提高代码效率、提高开发效率，并且对程序的性能优化很有帮助。最后，希望读者能够在实践中掌握排序算法的实现方法，熟练应用到实际开发中。