[数据结构与算法]《算法学习》学习（十）----计数排序，基数排序，桶排序（C语言）

系列文章

《算法导论》学习（一）---- 插入排序和归并排序
《算法导论》学习（七）----堆排序和优先队列（C语言）
《算法导论》学习（八）----快速排序（C语言）
《算法导论》学习（九）----为什么比较排序算法时间复杂度的下界是确定的？
《算法学习》学习（十）----计数排序，基数排序，桶排序（C语言）

前言

本文主要讲解了三大线性时间排序：
1.计数排序
2.基数排序
3.桶排序
给出了它们的C语言代码和算法逻辑

一、线性时间排序

1.什么是比较排序？

比较算法有一个性质：在排序的最终结果中，各元素的次序依赖于它们之间的比较
比如：

1.插入排序
2.冒泡排序
3.归并排序
4.堆排序
5.快速排序

2.为什么比较排序不能是线性时间排序？

在前面的文章我们证明了如下的结论：

对包含n个元素的输入序列来说，任何比较排序在最坏情况下都要经过$\Omega (nlgn)$次比较

因此比较排序算法不可能是线性时间排序算法

3.线性时间排序算法

比如有：

1.计数排序
2.基数排序
3.桶排序

这些算法它们都不是比较排序算法，它们得到正确的顺序不是通过比较，而是通过计算来进行的。

都采用了空间换时间的算法理念

二、计数排序

1.C语言代码

#include<stdio.h>
#include<stdlib.h>
#include<time.h>


//输入的规模 
#define SIZE 100
//输入数据的范围上界0~LIM 
#define LIM 1000



//计数排序 
void COUNTING_SORT(int *a,int *b,int k,int size)
{
	int c[k+1];//申请大小为k+1的空间 
	int i=0;
	//将c清0 
	for(i=0;i<=k;i++)
	{
		c[i]=0;
	}
	//对a中的元素进行计数
	//如果a中的元素x出现，那么就让c[x]的数值加1
	//这样，有a数组总共n个x，那么对应的c[x]=n 
	for(i=0;i<size;i++)
	{
		c[a[i]]++;
	}
	//进行不断的加法操作
	//通过该操作，c[x]的值代表的是，a中小于等于x的个数
	//得到这个个数信息，就可以变相得到x的大小顺序信息 
	for(i=1;i<=k;i++)
	{
		c[i]=c[i]+c[i-1];
	}
	//排序	
	for(i=size-1;i>=0;i--)
	{
		//通过c数组，得到a[i]的值x的次序
		//通过索引的方式写入数组，完成排序 
		b[c[a[i]]-1]=a[i];
		
		//由于a中很可能会存在重复的元素
		//那么排完序让其减一，就可以避免重复
		//而且这么做，可以保证a和b中，相同值的前后关系是不变的
		//这样得到的计数排序算法是“稳定的” 
		c[a[i]]=c[a[i]]-1;
	}
}


int main()
{
	int a[SIZE];
	int b[SIZE];
	srand((unsigned)time(NULL));
	int i=0;
	//得到随机数组 
	for(i=0;i<SIZE;i++)
	{
		a[i]=rand()%LIM;
	}
	//将随机数组打印出来 
	for(i=0;i<SIZE;i++)
	{
		printf("%5d",a[i]);
	}
	printf("\n");
	//对数组进行计数排序 
	COUNTING_SORT(a,b,LIM,SIZE);
	//将排序后的新数组打印出来 
	for(i=0;i<SIZE;i++)
	{
		printf("%5d",b[i]);
	}
	printf("\n");	
	return 0;
}

2.算法逻辑

（1）前提假设

假设n个输入元素中的每一个元素都是在0到k区间内的一个整数，其中k也是一个整数。

（2）基本思想

1.对于每一个输入元素x，确定小于等于x的个数n。利用信息n，就可以将x放到输出有序数组B上面，即B[n]=x。

2.那么让输入无序数组A中的每一个元素经历上述过程，就可以得到完整的输出有序数组B

3.对于输入无序数组A中有多个同一元素的情况，用如下解决方案：

1.对于A含有多个x的情况下，统计出的个数n里面，包含小于x的元素的个数n1，以及x本身的个数n2
2.那么n1~n1+n2就是多个x元素应该在输出有序数组B的顺序
3.每一次输出x后，就令n--，那么索引便是n1~n1+n2
4.采用从尾到头的循环的方式，就可以保证A和B中的相同元素的先后次序不变

（3）算法特点

算法本身具有稳定性：

输入数组A和输出数组B中，相同元素的先后次序不变，比如说：

A中有一段是“8，8，8”，我们给它们编号“$8_1，8_2，8_3$”，那么B输出时也是：“$8_1，8_2，8_3$”

3.算法时间性能分析

$$当k=O(n),n为输入规模时，算法的运行时间为T(n)=\Theta (n)。$$
但是时间复杂度的常数项比较大。

三、基数排序

1.C语言代码

#include<stdio.h>
#include<stdlib.h>
#include<time.h>


//输入的规模 
#define SIZE 100
//输入数据的范围上界0~LIM 
#define LIM 100000



//得到一个数的位信息
int get_radix(int num,int r)
{
	int i=0;
	int temp;
	for(i=0;i<r;i++)
	{
		temp=num%10;
		num=num/10;
	}
	return temp;
} 




//计数排序
//这里的计数排序是针对基数排序的
//计数的范围永远是0~9
//广泛适用的计数排序见计数排序 
void COUNTING_SORT(int *a,int *b,int k,int size)
{
	int c[11];//申请大小为11的空间 
	int temp[size];//申请大小为size的空间
	int i=0;
	//将c清0 
	for(i=0;i<11;i++)
	{
		c[i]=0;
	}
	//得到a中元素的第k位数的数组 
	for(i=0;i<size;i++)
	{
		b[i]=get_radix(a[i],k);
	}
	//对b中的元素进行计数
	//如果b中的元素x出现，那么就让c[x]的数值加1
	//这样，有b数组总共n个x，那么对应的c[x]=n 
	for(i=0;i<size;i++)
	{
		c[b[i]]++;
	}
	//进行不断的加法操作
	//通过该操作，c[x]的值代表的是，b中小于等于x的个数
	//得到这个个数信息，就可以变相得到x的大小顺序信息 
	for(i=1;i<=10;i++)
	{
		c[i]=c[i]+c[i-1];
	}
	//排序	
	for(i=size-1;i>=0;i--)
	{
		//通过c数组，得到b[i]的值x的次序
		//通过索引的方式写入数组，完成排序 
		//这里b只是某一位的数据，真正写入的应该是a中的真实数据 
		temp[c[b[i]]-1]=a[i];
		
		//由于b中很可能会存在重复的元素
		//那么排完序让其减一，就可以避免重复
		//而且这么做，可以保证temp和a中，相同值的前后关系是不变的
		//使更高位的排序并不会影响原来的有序 
		c[b[i]]=c[b[i]]-1;
	}
	//将这一阶段排好序的数组存入a 
	for(i=0;i<size;i++)
	{
		a[i]=temp[i];
	}
}



//基数排序
void RADIX_SORT(int *a,int r,int size)
{
	int i=0;
	int b[size];
	//按位数循环，从低位到高位进行排序 
	for(i=1;i<=r;i++)
	{
		COUNTING_SORT(a,b,i,size);
	}
}



int main()
{
	int a[SIZE];
	int b[SIZE];
	srand((unsigned)time(NULL));
	int i=0;
	//得到随机数组 
	for(i=0;i<SIZE;i++)
	{
		a[i]=rand()%LIM;
	}
	//得到a中所有元素的最大位数
	int d=1;
	int lim=LIM-1;
	for(i=0;;i++)
	{
		lim=lim/10;
		if(lim==0)
		{
			break;
		}
		d++;
	} 
	//将随机数组打印出来 
	for(i=0;i<SIZE;i++)
	{
		printf("%6d",a[i]);
	}
	printf("\n");
	//对数组进行基数排序 
	RADIX_SORT(a,d,SIZE);
	//将排序后的新数组打印出来 
	for(i=0;i<SIZE;i++)
	{
		printf("%6d",a[i]);
	}
	printf("\n");	
	return 0;
}

2.算法逻辑

（1）前提假设

假设n个输入元素中的每一个元素都是不超过k位的一个整数，其中k也是一个整数。

（2）基本思想

1.对于一组输入无序数组A，它的所有元素最大为k位

2.那么从最低位开始往最高位循环，每一次循环根据A中这些数该位上0~9的数字排序

3.每一次排序都用计数排序，计数排序的k值为9

4.每排序一个位上的数据，就依此来改变整体数据的位次

3.算法时间性能分析

当输入数组为：n个d位数，其中每一个数位有k个可能的取值,那么当：
$$d为常数且k=O(n)时，基数排序的时间代价是线性时间代价，T(n)=\Theta (n)$$
但是时间复杂度的常数项比较大。
即每一次循环的用时比快速排序要长，但是循环的次数小于快速排序。

四、桶排序

1.C语言代码

注意：

该代码中涉及到了链表的数据结构，下面代码中的链表仅是针对桶排序写的，不是一般性的链表操作函数。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>



#define SIZE 1000
#define LIM 1000



void insertion_sort(int *x,int num)
{
	int i=0;//循环变量初始化 
	int j=0;//循环变量初始化 
	int tempval;//中间暂存变量初始化，因涉及两数交换所需
	/*
	第一个循环是要遍历一遍数组
	依次为每一个变量找到它合适的位置
	这个合适的位置是一个局部的范围
	范围是在这个变量之前的空间，包括这个变量
	随着循环的进行，到最后
	这个局部的范围就是所有变量
	那么就完成排序 
	*/ 
	for(i=1;i<num;i++)
	{
		j=i-1;//为位置指正赋值，目的是设置局部范围的界限
		/*
		第二个循环是找准第一个循环所确定变量的合适位置
		循环的方向是从确定变量位置往前
		循环条件包含了判断规则
		满足循环就需要进行交换数据
		不满足循环时，就是局部排序完成时 
		*/ 
		while((x[j+1]<x[j])&&(j>=0))
		{
			tempval=x[j+1];//数据交换 
			x[j+1]=x[j];
			x[j]=tempval;
			j=j-1;//循环变量赋值，推动循环进行 
		}
	}
}



//设计链表的数据结构 
typedef struct list
{
	//值 
	int key;
	//指向下一个结点的指针 
	list* p;
}list; 



//获取链表的长度
//该长度也可以称为值的数量 
int list_length(list *a,int i)
{
	int length=0;//声明长度变量 
	//链表循环变量 
	list *temp;
	temp=a[i].p;
	//如果temp没有指向的空间，那么结束循环 
	while(temp!=NULL)
	{
		length++;//一次循环代表有一个结点空间 
		temp=temp->p;//将循环变量指向下一个结点 
	}
	return length;//返回长度 
}



//释放动态分配的内存 
void destroy_list(list *a,int n)
{
	list *temp1;
	list *temp2;
	temp1=a[n].p;
	while(temp1!=NULL)
	{
		temp2=temp1;
		temp1=temp1->p;
		free(temp2);
//		printf("release success\n"); 
	}
}



//插入值到链表
//该插入函数是将新值永远插入第一个位置 
void list_insert(list *a,int n,int num)
{
	list* temp;
	//如果不动态分配内存，那么内存会被系统在程序运行到某个结点被回收
	//导致无法存储值到程序结束 
	temp=(list *)malloc(sizeof(list));//动态分配内存 
	temp->key=num;
	//如果链表是空的，那么直接插入到头节点 
	if((a[n].p)==NULL)
	{
		temp->p=NULL;
		a[n].p=temp;
	}
	//如果链表不空，那么需要插入到头节点后，还要与原头结点连接 
	else
	{
		temp->p=a[n].p;
		a[n].p=temp;
	}
}



//链表信息打印 
void list_print(list *a,int n)
{
	list* temp;
	temp=(list *)malloc(sizeof(list));
	temp->p=a[n].p;
	printf("%d  |||",list_length(a,n));//打印大小
	//大小之后打印具体的值 
	while(temp->p!=NULL)
	{
		printf("%5d",temp->p->key);
		temp->p=temp->p->p;
	}
	printf("\n");
}



//链表排序
//并没有在链表的基础上进行排序
//而是通过一个中间数组
//先将链表的值赋给数组，数组排好序后，再传值给链表
//那么数组的排序就可以使用多种排序手段
//这里用的最简单的插入排序 
void list_sort(list *a,int n)
{
	if(a==NULL)
	{
		return ;
	}
	int i=0;
	int num=list_length(a,n);
	int temp1[num];
	list *temp;
	temp=a[n].p;
	//为数组赋值 
	while(temp!=NULL)
	{
		temp1[i]=temp->key;
		temp=temp->p;
		i++;
	}
	//排序 
	insertion_sort(temp1,num);	
	i=0;
	temp=a[n].p;
	//为链表赋值 
	while(temp!=NULL)
	{
		temp->key=temp1[i];
		temp=temp->p;
		i++;
	}	
}



//桶排序 
void BUCKET_SORT(int *a,int size)
{
	int i=0;
	int j=0;
	float temp1;
	int temp2;
	list *temp3;
	list b[size];//先定义一个链表数组
	//为链表数组初始化 
	for(i=0;i<size;i++)
	{
		b[i].p=NULL;
	}
	//将数组的元素插入到指定的链表 
	for(i=0;i<size;i++)
	{
		temp1=(float)a[i]/(float)LIM;//将数据降到0~1之间，当作为均匀分布概率值 
		temp2=(int)(temp1*size);//将概率值乘上来链表数组的大小，向下取整后找到链表数组中对应的链表 
		list_insert(b,temp2,a[i]);//将元素插入指定链表 
	}
	//将链表数组的所有链表进行排序 
	for(i=0;i<size;i++)
	{
		list_sort(b,i);
	}
	//按照链表数组的绝对顺序，将值赋值给原数组
	//这样就排序成功了 
	for(i=0;i<size;i++)
	{
		temp3=b[i].p;
		while(temp3!=NULL)
		{
			a[j]=temp3->key;
			j++;
			temp3=temp3->p;
		}
	}
	for(i=0;i<size;i++)
	{
		destroy_list(b,i);
	}
}



int main()
{
	int a[SIZE];
	srand((unsigned)time(NULL));
	int i=0;
	//得到随机数组 
	for(i=0;i<SIZE;i++)
	{
		a[i]=rand()%LIM;
	}
	//将随机数组打印出来 
	for(i=0;i<SIZE;i++)
	{
		printf("%5d",a[i]);
	}
	printf("\n");
	//对数组进行桶排序 
	BUCKET_SORT(a,SIZE);
	//将排序后的新数组打印出来 
	for(i=0;i<SIZE;i++)
	{
		printf("%5d",a[i]);
	}
	printf("\n");	
	return 0;
}

2.算法逻辑

（1）假设前提

输入数据的情况服从均匀分布

（2）基本思想

1.将数据同过除以某一个数，使得所有数据落入[0,1)，这些数据均匀分布在其上

2.如果有n个数据输入，那么申请n个链表L(n)，称为n个桶

3.将落入[0,1)中的数据x，让i=n*x（向下取整），然后让原数据a插入链表L(i)

4.然后对每一个链表L(i)，进行排序

5.然后将n个链表中的数据，依次输出到数组

（3）算法特点

将n个数据均匀分到n个链表中，那么如果数据是均匀的话，每一个链表中的数据是极小的

那么对于每一个链表的排序规模较小，时间代价是常数

3.算法时间性能分析

算法的时间分析涉及复杂的概率分析，这里不做具体分析

那么结论是：
$$桶的大小的平方和与总的元素数呈线性关系，桶排序的代价在线性时间内完成$$

五、线性时间排序一定好吗？

1.时间角度

线性时间排序的循环次数比比较时间排序少，但是每一次循环花费时间更多

2.空间角度

线性时间排序运用了空间换时间的思路，需要大量的额外空间来减少循环次数

3.结论

1.如果内存足够，输入数据又满足相应的特点，那么可以采用线性时间排序

2.如果内存比较珍贵，那么各方面性能都好的快速排序是很好的选择

总结

本文的不妥之处，请各位读者包容和指正。