排序算法--归并排序和基数排序

        前面几篇博客学习介绍了插入排序，交换排序，选择排序等排序算法。本篇博客将主要学习介绍归并排序和基数排序。学习完这两个算法，我们的排序算法就学完了。

 

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.基数排序

 

基本思想

      基数排序（以整形为例），将整形10进制按每位拆分，然后从低位到高位依次比较各个位。主要分为两个过程：

(1)分配，先从个位开始，根据位值(0-9)分别放到0~9号桶中（比如53,个位为3，则放入3号桶中）

(2)收集，再将放置在0~9号桶中的数据按顺序放到数组中

重复(1)(2)过程，从个位到最高位

例如：

把数组a[10]={75,23,98,44,57,12,29,64,38,82}升序排列,

 

 最终排序结果为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(dn)(d即表示整形的最高位数)

空间复杂度：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)排序，如基数排序

各种排序的性能

 

没有哪一种排序方法是绝对好的。每一种排序方法都有优缺点，适合于不同的环境，因此，在实际应用中，应根据具体情况来做选择。

评论

1 楼 fggsgigomkg 2015-04-05  

基数排序说的很好，理解了