在本文中，我们将讨论两种类型的 基数排序：
在本文中，我们的任务是探讨 MSD 基数排序并将其与 LSD 基数排序进行比较。
方法： 其核心思想是对每一位 i 执行以下步骤，其中 i 的值从最高有效位变化到最低有效位：
- 根据元素的第 i 位将其存储在不同的桶中。
- 递归地对包含多个元素的每个桶进行排序。
最高有效位 vs 最低有效位 基数排序：
- 对于排序固定长度的整数，MSD 比 LSD 更高效，因为它可能不需要检查每个整数的每一位：
LSD 基数排序：
> !image
MSD 基数排序：
> !imageMSD 基数排序
- 与 LSD 不同，MSD 可用于排序变长字符串。LSD 必须是稳定的才能正常工作，但 MSD 可以是稳定的也可以是不稳定的，并且 MSD 可以处理随机字符串。
!imageMSD 基数排序变长字符串
- 时间复杂度：
- LSD 基数排序： 最佳和最坏情况下的时间复杂度均为 O(N*M)，其中 M = 最长字符串的长度。
MSD 基数排序： 最佳情况时间复杂度是 O(N)，而 最坏情况时间复杂度是 O(N*M)，其中 M = 字符串的平均长度。
- 辅助空间：
- LSD 基数排序： O(N + B)
- MSD 基数排序： O(N + MB），其中 M = 最长字符串的长度，B = 基数的大小（B=10 种可能的数字，或 B=256 个字符，对于二进制 B=2）。
- MSD 使用 递归，因此它比 LSD 需要更多的空间。这意味着在处理少量输入时，MSD 比 LSD 慢得多。
MSD 基数排序的实现:
使用 链表： 此实现针对的是使用链表的整数。如果为每个节点使用固定长度的数组，将会占用非常大的存储空间。
下面是使用链表实现 MSD 基数排序的代码：
C++
// C++ program for the implementation
// of MSD Radix Sort using linked list
#include
#include
using namespace std;
// Linked list node structure
struct node {
vector arr;
struct node* nxt[10];
};
// Function to create a new node of
// the Linked List
struct node* new_node(void)
{
struct node* tempNode = new node;
for (int i = 0; i < 10; i++) {
tempNode->nxt[i] = NULL;
}
// Return the created node
return tempNode;
}
// Function to sort the given array
// using MSD Radix Sort recursively
void msd_sort(struct node* root, int exp,
vector& sorted_arr)
{
if (exp <= 0) {
return;
}
int j;
// Stores the numbers in different
// buckets according their MSD
for (int i = 0;
i arr.size();
i++) {
// Get the MSD in j
j = (root->arr[i] / exp) % 10;
// If j-th index in the node
// array is empty create and
// link a new node in index
if (root->nxt[j] == NULL) {
root->nxt[j] = new_node();
}
// Store the number in j-th node
root->nxt[j]->arr.push_back(
root->arr[i]);
}
// Sort again every child node that
// has more than one number
for (int i = 0; i < 10; i++) {
// If root->next is NULL
if (root->nxt[i] != NULL) {
if (root->nxt[i]->arr.size()
> 1) {
// Sort recursively
msd_sort(root->nxt[i],
exp / 10,
sorted_arr);
}
// If any node have only
// one number then it means
// the number is sorted
else {
sortedarr.pushback(
root->nxt[i]->arr[0]);
}
}
}
}
// Function