C语言完整实现12种排序算法(小结)

本文主要介绍了C语言实现12种排序算法的详细过程以及相关示例。

排序算法的分类

排序算法可分为内部排序和外部排序。内部排序是指将待排序的数据全部加载到内存中进行排序，而外部排序是指在数据量过大时需要将数据分块，对每一块数据进行排序，最后将各个块合并起来，得到有序的结果。

在内部排序中，常用的排序算法大致可分为以下几类：

冒泡排序

冒泡排序是一种简单的排序算法，它重复地走访过要排序的元素，一次比较两个元素，如果它们的顺序错误就把它们交换过来。时间复杂度为 $O(n^2)$。

选择排序

选择排序是一种简单的排序算法，它每次从待排序的数据中选出最小（或最大）的元素，放在已排序的数据的末尾。时间复杂度为 $O(n^2)$。

插入排序

插入排序是一种简单直观的排序算法，它将待排序的数据分为已排序和未排序两个部分，每次从未排序的部分中取出一个元素，插入到已排序的部分中，时间复杂度为 $O(n^2)$。

希尔排序

希尔排序是一种插入排序的优化算法，它通过间隔不断缩小的方式，对待排序的数据进行多次插入排序。时间复杂度为 $O(n^{\frac{3}{2}})$。

归并排序

归并排序是一种使用分治思想的排序算法，它将待排序的序列划分成两个子序列，对每个子序列进行递归排序，最后将两个已排序的子序列合并成一个有序的序列。时间复杂度为 $O(n\log_2 n)$。

快速排序

快速排序也是一种使用分治思想的排序算法，它将待排序的序列划分成两个子序列，以基准元素为标准将序列分为小于基准元素和大于基准元素两部分，递归地对两个子序列进行快速排序。时间复杂度为 $O(n\log_2 n)$。

堆排序

堆排序是一种利用堆这种数据结构设计的排序算法，它首先将待排序的数据看成一个完全二叉树（堆），然后将该堆调整为最大堆或最小堆，再依次取出堆顶元素进行排序。时间复杂度为 $O(n \log_2 n)$。

基数排序

基数排序是一种非比较型的排序算法，它将待排序的元素拆分成若干个数字位，利用每一位的值进行排序，并依次进行桶排序。时间复杂度为 $O(nk)$，其中 $k$ 表示数字的位数。

示例说明

示例1

下面是冒泡排序的代码示例：

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

对于数组 arr，调用 bubble_sort(arr, len) 就可以进行冒泡排序。假设 arr 为 {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}，则排序后的结果为 {1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9}。

示例2

下面是归并排序的代码示例：

void merge(int arr[], int left, int mid, int right, int temp[]) {
    int i = left, j = mid+1, k = 0;
    while (i <= mid && j <=right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    for (i = 0; i < k; i++) {
        arr[left+i] = temp[i];
    }
}

void merge_sort(int arr[], int left, int right, int temp[]) {
    if (left < right) {
        int mid = (left + right) / 2;
        merge_sort(arr, left, mid, temp);
        merge_sort(arr, mid+1, right, temp);
        merge(arr, left, mid, right, temp);
    }
}

void merge_sort(int arr[], int len) {
    int *temp = (int*)malloc(len*sizeof(int));
    merge_sort(arr, 0, len-1, temp);
    free(temp);
}

对于数组 arr，调用 merge_sort(arr, len) 就可以进行归并排序。假设 arr 为 {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}，则排序后的结果为 {1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9}。