当前位置: 首页 > article >正文

桶排序(代码+注释)

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

// 定义桶的结构
typedef struct Bucket {
    int* data;   // 动态数组
    int count;   // 当前存储的元素个数
    int capacity; // 桶的容量
} Bucket;

// 初始化桶
void InitBucket(Bucket* bucket) {
    bucket->capacity = 10; // 初始容量
    bucket->data = (int*)malloc(bucket->capacity * sizeof(int));
    bucket->count = 0;
}

// 向桶中添加元素
void AddToBucket(Bucket* bucket, int value) {
    if (bucket->count == bucket->capacity) {
        bucket->capacity *= 2;
        bucket->data = (int*)realloc(bucket->data, bucket->capacity * sizeof(int));
    }
    bucket->data[bucket->count++] = value;
}

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

// 桶排序函数
void BucketSort(int* arr, int n) {
    if (n <= 1) return;

    // 找到数组中的最大值和最小值
    int min = arr[0], max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] < min) min = arr[i];
        if (arr[i] > max) max = arr[i];
    }

    int bucketCount = 10; // 默认分成10个桶
    int range = max - min + 1;
    int bucketRange = range / bucketCount + 1;

    // 初始化桶数组
    Bucket* buckets = (Bucket*)malloc(bucketCount * sizeof(Bucket));
    for (int i = 0; i < bucketCount; i++) {
        InitBucket(&buckets[i]);
    }

    // 将数据分配到桶中
    for (int i = 0; i < n; i++) {
        int bucketIndex = (arr[i] - min) / bucketRange;
        AddToBucket(&buckets[bucketIndex], arr[i]);
    }

    // 对每个桶中的数据排序并合并结果
    int index = 0;
    for (int i = 0; i < bucketCount; i++) {
        if (buckets[i].count > 0) {
            InsertionSort(buckets[i].data, buckets[i].count);
            for (int j = 0; j < buckets[i].count; j++) {
                arr[index++] = buckets[i].data[j];
            }
        }
        free(buckets[i].data);
    }

    // 释放桶数组
    free(buckets);
}

// 测试函数
int main() {
    int arr[] = {42, 32, 33, 52, 37, 47, 51, 30};
    int n = sizeof(arr) / sizeof(arr[0]);

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

    BucketSort(arr, n);

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

    return 0;
}

测试结果

详细可见排序学习整理(3)-CSDN博客 


http://www.kler.cn/a/419104.html

相关文章:

  • 分享一款 Vue 图片编辑插件 (推荐)
  • 构建现代Web应用:FastAPI、SQLModel、Vue 3与Axios的结合使用
  • Linux设置开启启动脚本
  • 在RockyLinux9.4上安装Microk8s
  • Java学习,数据结构
  • 探索HarmonyOS:一键掌握Router与NavPathStatck的传参和页面回调技巧
  • webUI自动化(十)iframe切换
  • 【docker集群应用】Docker数据管理与镜像创建
  • Flutter:encrypt插件 AES加密处理
  • 10.请求拦截和响应拦截
  • Rust代写 OCaml代做 Go R语言 SML Haskell Prolog DrRacket Lisp
  • Jackson库--ObjecMapper
  • vue3 与 spring-boot 完成跨域访问
  • Maven java 项目,想执行verify阶段指令,通常需要配置哪些插件呢?
  • YOLOv8-ultralytics-8.2.103部分代码阅读笔记-ops.py
  • Java知识及热点面试题总结(二)
  • 远程桌面协助控制软件 RustDesk v1.3.3 多语言中文版
  • 精准用户获取与私域流量运营:多商户链动 2+1 模式商城小程序的赋能策略
  • Linux内核编译流程(Ubuntu24.04+Linux Kernel 6.8.12)
  • spring boot 调用C#封装的DLL文件中的函数
  • 力扣3372.连接两棵树后最大目标节点数目I
  • 内网使用docker搭建librespeed测速网站
  • 挑战用React封装100个组件【004】
  • UaGateway:实现OPC DA和OPC UA的高效转换
  • FFmpeg一些常用的命令
  • ElasticSearch的学习