排序算法--归并排序和基数排序
前面几篇博客学习介绍了插入排序，交换排序，选择排序等排序算法。本篇博客将主要学习介绍归并排序和基数排序。学习完这两个算法，我们的排序算法就学完了。
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)排序，如基数排序
各种排序的性能
没有哪一种排序方法是绝对好的。每一种排序方法都有优缺点，适合于不同的环境，因此，在实际应用中，应根据具体情况来做选择。
上一篇： java实现常用的八种内排序方法
下一篇： MySQL 5.1.47 GA 发布