《算法导论》学习(一)---- 插入排序和归并排序
《算法导论》学习(七)----堆排序和优先队列(C语言)
《算法导论》学习(八)----快速排序(C语言)
《算法导论》学习(九)----为什么比较排序算法时间复杂度的下界是确定的?
《算法学习》学习(十)----计数排序,基数排序,桶排序(C语言)
文章目录
- 系列文章
- 前言
- 一、线性时间排序
- 1.什么是比较排序?
- 2.为什么比较排序不能是线性时间排序?
- 3.线性时间排序算法
- 二、计数排序
- 1.C语言代码
- 2.算法逻辑
- (1)前提假设
- (2)基本思想
- (3)算法特点
- 3.算法时间性能分析
- 三、基数排序
- 1.C语言代码
- 2.算法逻辑
- (1)前提假设
- (2)基本思想
- 3.算法时间性能分析
- 四、桶排序
- 1.C语言代码
- 2.算法逻辑
- (1)假设前提
- (2)基本思想
- (3)算法特点
- 3.算法时间性能分析
- 五、线性时间排序一定好吗?
- 1.时间角度
- 2.空间角度
- 3.结论
- 总结
前言
本文主要讲解了三大线性时间排序:
1.计数排序
2.基数排序
3.桶排序
给出了它们的C语言代码和算法逻辑
一、线性时间排序 1.什么是比较排序?
比较算法有一个性质:在排序的最终结果中,各元素的次序依赖于它们之间的比较
比如:
1.插入排序
2.冒泡排序
3.归并排序
4.堆排序
5.快速排序
2.为什么比较排序不能是线性时间排序?
在前面的文章我们证明了如下的结论:
对包含n个元素的输入序列来说,任何比较排序在最坏情况下都要经过 Ω ( n l g n ) \Omega(nlgn) Ω(nlgn)次比较
因此比较排序算法不可能是线性时间排序算法
3.线性时间排序算法比如有:
1.计数排序
2.基数排序
3.桶排序
这些算法它们都不是比较排序算法,它们得到正确的顺序不是通过比较,而是通过计算来进行的。
都采用了空间换时间的算法理念
二、计数排序 1.C语言代码#include
#include
#include
//输入的规模
#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 8_1,8_2,8_3 81,82,83”,那么B输出时也是:“ 8 1 , 8 2 , 8 3 8_1,8_2,8_3 81,82,83”
3.算法时间性能分析
当
k
=
O
(
n
)
,
n
为输入规模时,算法的运行时间为
T
(
n
)
=
Θ
(
n
)
。
当k=O(n),n为输入规模时,算法的运行时间为T(n)=\Theta(n)。
当k=O(n),n为输入规模时,算法的运行时间为T(n)=Θ(n)。
但是时间复杂度的常数项比较大。
#include
#include
#include
//输入的规模
#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
)
=
Θ
(
n
)
d为常数且k=O(n)时,基数排序的时间代价是线性时间代价,T(n)=\Theta(n)
d为常数且k=O(n)时,基数排序的时间代价是线性时间代价,T(n)=Θ(n)
但是时间复杂度的常数项比较大。
即每一次循环的用时比快速排序要长,但是循环的次数小于快速排序。
注意:
该代码中涉及到了链表的数据结构,下面代码中的链表仅是针对桶排序写的,不是一般性的链表 *** 作函数。
#include
#include
#include
#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.算法时间性能分析算法的时间分析涉及复杂的概率分析,这里不做具体分析
那么结论是:
桶的大小的平方和与总的元素数呈线性关系,桶排序的代价在线性时间内完成
桶的大小的平方和与总的元素数呈线性关系,桶排序的代价在线性时间内完成
桶的大小的平方和与总的元素数呈线性关系,桶排序的代价在线性时间内完成
线性时间排序的循环次数比比较时间排序少,但是每一次循环花费时间更多
2.空间角度线性时间排序运用了空间换时间的思路,需要大量的额外空间来减少循环次数
3.结论1.如果内存足够,输入数据又满足相应的特点,那么可以采用线性时间排序
2.如果内存比较珍贵,那么各方面性能都好的快速排序是很好的选择
总结
本文的不妥之处,请各位读者包容和指正。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)