数据结构 Sort

数据结构与算法回顾（八）：海量整数排序的分治式解决思路（未完待续）

一道 pingcap 的算法题目

Posted by pandaychen on May 28, 2022

0x00 前言

问题：实现一个 16M 大小的整数 int64 的数组排序，如何实现？采用多路归并方式实现

0x01 多路归并排序

先简单回顾下，多路归并排序（Multi-way merge sort）是归并排序的一种扩展，它可以同时合并多个有序数组。归并排序的基本思想是将两个有序数组合并成一个有序数组，而多路归并排序是将 k 个有序数组合并成一个有序数组。多路归并排序在处理大规模数据时，可以显著减少磁盘 I/O 次数，提高排序效率。多路归并排序的基本步骤如下：

  1. 将待排序的数据分为 k 个有序数组
  2. 将 k 个有序数组两两合并，得到 k/2 个有序数组。重复这个过程，直到剩下一个有序数组
  3. 输出合并后的有序数组

多路归并排序的时间复杂度为 O(nlogk)，其中 n 是待排序数据的总数，k 是归并的路数。当 k=2 时，多路归并排序就是普通的归并排序。多路归并排序的实现可以使用优先队列（如 MinHeap）来选择每次合并的最小元素，从而提高合并的效率。具体步骤如下：

  1. 建立一个大小为 k 的最小堆，将 k 个有序数组的首元素插入到堆中
  2. 每次从堆中取出最小元素，将其添加到合并后的数组中
  3. 将被取出元素所在数组的下一个元素插入堆中。如果该数组已经没有元素，就跳过这一步
  4. 重复步骤 2 和 3，直到堆为空

解决思路

将待排序数组分成多个组，利用多个 goroutine 实现各个组的并行排序；然后通过 Heap(最小堆) 进行多路归并排序；

0x03 参考

CATALOG
    FEATURED TAGS
    Latex gRPC 负载均衡 OpenSSH Authentication Consul Etcd Kubernetes 性能优化 Python 分布式锁 WebConsole 后台开发 Golang OpenSource Nginx Vault 网络安全 Perl 分布式理论 Raft 正则表达式 Redis 分布式 限流 go-redis 微服务 反向代理 ReverseProxy Cache 缓存 连接池 OpenTracing GOMAXPROCS GoMicro 微服务框架 日志 Pool Kratos Hystrix 熔断 并发 Pipeline 证书 Prometheus Metrics Breaker 定时器 Timer Timeout Kafka Xorm MySQL Fasthttp bytebufferpool 任务队列 队列 异步队列 GOIM Pprof errgroup consistent-hash Zinx 网络框架 设计模式 HTTP Gateway Queue Docker 网关 Statefulset NFS Machinery Teleport Zero Trust Oxy 存储 Confd 热更新 OAuth SAML OpenID Openssl AES 微服务网关 IM KMS 安全 数据结构 hashtable Sort Asynq 基数树 Radix Crontab 热重启 系统编程 sarama Go-Zero RDP VNC 协程池 UDP hashmap 网络编程 自适应技术 环形队列 Ring Buffer Circular Buffer InnoDB timewheel GroupCache Jaeger GOSSIP CAP Bash websocket 事务 GC TLS singleflight 闭包 Helm kubernetes network iptables MITM HTTPS tap tun 路由 wireguard Tun gvisor Git NAT 协议栈 Envoy FRP DPI gopacket DNS GoZero Gost
    FRIENDS