【数据结构】归并排序、基数排序算法的学习知识点总结

 目录

1、归并排序

        1.1 算法思想

        1.2 代码实现

        1.3 例题分析

2、基数排序

        2.1 算法思想

        2.2 代码实现

        2.3 例题分析

---

1、归并排序

1.1 算法思想

        归并排序是一种采用分治思想的经典排序算法，通过将待排序数组分成若干个子序列，将每个子序列排序，最终合并成一个有序序列。其基本思路可以归纳为以下三个步骤：

1. 分治：将待排序数组递归地分成两个子序列，直到每个子序列中只有一个元素；
2. 合并：将两个有序子序列合并成一个有序序列，直到合并成一个完整的有序序列；
3. 递归：重复以上两个步骤，直到排序完成。

        具体实现过程中，可以采取自上而下或自下而上的方式进行归并排序。其中，自下而上的归并排序首先将整个数组划分成若干个大小为1的子数组，然后将相邻两个子数组合并成一个有序数组，逐渐扩大有序数组的长度，直到整个数组有序。

        归并排序算法的时间复杂度为 O(nlogn)，具有稳定性，适用于对大规模数据进行排序。

1.2 代码实现

归并排序（Merge Sort）是一种分治思想的排序算法，它的核心思想是将待排序的序列分成若干子序列，分别排序，然后合并。

C语言实现归并排序的代码如下：

#include <stdio.h>
#include <stdlib.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];

    // 将数据复制到左右子数组中
    for (i = 0; i < n1; i++) {
        L[i] = arr[l + i];
    }
    for (j = 0; j < n2; j++) {
        R[j] = arr[m + 1 + j];
    }

    // 将左右子数组合并到 arr 中
    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++;
    }

    // 处理剩余元素
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    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);
    }
}

int main() {
    int arr[] = {5, 1, 4, 2, 8, 0, 2};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    // 执行归并排序
    mergeSort(arr, 0, n - 1);

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

    return 0;
}

        在这段代码中，merge() 函数用于合并左右子数组，mergeSort() 函数用于对左右子数组进行排序并合并。在 main() 函数中，我们创建了一个待排序的整数数组，然后调用 mergeSort() 函数对其进行排序，并输出排序后的结果。

1.3 例题分析

假设我们有一个无序数组[10, 5, 2, 7, 6, 4, 3, 8, 9, 1]，要使用归并排序对其进行排序。下面是具体步骤：

1. 首先将数组不断分成两半，直到每个子数组只有一个元素为止。

[10, 5, 2, 7, 6, 4, 3, 8, 9, 1] -> [10, 5, 2, 7, 6] [4, 3, 8, 9, 1] -> [10, 5] [2, 7, 6] [4, 3] [8, 9, 1] -> [10] [5] [2] [7] [6] [4] [3] [8] [9] [1]

2. 接着，将相邻的两个子数组合并，并按顺序排序。

[10] [5] -> [5, 10]
[2] [7] [6] -> [2, 6, 7]
[4] [3] -> [3, 4]
[8] [9] [1] -> [1, 8, 9]

3. 重复步骤2，直到最终将所有子数组合并成为一个有序数组。

[5, 10] [2, 6, 7] [3, 4] [1, 8, 9] -> [2, 3, 4, 5, 6, 7, 8, 9, 10]

4. 最终得到的有序数组为[2, 3, 4, 5, 6, 7, 8, 9, 10]。可以看出，归并排序的时间复杂度为O(nlogn)，且不会破坏原有数组的顺序。

2、基数排序

2.1 算法思想

基数排序是一种非比较排序算法，根据关键字的每一位来排序，最终得到有序序列。其基本思想是将待排序的元素按照其每一位的值，将其分配到对应的桶中，然后按照桶的顺序依次取出元素，即可得到有序序列。

具体实现步骤如下：

1. 将所有待排序数按照个位数的值依次放入相应的桶中。

2. 按照桶的顺序依次取出每个桶中的元素，将其按照一位数的大小依次放回原数组中。

3. 对于十位数、百位数等同理，直到最高位数。

4. 最终得到有序序列。

                需要注意的是，基数排序算法的空间复杂度较高，需要额外的空间来存储桶和中间结果。在实际应用中，需要权衡算法的时间复杂度和空间复杂度，选择合适的算法。

2.2 代码实现

以下是一个基数排序的实现，它将一组数字按位数从低到高排序，每次排序都利用计数排序算法进行。

#include <iostream>
#include <vector>

using namespace std;

// 计数排序算法，用于将整数数组按某一位进行排序
void countingSort(vector<int>& arr, int exp)
{
    vector<int> output(arr.size());
    vector<int> count(10, 0);

    // 统计每个数字出现的次数
    for (int i = 0; i < arr.size(); i++)
        count[(arr[i] / exp) % 10]++;

    // 累加计数数组，求出每个数字在排序后的数组中的位置
    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];

    // 根据计数数组中的位置，将数字放置到排序后的数组中
    for (int i = arr.size() - 1; i >= 0; i--)
    {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    // 将排序后的数组复制到原始数组中
    for (int i = 0; i < arr.size(); i++)
        arr[i] = output[i];
}

// 基数排序算法
void radixSort(vector<int>& arr)
{
    int max = *max_element(arr.begin(), arr.end());

    // 从低位到高位依次进行排序
    for (int exp = 1; max / exp > 0; exp *= 10)
        countingSort(arr, exp);
}

int main()
{
    vector<int> arr = { 170, 45, 75, 90, 802, 24, 2, 66 };
    radixSort(arr);

    for (int i = 0; i < arr.size(); i++)
        cout << arr[i] << " ";

    return 0;
}

2.3 例题分析

        基数排序是一种非比较排序算法，其基本思想是将待排序的数据按照位数划分为不同的数字位，然后依次对每一位进行排序。

        例如，对于一个无序数组[753, 584, 626, 901, 321]，经过一轮排序后，按照个位数字的大小，可以得到以下排列：[901, 321, 753, 584, 626]，此时数组已经按照个位数字排好序了。

        接下来，我们再按照十位数字的大小对这个序列进行排序，排完之后得到的序列为：[321, 584, 626, 901, 753]。

        最后，再按照百位数字的大小进行排序就可以得到最终的有序数组：[321, 584, 626, 753, 901]。

        基数排序的时间复杂度是O(d*(n+k))，其中d为位数，n为元素个数，k为数字范围。因此，当数字范围较小且位数不多时，基数排序的效率较高，但如果数字范围很大或者位数较多时，基数排序的效率就会下降。