Go Through算法导论:基数排序

2016年02月28日 原创
关键词: 数据结构 算法导论
摘要 本文介绍了什么是基数排序以及如何用C++写一个基数排序程序。

基数排序来源于一种用在卡片排序机上的算法,现在你只能在博物馆找到这种卡片排序机了。基数排序的主要思想是对要排序的数据的每一位(每一个关键字)从低位到高位,用稳定的算法进行排序。下图对要排序的数组的每一位都用稳定的排序算法进行了排序,从个位到百位。

基数排序一般应用在对具有多关键字域的记录的排序。例如,我们希望用三个关键字(年、月和日)来对日期进行排序。对这个问题,我们可以使用基于特殊比较函数的排序算法:给定两个日期,先比较黏,如果相同,在比较月,如果还相同,就比较日。我们也可以采用另一种方法,用一种稳定排序算法对这些信息进行三次排序:先日,再月,最后是年。

计数排序的代码是非常直观的。在下面的伪代码中,我们假设n个d位的元素存放在数组A中,其中第1位是最低位,第d位是最高位。

RADIX-SORT(A,d)

   for i = 1 to d

      use a stable sort to sort array A on digit i

下面是基于基数排序和计数排序对日期进行排序的c++程序。

#include<iostream>
#include<list>
using namespace std;
struct date{
    int year, month, day;
    date(int year, int month, int day) :year(year), month(month), day(day){}
    int getData(int index) {
        return index == 0 ? year :
            index == 1 ? month :
            day;
    }
    date(){}
};
date dates[] = {date(1994,9,13),date(1992,8,4),date(1998,5,3),date(1994,9,1),date(1994,9,28),date(1988,1,5)};
struct counter{
    int count = 0;
    list<date*> dates;
};
void countingsort(date* d,date** dout,int index, int length) {
    counter temp[2000];
    for (int i = 0; i < length; i++) {
        temp[d[i].getData(index)].count++;
        temp[d[i].getData(index)].dates.push_back(&d[i]);
    }
    for (int i = 1; i < 2000; i++){
        temp[i].count = temp[i].count + temp[i - 1].count;
    }

    for (int i = 0; i < length; i++){
        dout[temp[d[i].getData(index)].count-1] = temp[d[i].getData(index)].dates.front();
        temp[d[i].getData(index)].dates.pop_front();
        temp[d[i].getData(index)].count--;
    }
    

}
void radixsort(date* arr, int d) {
    for (int i = d-1; i >=0 ; i--) {
        date** out = new date*[6];
        countingsort(arr,out, i,6);
        date b[6];
        for (int j = 0; j < 6; j++) {
            b[j] = *out[j];
        }
        for (int j = 0; j < 6; j++) {
            arr[j] = b[j];
        }
    }

}
int main() {
    radixsort(dates, 3);
    for (int i = 0; i < 6; i++) {
        cout << dates[i].year << "-" << dates[i].month << "-" << dates[i].day << endl;
    }
    return 0;
}

运行结果: