基数排序算法
- 基本概念:基数排序是一种非比较排序算法,它通过对数组中的元素按位数分组并根据每个位的值进行排序。
- 排序过程:首先找出数组中的最大元素,然后按照从最低有效位到最高有效位的顺序,使用稳定的排序算法(如计数排序) 对元素进行排序。
- 应用和效率:基数排序适用于处理大范围数字,其时间复杂度为线性,但由于使用额外的空间来存储中间排序结果,空间效率较低。
基数排序是一种排序算法,它首先将元素按照各个位数分组,然后根据它们的递增/递减顺序对元素进行排序。
假设我们有一个包含8个元素的数组。首先,我们将根据个位的值对元素进行排序。然后,我们将根据十位的值对元素进行排序。这个过程一直持续到最后一个有效位。
让我们假设初始数组为[121, 432, 564, 23, 1, 45, 788]
。按照基数排序的方式排序如下图所示。
在阅读本文之前,请先学习计数排序,因为计数排序在基数排序中用作中间排序。
基数排序的工作原理
-
找到数组中的最大元素,记为
max
。令X
为max
中的数字位数。我们计算X
,因为我们必须遍历所有元素的有效位。在数组
[121, 432, 564, 23, 1, 45, 788]
中,最大数字为788,它有3位数字。因此,循环应该执行到百位数(3次)。 -
依次遍历每个有效位。
使用任何稳定的排序技术,按照每个有效位上的数字对元素进行排序。我们在这里使用计数排序。
根据个位数字(
X=0
)对元素进行排序。 -
接下来,根据十位上的数字对元素进行排序。
-
最后,根据百位上的数字对元素进行排序。
基数排序算法
radixSort(array)
d <- 最大元素中的位数
创建大小为0-9的d个桶
for i 从 0 到 d
使用计数排序,根据第i位数字对元素进行排序
countingSort(array, d)
max <- 在d位元素中找到最大的元素
初始化一个包含全0的计数数组
for j 从 0 到 数组大小
找到元素的第d位上每个唯一数字的总计数,并将计数存储在计数数组的j索引处
for i 从 1 到 max
找到累计总和并存储在计数数组中
for j 从 数组大小 到 1
恢复元素到数组中
减少每个恢复的元素的计数值1
Python、Java 和 C/C++ 中的基数排序代码
# Python中的基数排序
# 使用计数排序按照位数的重要性来排序元素
def countingSort(array, place):
size = len(array)
output = [0] * size
count = [0] * 10
# 计算元素的个数
for i in range(0, size):
index = array[i] // place
count[index % 10] += 1
# 计算累计个数
for i in range(1, 10):
count[i] += count[i - 1]
# 按排序后的顺序放置元素
i = size - 1
while i >= 0:
index = array[i] // place
output[count[index % 10] - 1] = array[i]
count[index % 10] -= 1
i -= 1
for i in range(0, size):
array[i] = output[i]
# 实现基数排序的主要函数
def radixSort(array):
# 获取最大元素
max_element = max(array)
# 应用计数排序以根据位数值排序元素。
place = 1
while max_element // place > 0:
countingSort(array, place)
place *= 10
data = [121, 432, 564, 23, 1, 45, 788]
radixSort(data)
print(data)
// Java编程中的基数排序
import java.util.Arrays;
class RadixSort {
// 使用计数排序按照有效位排序元素
void countingSort(int array[], int size, int place) {
int[] output = new int[size + 1];
int max = array[0];
for (int i = 1; i < size; i++) {
if (array[i] > max)
max = array[i];
}
int[] count = new int[max + 1];
for (int i = 0; i < max; ++i)
count[i] = 0;
// 计算元素的个数
for (int i = 0; i < size; i++)
count[(array[i] / place) % 10]++;
// 计算累计个数
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
// 按排序后的顺序放置元素
for (int i = size - 1; i >= 0; i--) {
output[count[(array[i] / place) % 10] - 1] = array[i];
count[(array[i] / place) % 10]--;
}
for (int i = 0; i < size; i++)
array[i] = output[i];
}
// 获取数组中的最大元素
int getMax(int array[], int n) {
int max = array[0];
for (int i = 1; i < n; i++)
if (array[i] > max)
max = array[i];
return max;
}
// 实现基数排序的主要函数
void radixSort(int array[], int size) {
// 获取最大元素
int max = getMax(array, size);
// 应用计数排序以根据位数值排序元素。
for (int place = 1; max / place > 0; place *= 10)
countingSort(array, size, place);
}
// 主程序
public static void main(String args[]) {
int[] data = { 121, 432, 564, 23, 1, 45, 788 };
int size = data.length;
RadixSort rs = new RadixSort();
rs.radixSort(data, size);
System.out.println("按升序排序的数组:");
System.out.println(Arrays.toString(data));
}
}
// C编程中的基数排序
#include <stdio.h>
// 从数组中获取最大元素
int getMax(int array[], int n) {
int max = array[0];
for (int i = 1; i < n; i++)
if (array[i] > max)
max = array[i];
return max;
}
// 使用计数排序按有效位排序元素
void countingSort(int array[], int size, int place) {
int output[size + 1];
int max = (array[0] / place) % 10;
for (int i = 1; i < size; i++) {
if (((array[i] / place) % 10) > max)
max = array[i];
}
int count[max + 1];
for (int i = 0; i < max; ++i)
count[i] = 0;
// 计算元素的个数
for (int i = 0; i < size; i++)
count[(array[i] / place) % 10]++;
// 计算累计个数
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
// 按排序后的顺序放置元素
for (int i = size - 1; i >= 0; i--) {
output[count[(array[i] / place) % 10] - 1] = array[i];
count[(array[i] / place) % 10]--;
}
for (int i = 0; i < size; i++)
array[i] = output[i];
}
// 实现基数排序的主要函数
void radixsort(int array[], int size) {
// 获取最大元素
int max = getMax(array, size);
// 应用计数排序以根据位数值排序元素。
for (int place = 1; max / place > 0; place *= 10)
countingSort(array, size, place);
}
// 打印数组
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
// 主程序
int main() {
int array[] = {121, 432, 564, 23, 1, 45, 788};
int n = sizeof(array) / sizeof(array[0]);
radixsort(array, n);
printArray(array, n);
}
希望这些代码和解释对你有帮助。如果你有任何问题,请随时提问。
基数排序算法(C++编程)
基数排序是一种高效的排序方法,它根据元素的每一位来分配和收集元素。
基数排序代码示例(C++)
#include <iostream>
using namespace std;
// 获取数组中的最大元素
int getMax(int array[], int n) {
int max = array[0];
for (int i = 1; i < n; i++)
if (array[i] > max)
max = array[i];
return max;
}
// 使用计数排序来基于重要位对元素进行排序
void countingSort(int array[], int size, int place) {
const int max = 10;
int output[size];
int count[max];
for (int i = 0; i < max; ++i)
count[i] = 0;
// 计算每个元素的数量
for (int i = 0; i < size; i++)
count[(array[i] / place) % 10]++;
// 计算累积数量
for (int i = 1; i < max; i++)
count[i] += count[i - 1];
// 根据排好的顺序放置元素
for (int i = size - 1; i >= 0; i--) {
output[count[(array[i] / place) % 10] - 1] = array[i];
count[(array[i] / place) % 10]--;
}
for (int i = 0; i < size; i++)
array[i] = output[i];
}
// 实现基数排序的主要功能
void radixsort(int array[], int size) {
// 获取最大元素
int max = getMax(array, size);
// 基于每个位的值应用计数排序
for (int place = 1; max / place > 0; place *= 10)
countingSort(array, size, place);
}
// 打印数组
void printArray(int array[], int size) {
for (int i = 0; i < size; i++)
cout << array[i] << " ";
cout << endl;
}
// 驱动代码
int main() {
int array[] = {121, 432, 564, 23, 1, 45, 788};
int n = sizeof(array) / sizeof(array[0]);
radixsort(array, n);
printArray(array, n);
}
基数排序的复杂度
时间复杂度 | |
---|---|
最佳 | O(n+k) |
最差 | O(n+k) |
平均 | O(n+k) |
空间复杂度 | O(max) |
--- | --- |
稳定性 | 是 |
--- | --- |
由于基数排序是一种非比较排序算法,它相较于比较排序算法具有一定的优势。
基数排序使用计数排序作为稳定的中间排序时,时间复杂度为O(d(n+k))
。
这里,d
是循环的次数,O(n+k)
是计数排序的时间复杂度。
因此,基数排序的时间复杂度是线性的,比比较排序算法的O(nlog n)
更好。
如果我们处理非常大的数字或其他进制的数字,例如32位和64位的数字,基数排序可以在线性时间内执行,但中间排序会占用大量空间。
这使得基数排序在空间上效率较低。这也是为什么这种排序不常用于软件库中的原因。
基数排序的应用领域
基数排序在以下情况下被使用:
- 在制作后缀数组时使用了DC3算法(Kärkkäinen-Sanders-Burkhardt)。
- 处理数字范围很大的情况下。