排序算法--归并排序和基数排序
前面几篇博客学习介绍了插入排序,交换排序,选择排序等排序算法。本篇博客将主要学习介绍归并排序和基数排序。学习完这两个算法,我们的排序算法就学完了。
1.归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
基本思路
归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。最简单的归并是直接将两个有序的子表合并称为一个有序表,即二路归并。
表的合并
这个非常简单,只要从比较二个数列的第一个数,谁小就先取谁,取了后就在对应数列中删除这个数。然后再进行比较,如果有数列为空,那直接将另一个数列的数据依次取出即可。
实现代码
//两个有序表的合并
void combine(int a[],int lena,int b[],int lenb)
{
int *c=new int[lena+lenb];//合并表
int ai=0,bi=0,ci=0;//各个数组下标,初始为0
//a,b数组第一个值对比,取小值放到c中
while(ai<lena&&bi<lenb)
{
if(a[ai]>b[bi])
{
c[ci]=b[bi];
bi++;
ci++;
}
else
{
c[ci]=a[ai];
ai++;
ci++;
}
}
//若a数组还剩元素,直接放到c数组里
while(ai<lena)
{
c[ci]=a[ai];
ai++;
ci++;
}
//若b数组还剩元素,直接放到c数组里
while(bi<lenb)
{
c[ci]=b[bi];
bi++;
ci++;
}
//输出结果
for(int i=0;i<lena+lenb;i++)
cout<<c[i]<<" ";
}
可以看出来,有序表的整合还是比较容易的,而且效率挺高的,可以达到O(n)。
我们可以利用这个把一个无序表分为两组A,B,再把A,B各自又分为两组,以此类推,直到最后分出来的每组只剩下一个元素,此时子表是有序的(只有一个元素)。然后在两两合并,即最初无序表的有序表。
示例图:
实现代码
//合并有序数列a[first...mid]和a[mid+1...last], a[first...mid]和a[mid+1...last]一定为有序
void Combine(int a[], int first, int mid, int last)
{
int *temp=new int[last-first+1];//临时记录数组
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;
//两两对比
while (i <= m && j <= n)
{
if (a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
//将剩下的记录放到temp中
while (i <= m)
temp[k++] = a[i++];
while (j <= n)
temp[k++] = a[j++];
//将temp复制回a
for (i = 0; i < k; i++)
a[first + i] = temp[i];
delete [] temp;//释放temp内存
}
void mergesort(int a[], int first, int last)
{
if (first < last)
{
int mid = (first + last) / 2;
mergesort(a, first, mid); //左边有序
mergesort(a, mid + 1, last); //右边有序
Combine(a, first, mid, last); //再将二个有序数列合并
}
}
效率分析
归并排序的效率是比较高的,设数列长为N,将数列分开成小数列一共要logN步,每步都是 一个合并有序数列的过程,时间复杂度可以记为O(N),故一共为O(N*logN)。因为归并排序每次都是在相邻的数据中进行操作,所以归并排序在 O(N*logN)的几种排序方法(快速排序,归并排序,希尔排序,堆排序)也是效率比较高的。
归并排序过程中,每一趟都需要有一个辅助空间来存储两个子序列表归并的结果,在该排序完毕后释放,所以总的辅助空间复杂度为O(n),显然他不是就地排序。归并排序是一个稳定排序。
2.基数排序
基本思想
最终排序结果为12 23 29 38 44 57 64 75 82 98
#define MAXSIZE 10 //桶里最大放多少值
//桶的结构
struct node
{
int key[MAXSIZE];//桶里的数据
int count;//桶里数据的个数
node()
{
count=0;//count为0表示桶内没数字
}
};
//各个位的值获取
int GetNumInPos(int num,int pos)
{
int temp = 1;
for (int i = 0; i < pos - 1; i++)
temp *= 10;
return (num / temp) % 10;
}
//基数排序
void RadixSort(int a[],int len)
{
//获取a数组的最大值来确定装几次桶
int max=0;
for(int i=0;i<len;i++)
{
if(a[i]>max)
max=a[i];
}
//计算装桶次数d
int d=1;
int temp=10;
while(true)
{
if(max/temp>0)
{
d++;//次数加一
temp*=10;
}
else
break;
}
node head[10];//10个桶
int pos=1;//获取哪个位上的树,1表示个位
while(d>=pos)
{
//依次把数组的数字放进相应桶里
for(int i=0;i<len;i++)
{
int id=GetNumInPos(a[i],pos);
head[id].key[head[id].count]=a[i];
head[id].count++;
}
//依次从桶里去除数据赋值给a数组
int num=0;
for(int i=0;i<10;i++)
{
if(head[i].count!=0)
{
for(int j=0;j<head[i].count;j++)
{
a[num]=head[i].key[j];
num++;
}
//清空桶
head[i].count=0;
}
}
pos++;
}
}
空间复杂度:O(10n) (10表示0~9,用于存储临时的序列)
稳定性:稳定
附上源代码地址:https://github.com/longpo/algorithm/tree/master/Combine
总结
至此,八大排序算法就学完了。
通常可以按平均时间将排序分为3类
1.平方阶O(n^2)排序,一般称为简单排序,如直接插入排序,直接选择排序和冒泡排序
2.线性对数阶O(nlog2(n))排序,如希尔排序,快速排序,堆排序和归并排序
3,。线性阶O(n)排序,如基数排序
各种排序的性能
没有哪一种排序方法是绝对好的。每一种排序方法都有优缺点,适合于不同的环境,因此,在实际应用中,应根据具体情况来做选择。