6.2 基数排序

      基数排序算法，其原理是将整数按位数切割为不同的数组，然后按每个位数分别进行比较。

      基数排序的方法既可以采用LSD（Leastsignificant digital），从键值的最右边开始，也可以采用MSD（Most significant digital），从键值的最左边开始。

    （1）LSD方式（最低位优先）

      首先，依据最低位对所有对象进行排序；

      其次，依据次低位对 上一次排序得到的结果 进行再排序；

      然后，依次重复上述过程，直至依据最高位的最后一趟排序完成，即可得到一个有序的序列。

      使用这种排序方法对每一位进行排序时不需要再分组，而是针对整个对象。也由此造成了此方式实现较为简单，但效率较低。

      以数组{329,457,657,839,436,720,355}为例，使用LSD方式时，其排序过程如图6-2-1所示。

    （2）MSD方式（最高位优先）

      最高位优先法通常是一个递归的过程：

      首先，根据最高位排序；

      其次，在上次排序的基础上，对具有相同最高位的对象的次高位进行排序；

      然后，依次重复上述过程，直至对最低位的最后一趟排序完成，即可得到一个有序的序列。

      由于这种排序算法之后的排序并非针对所有对象，并采用了递归的方式，增加了实现的复杂度，同时也提升了算法效率。

      以数组{329,457,657,839,436,720,355}为例，使用MSD方式时，其排序过程如图6-2-2所示。

      比较两种方式可知，MSD方式的实现相较于LSD方式的实现较为复杂；但效率方面MSD方向表现会好一些。

      经过上述过程的分解，可以发现基数排序法的效率主要取决于排序不同位的数字时所采用的稳定的中间排序算法。

      所谓排序算法的稳定性，是指保证排序前两个相等的数字在序列中的前后顺序 与 排序后两数字的前后顺序不变。而基数排序算法中的中间排序算法必须是稳定的排序算法。

      常用的稳定的排序算法包括：插入排序、合并排序、冒泡排序、折半插入排序，基数排序等。

      常用的不稳定的排序算法包括：快速排序、堆排序、希尔排序等。

      基数排序算法相比于其他算法在对于单个数字组成的数组的排序上并无优势，其优势主要体现在类似于时间（XX：YY），日期（YYYY-MM-DD）等这种多个数字一组表示一个元素，对于这种元素组成的数组的排序也许更能体现基数排序算法的特点。

      以下我们将给出日期（YYYY-MM-DD）为元素组成的数组的基数排序源代码，使用MSD和LSD两种不同的方式。

      LSD方式，C实现代码如下：

#include<stdio.h>
#include<random>
#include<Time.h>
//表示提取时间结构体中哪个元素的标志位
const int DAY = 0;
const int MONTH = 1;
const int YEAR = 2;
//定义一个表示时间的结构体
struct Time{
    int day;
    int month;
    int year;
};
//交换两元素的位置
template<typename T>
void exchange(T &a, T &b){
    T temp = a;
    a = b;
    b = temp;
}
//读取一个日期（YYYY-MM-DD）中的元素，简化读取过程。
int getElement(Time a[], const int &index, const int &flag){
	return *( (int*)(&a[index]) + flag );
}
//采用插入排序作为基数排序的中间排序算法。
void insertion_sort(Time a[], const int &length, const int &flag){
	for(int i=1; i<length; i++) {
		int elementBefore = getElement(a, i-1, flag);
		int elementAfter = getElement(a, i, flag);
		if(  elementAfter >= elementBefore ){
			continue;
		}else {
			int baseElement = getElement(a, i, flag);
			Time base = a[i];
			int j=i-1;
			for(; j>=0; j--){
				int tempElement = getElement(a, j, flag);
				if( tempElement <= baseElement ) {
					break;
				}else {
					a[j+1] = a[j];
				}
			}
			a[j+1] = base;
		}
	}
}
//显示数组的排序。
void showArray(Time a[], const int &length){
    for(int i=0; i<length; i++) {
        printf("%4d-%2d-%2d\n", a[i].year, a[i].month, a[i].day);
    }
    printf("\n");
}
//基数排序，此为LSD方式，即从键值的最右边开始比较。
void radix_sort(Time a[], const int &length){
	insertion_sort(a, length, DAY);
	insertion_sort(a, length, MONTH);
	insertion_sort(a, length, YEAR);
}
int main(int argc, char** argv){
	//数组中元素的个数
    const int length = 30;
	//年度的起始年份
	const int yearStart = 1900;
	//年份的跨度，即从1900-2014年
    const int yearLength = 105;
	//月份的跨度
    const int monthLength = 12;
	//日期的跨度，由于不同月份其最大日期数不同，但为了简化程序，此处不做讨论，统一取一个月含31天
    const int dayLength = 31;
	//为数组a分配内存看空间
    Time* a = (Time*)malloc(sizeof(Time)*length);
    srand( (unsigned int)time(NULL) );
	//为时间结构体为元素组成的数组随机赋值。
    for(int i=0; i<length; i++) {
        a[i].day = rand()%dayLength + 1;
        a[i].month = rand()%monthLength + 1;
        a[i].year = rand()%yearLength + yearStart;
    }
	//显示原数组
    showArray(a, length);
    //进行基数排序
	radix_sort(a, length);
	//显示排序后数组的排序状况
    showArray(a, length);
	//释放分配的内存空间
	free(a);
	//暂停程序，便于观察结果
	system("pause");
    return 0;
}

      LSD方式下，C++代码实现如下：

#include <vector>
#include <iostream>
#include <iomanip>
#include <random>
#include <time.h>
using namespace std;
//表示提取时间中的哪个元素的标志位
const int DAY = 0;
const int MONTH = 1;
const int YEAR = 2;
class Time{
public:
	Time(const int &year, const int &month, const int &day);
	int getElement(const int &flag);
	void showTime();
private:
	int year;
	int month;
	int day;
};
//初始化Time类，包括年，月，日。
Time::Time (const int& year, const int &month, const int &day) {
	this->year = year;
	this->month = month;
	this->day = day;
}
//得到时间结构中的一个元素，如：年，月，日等
int Time::getElement(const int &flag) {
	if( flag==DAY ) {
		return day;
	}else if( flag==MONTH ) {
		return month;
	}else if( flag==YEAR ) {
		return year;
	}
	//输出错误标示，指出输入的flag不符合要求
	return -1;
}
//显示当前对象表示的时间
void Time::showTime() {
	cout<<setw(4)<<year<<"-"<<setw(2)<<month<<"-"<<setw(2)<<day<<endl;
}

//显示vector中所有对象的时间
void show(vector<Time> &a) {
	vector<Time>::const_iterator itEnd = a.end();
	for(vector<Time>::iterator it=a.begin(); it<itEnd; it++) {
		(*it).showTime();
	}
	cout<<endl;
}
//此处的end为数组的最后一位坐在的位置
void merge(vector<Time> &a, const int &start, const int &mid, const int &end, const int &flag){
    vector<Time>::const_iterator itStart = a.begin() + start;
    vector<Time>::const_iterator itEnd = a.begin() + end;
    vector<Time>::const_iterator itMid = a.begin() + mid;
	vector<Time> left(itStart, itMid+1);
	vector<Time> right(itMid+1, itEnd+1);

	vector<Time>::iterator it = a.begin()+start;
	vector<Time>::iterator itLeft = left.begin();
	vector<Time>::const_iterator itEndLeft = left.end();
	vector<Time>::iterator itRight = right.begin();
	vector<Time>::const_iterator itEndRight = right.end();
	//不使用“哨兵”,存储是否排序完成的标志即可
	int countLeft = left.size();
	int countRight = right.size();
	int count = countLeft+countRight;
	for(int i=0; i<count; i++) {
		if( (itLeft!=itEndLeft) && (itRight!=itEndRight) ) {
			int leftElement = (*itLeft).getElement(flag);
			int rightElement = (*itRight).getElement(flag);
			if( leftElement<=rightElement ){
				*it = *itLeft;
				itLeft++;
			}else {
				*it = *itRight;
				itRight++;
			}
			it++;
		}else if( itLeft==itEndLeft ){
			for(;itRight<itEndRight;) {
				//等价于(*it)=*(itRight); it++; itRight++;
				*(it++) = *(itRight++);
			}
			break;
		}else if( itRight==itEndRight ) {
			for(;itLeft<itEndLeft;) {
				//等价于(*it)=*(itLeft); it++; itLeft++;
				*(it++) = *(itLeft++);
			}
			break;
		}
	}
}
void merge_sort(vector<Time> &a, const int &start, const int &end, const int &flag){
    if(start<end) {
        int mid = (start+end)/2;
        merge_sort(a, start, mid, flag);
        merge_sort(a, mid+1, end, flag);
        merge(a, start, mid, end, flag);
    }
}
//基数排序，先按日期排序，后按月份排序，最后按年份排序
void radix_sort(vector<Time> &a) {
	merge_sort(a, 0, a.size()-1, DAY);
	merge_sort(a, 0, a.size()-1, MONTH);
	merge_sort(a, 0, a.size()-1, YEAR);
}

int main(int argv, char** argc) {
	//数组中含有的元素个数
	const int length = 30;
	//设置起始年份
	const int yearStart = 1900;
	//设置年份跨度，此例中年份跨度为1900-2014年
	const int yearLength = 115;
	//设置起始月份
	const int monthStart = 1;
	//设置月份跨度，此例中月份跨度为1-12月
	const int monthLength = 12;
	//设置起始日期
	const int dayStart = 1;
	//设置日期跨度，此例中日期跨度为1-31日，暂未考虑不同月份的最大天数差异的问题
	const int dayLength = 31;
	
	//对原数组进行随机赋值
	vector<Time> timeVector;
	srand( (unsigned int)time(NULL) );
	for(int i=0; i<length; i++) {
		int year = rand()%yearLength + yearStart;
		int month = rand()%monthLength + monthStart;
		int day = rand()%dayLength + dayStart;
		Time temp(year, month ,day);
		timeVector.push_back(temp);
	}

	//对控制台title进行命名
	system("title 基数排序");
	//显示原数组序列情况
	show(timeVector);
	//进行基数排序
	radix_sort(timeVector);
	//显示排序后数组的排序情况
	show(timeVector);
	//暂停，方便观察结果
	system("pause");
	return 0;
}

      其运行结果如下图所示：

      MSD方式下，c实现代码如下：

#include <stdio.h>
#include <random>
#include <time.h>
#include <malloc.h>

const int DAY = 0;
const int MONTH = 1;
const int YEAR = 2;
const int countFlags = 3;
//定义Time结构体，表示日期
struct Time {
	int day;
	int month;
	int year;
};
//某键值中是否有相同的元素
struct RangeSame {
	int start;
	int end;
};
//
struct RangeSameArray{
	int lengthRangeSame;
	RangeSame* rangeSameArray;
};
//
void showTimeSeries(const Time timeSeries[], const int &length) {
	for(int i=0; i<length; i++) {
		printf("%4d-%2d-%2d\n", timeSeries[i].year, timeSeries[i].month, timeSeries[i].day);
	}
	printf("\n");
}
void showTimeSeries(const Time timeSeries[], const int &start, const int &end) {
	for(int i=start; i<end+1; i++) {
		printf("%4d-%2d-%2d\n", timeSeries[i].year, timeSeries[i].month, timeSeries[i].day);
	}
	printf("\n");
}
//交换两元素的位置
template<typename T>
void exchange(T &a, T &b) {
	T temp = a;
	a = b;
	b = temp;
}
//获得Time结构体中的年份，月份，日期等元素
int getElement(Time time, const int &flag) {
	if( flag==DAY ) {
		return time.day;
	}else if( flag==MONTH ) {
		return time.month;
	}else if( flag==YEAR ) {
		return time.year;
	}
	return -1;
}
//冒泡排序算法
void bubble_sort(Time timeSeries[], const int &start, const int &end, const int &flag) {
	for(int i=start; i<end+1; i++) {
		//end-(i-start) = end-+start-i
		for(int j=start; j<end+start-i; j++) {
			int elementBefore = getElement(timeSeries[j], flag);
			int elementAfter = getElement(timeSeries[j+1], flag);
			if( elementBefore>elementAfter ) {
				exchange(timeSeries[j], timeSeries[j+1]);
			}
		}
	}
}
//检测时间序列中是否有相同键值的片段
RangeSameArray checkSame(Time timeSeries[], const int &start, const int &end, const int &flag) {
	RangeSameArray rangeSameArray;
	rangeSameArray.lengthRangeSame  = 0;
	rangeSameArray.rangeSameArray = NULL;
	int countSame = 0;
	bool isSaming = false;
	//检测相同键值的元素的起止位置
	for(int i=start; i<end; i++) {
		int elementBefore = getElement(timeSeries[i], flag);
		int elementAfter = getElement(timeSeries[i+1], flag);
		if( elementBefore==elementAfter ) {
			if( isSaming==false ) {
				isSaming = true;
				rangeSameArray.lengthRangeSame += 1;
				rangeSameArray.rangeSameArray = (RangeSame*)realloc(rangeSameArray.rangeSameArray, sizeof(RangeSame)*rangeSameArray.lengthRangeSame);
				rangeSameArray.rangeSameArray[ rangeSameArray.lengthRangeSame-1 ].start = i;
				rangeSameArray.rangeSameArray[ rangeSameArray.lengthRangeSame-1 ].end = i+1;
			}else {
				rangeSameArray.rangeSameArray[ rangeSameArray.lengthRangeSame-1 ].end = i+1;
			}
		}else {
			if( isSaming==true ) {
				isSaming = false;
			}
		}
	}
	return rangeSameArray;
}
//基数排序
void radix(Time timeSeries[], const int &start, const int &end, int flag) {
	//检测是否对所有位完成排序过程
	if( flag>=0 ){
		//进行冒泡排序
		bubble_sort(timeSeries, start, end, flag);
		//显示排序的细节过程
		//showTimeSeries(timeSeries, start, end);
		//判断是否有相同的键值，并保留其起止位置
		RangeSameArray rangeSameArray = checkSame(timeSeries, start, end, flag);
		//对相同键值的元素，对其次高位进行排序
		flag -= 1;
		for( int i=0; i<rangeSameArray.lengthRangeSame; i++) {
			radix(timeSeries, rangeSameArray.rangeSameArray[i].start, rangeSameArray.rangeSameArray[i].end, flag);
		}
	}
}
void radix_sort(Time timeSeries[], const int &length) {
	radix(timeSeries, 0, length-1, YEAR);
}
int main(int argc, char** argv) {
	//数组中含有的元素个数
	const int length = 30;
	//设置起始年份
	const int yearStart = 1900;
	//设置年份跨度，此例中年份跨度为1900-2014年
	const int yearLength = 115;
	//设置起始月份
	const int monthStart = 1;
	//设置月份跨度，此例中月份跨度为1-12月
	const int monthLength = 12;
	//设置起始日期
	const int dayStart = 1;
	//设置日期跨度，此例中日期跨度为1-31日，暂未考虑不同月份的最大天数差异的问题
	const int dayLength = 31;

	Time* timeSeries = (Time*)malloc( sizeof(Time)*length );
	srand( (unsigned int)time(NULL) );
	for(int i=0; i<length; i++) {
		timeSeries[i].year = rand()%yearLength + yearStart;
		timeSeries[i].month = rand()%monthLength + monthStart;
		timeSeries[i].day = rand()%dayLength + dayStart;
	}
	system("title 基数排序");
	showTimeSeries(timeSeries, length);
	//基数排序算法MSD方式
	radix_sort(timeSeries, length);
	showTimeSeries(timeSeries, length);
	system("pause");
	return 0;
}

      MSD方式下，C++代码实现如下：

#include <iostream>
#include <iomanip>
#include <random>
#include <time.h>
using namespace std;

class Time{
public:
	Time(const int &year, const int &month, const int &day);
	int getElement(const int &flag);
	void showTime();
	static const int DAY = 0;
	static const int MONTH = 1;
	static const int YEAR = 2;
private:
	int day;
	int month;
	int year;
};
class RangeSame{
public:
	RangeSame(){};
	RangeSame(vector<Time>::iterator itStartInit, vector<Time>::iterator itLastInit):itStart(itStartInit),itLast(itLastInit){};
	void setStart(vector<Time>::iterator itStart){ this->itStart = itStart; }
	void setLast(vector<Time>::iterator itLast) { this->itLast = itLast; }
	vector<Time>::iterator getStart() { return itStart; }
	vector<Time>::iterator getLast() { return itLast; }
private:
	vector<Time>::iterator itStart;
	vector<Time>::iterator itLast;
};
Time::Time(const int &year, const int &month, const int &day) {
	this->year = year;
	this->month = month;
	this->day = day;
}
int Time::getElement(const int &flag) {
	if( flag==YEAR ) {
		return year;
	}else if( flag==MONTH) {
		return month;
	}else if( flag==DAY ) {
		return day;
	}
	return -1;
}
void Time::showTime(){
	cout<<setw(4)<<year<<"-"<<setw(2)<<month<<"-"<<setw(2)<<day<<endl;
}
void showTimeSeries(vector<Time> timeSeries) {
	vector<Time>::const_iterator itEnd = timeSeries.end();
	for(vector<Time>::iterator it=timeSeries.begin(); it<itEnd; it++) {
		(*it).showTime();
	}
	cout<<endl;
}
void showTimeSeries(vector<Time>::iterator itStart, vector<Time>::const_iterator &itEnd) {
	for(vector<Time>::iterator it=itStart; it<itEnd; it++) {
		(*it).showTime();
	}
	cout<<endl;
}
//寻找待插入元素的插入位置
vector<Time>::iterator findInsertPosition(vector<Time>::iterator itStart, vector<Time>::iterator itLast, vector<Time>::iterator itInsert, const int &flag) {
	int elementInsert = (*itInsert).getElement(flag);
	vector<Time>::iterator itMid = itStart+(itLast-itStart)/2;
	int elementMiddle = (*itMid).getElement(flag);
	vector<Time>::iterator itInsertPosition = itStart;
	if( itLast-itStart!=0 ) {
		if( elementInsert<elementMiddle ) {
			itInsertPosition = findInsertPosition(itStart, itMid, itInsert, flag);
		}else {
			itInsertPosition = findInsertPosition(itMid+1, itLast, itInsert, flag);
		}
	}else {
		if( elementInsert<elementMiddle ) {
			return itStart;
		}else {
 			return itStart+1;
		}
	}
	return itInsertPosition;
}
//确定插入位置后，对原数组进行重新排序
void insert(vector<Time>::iterator itStart, vector<Time>::iterator itLast, vector<Time>::iterator itInsert) {
	Time temp = *itInsert;
	for(vector<Time>::iterator it=itLast+1; it>itStart; it--) {
		(*it) = (*(it-1));
	}
	(*itStart) = temp;
}
//折半插入排序
void binary_insertion_sort(vector<Time>::iterator itStart, vector<Time>::iterator itLast, const int &flag) {
	for(vector<Time>::iterator it=itStart; it<itLast; it++) {
		vector<Time>::iterator itInsert = findInsertPosition(itStart, it, it+1, flag);
		insert(itInsert, it, it+1);
	}
}

vector<RangeSame> checkSame(vector<Time>::iterator itStart, vector<Time>::iterator itLast, const int &flag) {
	vector<RangeSame> rangeSame;
	vector<RangeSame>::iterator itRangeSame = rangeSame.begin();
	bool isSaming = false;
	for(vector<Time>::iterator it=itStart; it<itLast; it++) {
		int elementBefore = (*it).getElement(flag);
		int elementAfter = (*(it+1)).getElement(flag);
		if( elementBefore==elementAfter ) {
			if( isSaming==false ) {
				isSaming = true;
				RangeSame tempRangeSame(it, (it+1));
				rangeSame.push_back(tempRangeSame);
				itRangeSame = rangeSame.end()-1;
			}else{
				(*itRangeSame).setLast( it+1 );
			}
		}else{
			if( isSaming==true ) {
				isSaming = false;
			}
		}
	}
	return rangeSame;
}

void radix(vector<Time>::iterator itStart, vector<Time>::iterator itLast, int &flag) {
	if( flag>=0 ) {
		//进行折半插入排序
		binary_insertion_sort(itStart, itLast, flag);
		//显示排序情况
		//showTimeSeries(itStart, itLast+1);
		//检查是否有相同的键值
		vector<RangeSame> rangeSame = checkSame(itStart, itLast, flag);
		flag -= 1;
		//对具有相同键值的元素进行排序
		for(vector<RangeSame>::iterator it=rangeSame.begin(); it<rangeSame.end(); it++) {
			radix( (*it).getStart(), (*it).getLast(), flag);
		}
	}
}
//基数排序算法
void radix_sort(vector<Time> &timeSeries) {
	vector<Time>::iterator itStart = timeSeries.begin();
	vector<Time>::iterator itLast = timeSeries.end()-1;
	int flag = Time::YEAR;
	radix(itStart, itLast, flag);
}

int main(int argc, char** arv) {
	//数组中含有的元素个数
	const int length = 30;
	//设置起始年份
	const int yearStart = 1900;
	//设置年份跨度，此例中年份跨度为1900-2014年
	const int yearLength = 115;
	//设置起始月份
	const int monthStart = 1;
	//设置月份跨度，此例中月份跨度为1-12月
	const int monthLength = 12;
	//设置起始日期
	const int dayStart = 1;
	//设置日期跨度，此例中日期跨度为1-31日，暂未考虑不同月份的最大天数差异的问题
	const int dayLength = 31;

	//初始化Time数列，并对其随机赋值
	srand( (unsigned int)time(NULL) );
	vector<Time> timeSeries;
	for(int i=0; i<length; i++) {
		int year = rand()%yearLength + yearStart;
		int month = rand()%monthLength + monthStart;
		int day = rand()%dayLength + dayStart;
		Time temp(year, month, day);
		timeSeries.push_back(temp);
	}
	//对控制台窗口进行命名
	system("title 基数排序");
	//显示原数组
	showTimeSeries(timeSeries);
	//进行基数排序
	radix_sort(timeSeries);
	//显示排序后的数组
	showTimeSeries(timeSeries);
	//暂停程序，方便观察结果
	system("pause");
	return 0;
}

      本例中，稳定的中间排序算法采用折半插入排序算法。由于之前并未做折半插入排序算法的讲解，故借用百度百科中的相关介绍，详情可见折半插入排序。

      为了尽可能地说明基数排序的中间算法可由任意的稳定排序算法实现，同时帮助回顾和再次熟悉一下有哪些稳定的排序算法，所以本次实例中每次均采用了不同的中间排序算法，依次为：插入排序算法、合并排序算法、冒泡排序算法和折半插入排序算法。

      同时，在关于MSD和LSD两种方式的说明上，以下文章给我了我很大的帮助。

      http://www.cnblogs.com/Braveliu/archive/2013/01/21/2870201.html