习题：基数排序-基于单向链表

传统的排序方法多数是基于比较的，例如双向冒泡排序法

//双向冒泡排序
void sort1()
{
    int a[7] = {1, 2, 3, 4, 5, 6, 7};
    int i = 0,j = 0,zz = 0;
    for (i = 0; i < 3; i++) {
        for (j = 0; j < 6 - i; j++) {
            if (a[j] < a[j + 1]) { zz = a[j]; a[j] = a[j + 1]; a[j + 1] = zz; }
            if (a[6 - j] > a[5 - j]) { zz = a[6 - j]; a[6 - j] = a[5 - j]; a[5 - j] = zz; }
        }

    }
    for (i = 0; i < 7; i++)  {
        cout << a[i] << endl;
    }
}

虽然双向冒泡排序在原有冒泡排序基础上做了些改进，但时间复杂度依然是O（n²）

在学习了链表后有一种时间复杂度为O(nlog(r)m) ）的排序算法，r为所采取的基数，而m为堆数。

基数排序简单来说就是从个位到高位一位一位的排序

下面在main函数里实现了一个简单的基数排序，对15个三位以内的数字进行排序。(链表类的定义请看上一篇博客)

#include <iostream>
#include "shuzu.h"
#include "shuzu.cpp"
#include <math.h>
using namespace std;
int get_dc(int number, int figure);
int main()
{
	int ar[15] = { 216,125,524,124,629,514,363,845,12,637,240,80,246,164,583 };
	chain<int> *ori_list = new chain<int>(ar, 15);//创建链表读取原始数据
	chain<int> *bin = new chain<int>[10];//使用链表建立十个箱子存放在某一位相同的数字
	chain<int>* temp = new chain<int>(*ori_list);//复制一下原始数据到temp链表
	int num,dc;//取出的元素，指定位数的数字
	for (int j = 1; j <= 3; j++) {
		while (!temp->empty()) {
			num = temp->get(0);
			dc = get_dc(num, j);
			bin[dc].insert(bin[dc].size(), num);//插入必须在末尾
			temp->erase(0);
		}
		for (int i = 0; i < 10; i++) {
			while (!bin[i].empty()) {
				temp->insert(temp->size(), bin[i].get(0));
				bin[i].erase(0);
			}
		}
	}
	ori_list->output();
	temp->output();
}

int get_dc(int number,int figure) //获取指定位数的数字
{
	return number%int(pow(10,figure))/ pow(10,figure-1);
}

下面是用类的指针数组实现的，有一点改动

主要是定义指针数组这句chain<int> **bin = new chain<int>*[10];

#include <iostream>
#include "shuzu.h"
#include "shuzu.cpp"
#include <math.h>
using namespace std;
int get_dc(int number, int figure);
int main()
{
	int ar[15] = { 216,125,524,124,629,514,363,845,12,637,240,80,246,164,583 };
	chain<int> *ori_list = new chain<int>(ar, 15);
	chain<int> **bin = new chain<int>*[10];
	for (int i = 0; i < 10; i++)
		bin[i] = new chain<int>();
	chain<int> *temp = new chain<int>(*ori_list);
	int num,dc;//取出的元素，指定位数的数字
	for (int j = 1; j <= 3; j++) {
		while (!temp->empty()) {
			num = temp->get(0);
			dc = get_dc(num, j);
			bin[dc]->insert(bin[dc]->size(), num);
			temp->erase(0);
		}
		for (int i = 0; i < 10; i++) {
			while (!bin[i]->empty()) {
				temp->insert(temp->size(), bin[i]->get(0));
				bin[i]->erase(0);
			}
		}
	}
	ori_list->output();
	temp->output();
}

int get_dc(int number,int figure) //获取指定位数的数字
{
	return number%int(pow(10,figure))/ pow(10,figure-1);
}