桶、冒泡

whl666666 · 2025-03-06 23:11:58 · 学习·文化课

桶、冒泡、选择、插入、快速（排序算法）

1.桶

桶是什么？

桶排序是计数排序的升级版，也是分治算法。
它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。
桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序
（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
简言之，将值为i的元素放入i号桶，最后依次把桶里的元素倒出来。

桶模板代码

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

// 桶排序函数
void bucketSort(int arr[], int n) {
    // 创建桶数组
    int maxVal = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > maxVal) {
            maxVal = arr[i];
        }
    }
    int bucket[maxVal + 1];
    for (int i = 0; i <= maxVal; i++) {
        bucket[i] = 0;
    }

    // 将元素放入桶中
    for (int i = 0; i < n; i++) {
        bucket[arr[i]]++;
    }

    // 从桶中取出元素并排序
    int index = 0;
    for (int i = 0; i <= maxVal; i++) {
        while (bucket[i] > 0) {
            arr[index++] = i;
            bucket[i]--;
        }
    }
}

// 测试桶排序
int main() {
    int arr[] = {5, 2, 8, 4, 9, 1, 3, 7, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    bucketSort(arr, n);

    printf("排序后数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

2.冒泡

基本思想: 冒泡排序，类似于水中冒泡，较大的数沉下去，较小的数慢慢冒起来，假设从小到大，即为较大的数慢慢往后排，较小的数慢慢往前排。

冒泡模板代码

// 交换宏
#define swap(x,y) x=x+y,y=x-y,x=x-y

void bubbleSort(int arr[], int n)
{
    bool bExchange = false; // 交换标志

    for (int i = 0; i < n - 1; i++) // 最多做n-1趟排序 
    {
        bExchange = false;
        for (int j = 0; j < n - 1 - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                swap(arr[j + 1], arr[j]);
                bExchange = true; // 发生了交换，故将交换标志置为真
            }
        }

        if (!bExchange) // 考虑有一趟排序未发生交换的理想情况，可以提前终止算法
            return;
    }
}

——本笔记创建于2025/3/6