基数排序(radix sort)是种应用在打孔卡排序机上面的演算法,每一张卡片有80列,在每一列上机器可以选12个孔(如图所示)中任一一个孔进行打孔。然後根据打孔的位置将他们分别放到12个容器中。工程师就可以一个接一个容器去蒐集卡片,第一个位置打孔的卡片在最上面,依序排列。
对於10进位的数字来说,每一列只会用到10个数字。一个d位数就会用到d列。卡片排序机一次只能查看一列,所以需要对n张卡片上的d位数进行排序,我们就需要设计一个排序演算法。
Example:
1. 2. 3. 4.
329 72 0 7 2 0 3 29
457 35 5 3 2 9 3 55
657 43 6 4 3 6 4 36
839 --> 45 7 --> 8 3 9 --> 4 57
436 65 7 3 5 5 6 57
720 32 9 4 5 7 7 20
355 83 9 6 5 7 8 39
radix sort是按照最低有效位数来解决卡片的排序问题。
为了保证radix sort的正确性,卡片排序机所执行的排序必须是稳定的,也就是确保在取出卡片时能够保持原本的顺序。
假设一组序列第t - 1位已经完成排序,我们想要对第t位进行排序。对第t位来排序有两种状况:
从这个证明可以发现到,排序本身必须要具有稳定性。
我们必须要对某一位数进行排序,对於个别位数的排序,如果使用的排序演算法,由於我们要进行很多轮,因此最後的结果会比来得糟糕。这里使用counting sort来对个别位数进行排序。
我们已知counting sort的时间复杂度为,但我们并不会将每个位元切分之後独立进行排序,输入的值不一定会是整数,有可能是二进位数,甚至是字串等等,我们可以将好几个位元当作一个位数进行处理。
在一般情况下,如果我们给定n个d位数,其中每一个位数有k个可能的数值,如果每一位排序使用counting sort,则可以在的时间内完成排序。
假设我们给定n个二进位数,每一个数长达位元,则我们输入的数的范围为到之间。
如果将每个数,以位元作为一个位数,则整个数会有位数,在这样得情况下,我们只需要进行轮比较,也就是我们以进制的方式来表示一个数,每一位数最大值为,最小值为,可以将counting sort中的视为。
在这样的情况下,每一轮排序所需要的时间为,我们需要的执行的总时间为,整个想法为透过来减少比较的次数,藉此来降低执行时间。对於我们希望越大越好,藉此降低比较的次数,但是也不能太大,因为我们使用counting sort,数字越大效率越差,且太大时,将主导整个函数的增长,因此希望比较小。
如果我们希望能够选到最大的,同时希望不要大过於,也就是,我们可以取,因为,如果我们选取,我们就能够得到这个演算法的执行时间的上界,将代入,得到的时间复杂度为。
随着增长到大於後,的增长速度会比来的快,因此,当时,时间复杂度为。
如果减小到以下,则项会越来越大,而项会保持。当时,时间复杂度为,渐进情况是最好的。
将n个d位的元素放到A阵列中
RADIX-SORT(A,d)
for i = 1 to d
use a stable sort to sort array A on digit i
这里稳定的排序法使用counting sort
首先,先找到输入序列中的最大值,假定输入皆为10进位数,则radix为10,有10个容器,透过radix来取个位,十位,百位。
using namespace std;
int max_number(int *, int);
void radix_sort(int *, int);
int *counting_sort(int *, int, int);
int main(void)
{
int array[6] = {2341, 4653, 456, 321, 567, 2187};
for (auto i : array)
{
cout << i << ' ';
}
cout << '\n';
radix_sort(array, 6);
for (auto i : array)
{
cout << i << ' ';
}
}
int max_number(int *A, int a_length)
{
int max = A[0];
for (int i = 1; i < a_length; i++)
{
if (A[i] > max)
{
max = A[i];
}
}
return max;
}
void radix_sort(int *A, int a_length)
{
int max = max_number(A, a_length);
for (int radix = 1; max / radix > 0; radix *= 10)
{
counting_sort(A, a_length, radix);
}
}
int *counting_sort(int *A, int a_length, int radix)
{
int *output_array = (int *)malloc(sizeof(int) * a_length);
int count[10];
for (int i = 0; i < 10; i++)
{
count[i] = 0;
}
for (int i = 0; i < a_length; i++)
{
count[(A[i] / radix) % 10]++; //依照尾数放入容器中
}
for (int i = 1; i < 10; i++)
{
count[i] = count[i] + count[i - 1];
}
for (int i = a_length - 1; i >= 0; i--)
{
output_array[count[(A[i] / radix) % 10] - 1] = A[i];
count[(A[i] / radix) % 10]--;
}
for (int i = 0; i < a_length; i++)
{
A[i] = output_array[i];
}
}
参考资料:Introduction to algorithms 3rd, 图片源於维基百科
>>: Day 20:专案04 - Facebook爬虫01 | ChromeDriver、Selenium
Leetcode #209. Minimum Size Subarray Sum 简单来说题目会给一...
当我们建立起最简单的RESTful api後,接下来我们就要将测试也放到我们的程序中了 在golan...
HTML(Hyper Text Markup Language): →就是有一堆Elements(元...
Azure machine learning: Upload data- 自己的资料自己传 要做汇率...
Cloud ?? 今天来跟各位介绍一下到底什麽是云端。 4ㄉ,所谓的云端就是先教会电脑怎麽飞行,而通...