前面几篇博客学习介绍了插入排序,交换排序,选择排序等排序算法。本篇博客将主要学习介绍归并排序和基数排序。学习完这两个算法,我们的排序算法就学完了。
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)排序,如基数排序
各种排序的性能
没有哪一种排序方法是绝对好的。每一种排序方法都有优缺点,适合于不同的环境,因此,在实际应用中,应根据具体情况来做选择。
相关推荐
经典排序算法 - 基数排序Radix sort 经典排序算法 - 鸽巢排序Pigeonhole sort 经典排序算法 - 归并排序Merge sort 经典排序算法 - 冒泡排序Bubble sort 经典排序算法 - 选择排序Selection sort 经典排序算法 - ...
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
8.12-8.19_冒泡_选择_插入_希尔_快速_归并_基数_堆排序_排序算法Swift代码及UI演示
此文件为数据结构中的九种排序算法,包含一些排序方法的过程,其九种排序包括:直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,选择排序,堆排序,归并排序,基数排序!
十大经典排序算法 ... (2)排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部...常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序
C语言实现常见排序算法。编译环境:VS2010。 包括: 冒泡排序 快速排序 直接插入排序 Shell排序 ...归并排序(递归和非递归两种) 桶式排序 基数排序:顺序和静态队列两种方法 索引排序(采用简单插入排序)
试通过随机数据比较归并排序、基数排序各算法的关键字比较次数和关键字移动次数。 (1)待排序表的表长不小于100;其中的数据要用伪随机数产生程序产生;至少要用5组不同的输入数据作比较;比较的指标为有。关键字...
采用c++描述了各种排序算法,包括选择排序 冒泡排序 插入排序 基数排序 快速排序 归并排序 。实验内容 1、创建排序类。 2、提供操作:选择排序、冒泡排序、插入排序、*基数排序、*快速排序、*归并排序。 3、*能够...
各种排序算法的实现函数:包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序。 查找最大最小值函数 findMinMax:在给定数组中查找最大值和最小值。 计算平均值...
快速排序、归并排序、基数排序等排序算法比较,比较时间性能,采用C++语言实现。。。
在这份文档中,我用C语言实现了排序算法的多种方法,包括插入排序、选择排序、冒泡排序、希尔排序、归并排序、快速排序、桶排序和基数排序。这些算法可以帮助我们对数据进行有效的排序和整理,以便更好地处理和分析...
选择排序,冒泡排序,插入排序 基数排序,快速排序,归并排序
各种排序算法(插入 希尔 归并 快速 堆排序 基数排序 选择 冒泡等等)
这样会不会太邪恶了 基数排序根本没有关键字比较 题目有错滴
C_算法源码(冒泡排序+基数排序+插入排序+快速排序+归并排序 C_算法源码(冒泡排序+基数排序+插入排序+快速排序+归并排序 C_算法源码(冒泡排序+基数排序+插入排序+快速排序+归并排序 C_算法源码(冒泡排序+基数排序+...
排序算法 - 快速排序(Insert Sort) - 希尔排序(Shell Sort) - 冒泡排序(Bubble Sort) - 快速排序(Quick Sort) - 选择排序(Selection Sort) - 堆排序(Heap Sort) - 归并排序(Merge Sort) - 箱排序(Bin Sort) - 基数...
关于c#的一些算法 选择排序 冒泡排序 快速排序 插入排序 希尔排序 归并排序 基数排序 计数排序。。。
数据结构归并排序、基数排序讲解分析 word格式的
八种排序算法原理及Java实现( 冒泡排序+快速排序直接插入排序+希尔排序+选择排序+归并排序+基数排序)
10种排序算法代码+综合比较代码(直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序、折半插入排序、2路插入排序),其中不仅有各种排序算法的代码,还包含10种代码在关键字...