- 浏览: 887908 次
- 性别:
- 来自: 武汉
文章分类
最新评论
-
小宇宙_WZY:
膜拜一下大神,解决了我一个大问题,非常感谢 orz
【解惑】深入jar包:从jar包中读取资源文件 -
JKL852qaz:
感谢,遇到相同的问题!
【解惑】深入jar包:从jar包中读取资源文件 -
lgh1992314:
为什么java中调用final方法是用invokevirtua ...
【解惑】Java动态绑定机制的内幕 -
鲁曼1991:
说的都有道理,protected只能被同一级包的类所调用
【解惑】真正理解了protected的作用范围 -
鲁曼1991:
...
【总结】String in Java
1、基本概念介绍
(1) 如果待排序列中有两个相同的关键字 Ki = Kj,其顺序是Ki在Kj之前。如果经过排序之后,Ki 和 Kj的顺序颠倒了,则说明这个排序方法是不稳定 的。否则则是稳定 排序。
(2) 在内存中就可以完成的排序过程,称为内部排序 。如果待排数据量很大,内存不够容纳全部数据,在排序过程中必须对外存进行访问,则叫做外部排序 。
实际上,由于数据量级别不同。排序的方法会有很大的改变,思考排序效率的角度也不一样。这个专题系列未经特殊注明,都属于内部排序方法。
2、直接插入排序 O(N^2)
将一个记录插入到已经排好序的有序表中,从而得到一个新的,记录数增1的有序表。下面通过一个例子来说明这个排序流程:
待排序列: 49, 38 , 65 , 97, 76 , 13, 27 ,49
插入49: 49
插入38: 38, 49
插入65: 38, 49, 65
插入97: 38, 49, 65, 97
插入76: 38, 49, 65, 76, 97
插入13: 13, 38, 49, 65, 76, 97
插入27: 13, 27, 38, 49, 65, 76, 97
插入49: 13, 27, 38, 49, 49, 65, 76, 97
#include<iostream.h> /****************************** * 直接插入排序 Straight Insertion Sort * ******************************/ class SISortion{ public: //递增稳定排序 static void inc_sort(int keys[], int size); }; void SISortion:: inc_sort(int keys[], int size){ //记录当前要插入的key int post_key; //从第二个数据开始 for(int i=1;i<size;i++){ post_key=keys[i]; int j; //将比post_key要大的前面所有的key依次后移一位 for(j=i-1;j>=0;j--){ if(post_key<keys[j]) keys[j+1]=keys[j]; else break; } //将post_key插入到合适位置 keys[j+1]=post_key; } //打印排序结果 for(int k=0;k<size;k++) cout<<keys[k]<<" "; cout<<endl; } //Test SISortion void main(){ int raw[]={49,38,65,97,76,13,27,49}; int size=sizeof(raw)/sizeof(int); SISortion::inc_sort(raw,size); }
很显然,直接插入排序算法的时间复杂度为O(N^2) 。但是不需要额外的存储空间,因此空间复杂度为O(1) 。而且直接插入排序是稳定 的。
3、折半插入排序 O(N^2)
折半插入排序和直接插入排序的不同点在“查找”上。在有序关键字序列中,每次插入的关键字采用折半查找的方法来定位。虽然折半查找的时间复杂度为O(logN),但定位后循环数据后移仍然要花费O(N)的代价。因此时间复杂度仍然是O(N^2),空间复杂度为O(1),排序是稳定的。
#include<iostream.h> /****************************** * 折半插入排序 Binary Insertion Sort * ******************************/ class BISortion{ public: static void inc_sort(int keys[],int size); }; void BISortion :: inc_sort(int keys[],int size){ int post_key; for(int i=1;i<size;i++){ post_key=keys[i]; //折半查找 int low=0,high=i-1; while(low<=high){ int middle=(low+high)/2; if(post_key<keys[middle]) high=middle-1; else low=middle+1; } //移动位置 for(int j=i-1;j>=high+1;j--) keys[j+1]=keys[j]; keys[high+1]=post_key; } for(int k=0;k<size;k++){ cout<<keys[k]<<" "; } cout<<endl; } //Test BISortion void main(){ int keys[]={49,38,65,97,76,13,27,49}; int size=sizeof(keys)/sizeof(int); BISortion::inc_sort(keys,size); }
4、希尔排序(N*logN)
希尔排序(Shell's Sort)又称缩小增量排序(Diminishing Increment Sort),它也是一种插入排序,但是在时间效率上比前面两种有较大的改进。
对本身就是“正序”的关键字序列,直接插入排序的时间复杂度将降低到O(n)。由此可以设想,对"基本有序"的序列进行直接插入排序,效率将大大提高。希尔排序方法就是基于这个思想提出来的,其基本思想就是:先将整个待排序列分割成若干个子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,在对全体记录进行一次直接插入排序。
我们用下图的例子来看看希尔排序
很明显,希尔排序对每一趟增量子序列都是一种直接插入排序。但是每一趟排序中记录关键字都是和同一子序列中前一个记录的关键字进行比较(子序列相邻关键字之间的位置相差一个增量),因此关键字较小的记录不是一步一步向前挪动,而是根据增量大小跳跃式的前进。当序列基本有序的时候,第三趟增量为1的希尔排序就是直接排序,这时只需要比较和移动少量的记录即可。
#include<iostream.h> /****************** * 希尔排序 Shell Sort * ******************/ class ShellSort{ public: //希尔递增排序 static void inc_sort(int keys[],int size); }; void ShellSort :: inc_sort(int keys[],int size){ int increment=size; //增量 do{ increment=increment/3+1; //增量逐步减少至1 int post_key; for(int i=increment;i<size;i++){ if(keys[i]<keys[i-increment]){ post_key=keys[i]; for(int j=i-increment;j>=0&&post_key<keys[j];j=j-increment){ keys[j+increment]=keys[j]; } keys[j+increment]=post_key; } } cout<<"一趟希尔排序(增量="<<increment<<"):"; for(int k=0;k<size;k++) cout<<keys[k]<<" "; cout<<endl; }while(increment>1); } void main(){ int raw[]={49,38,65,97,76,13,27,49}; int size=sizeof(raw)/sizeof(int); ShellSort::inc_sort(raw,size); }
希尔排序的性能是个很复杂的问题,主要与增量的取值有关。到目前为止,还没有人求的最好的增量结果。但是大量数据实验表明,布尔排序的时间复杂度趋近于O(N*logN) 。但不管增量如何取值,最后一趟希尔排序的增量必须为1才能真正得到有序序列。而且希尔排序是不稳定的。
发表评论
-
★经典问题—链表中的环问题
2010-06-29 14:43 4397转载:http://www.cppblog.com ... -
★经典问题—元素选择问题
2010-05-24 10:53 3303元素选择问题 : 给定线性序集中n个元素和一个整数k( ... -
【串和序列处理 8】最长平台问题
2010-04-28 16:41 36301、经典最长平台算法 已知一个已经从小到大 ... -
【排序结构7】 基数排序
2010-04-20 16:17 4507《桶排序 》中我们能够看到,数据值的范围越大,可能需要桶的个 ... -
【排序结构6】 桶排序
2010-04-19 20:28 22848从《基于比较的排序结构总结 》中我们知道:全依赖“比较”操作的 ... -
【排序结构5】 基于比较的内部排序总结
2010-04-18 16:15 6688★ 基于“比较”操作的内部排序性能大PK ... -
【排序结构4】 归并排序
2010-04-17 16:29 3262归并排序 O(N*logN) 是另一种效率很高的排序方法。&q ... -
【排序结构3】 选择排序
2010-04-14 21:10 3563(1) 简单选择排序 O(N^2) 一趟简单选择排序 ... -
【排序结构2】交换排序
2010-04-14 11:04 25511、起泡排序 O(N^2) ... -
【串和序列处理 7】LIS 最长递增子序列
2010-03-25 16:37 5774LIS: 给定一个字符串序列S={x0,x1,x2,.. ... -
【串和序列处理 6】LCS 最长公共子序列
2010-03-23 17:38 8764LCS:又称 最长公共子序列。 其中子序列(subse ... -
【串和序列处理 5】KMP子串匹配算法
2010-03-22 19:59 9023模式匹配: 在字符串 ... -
★经典问题—欧几里得求最大公约数
2010-03-20 19:21 3324问题:快速求取正整数a,b的最大公约数? ... -
【串和序列处理 4】Suffix Trie 子串匹配结构
2010-03-20 15:15 9038Suffix Trie : 又称后 ... -
【串和序列处理 3】Trie Tree 串集合查找
2010-03-18 13:40 17563Trie 树, 又称字典树,单词查找树。它来源于retr ... -
【串和序列处理 2】字符串编辑距离算法
2010-03-15 08:45 11063我们来看一个实际应用。现代搜索技术的发展很多以提供优质、高效的 ... -
【串和序列处理 1】PAT Tree 子串匹配结构
2010-03-14 19:10 11249Patricia Tree 简称PAT tree ... -
【查找结构6】动态查找树比较
2010-03-12 13:32 11218我们这个专题介绍的动态查找树主要有: 二叉查找树(BST),平 ... -
【查找结构4】红黑树 [RBT]
2010-03-10 10:58 10501大部分转载:http://yanglongylj.blog.1 ... -
【查找结构5】多路查找树/B~树/B+树
2010-03-09 11:56 18104在前面专题中讲的BST、A ...
相关推荐
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
数据结构排序算法中的折半插入排序,又称二分法,是对基本插入排序的一种改进,比普通的插入排序要快
用函数实现直接插入排序,并输出每趟排序的结果. Input 第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 Output 每行输出一趟排序结果,数据之间用一个空格分隔 Sample Input 10 ...
用函数实现折半插入排序,并输出每趟排序的结果. Input 第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 Output 每行输出一趟排序结果,数据之间用一个空格分隔 Sample Input 10 5...
数据结构 综合排序 冒泡排序 直接插入排序 快速排序 希尔排序,完整的代码,有每种排序时间的比较
数据结构(c语言版)严蔚敏 吴伟民编著 中直接插入排序、折半排序、shell排序、冒泡排序、快速排序、选择排序、堆排序的实现、归并排序,使用c语言实现
数据排序中的一种最基本的排序算法 比较次数个移动次数约为n的平凡除4, 时间复杂度约为0(n的平凡)
本事例中将插入排序和选择排序合并在一个程序里,直观明了,程序简单易懂,是学习数据结构很好的互补
冒泡排序、快速排序、简单插入排序、希尔排序、简单选择排序、堆叠排序六种数据结构必考的排序方式理解
binary sort,二分法查找,binary search, 二分法排序,merge sort 混合排序,shell sort 希尔排序,insertion sort 插入排序。数据结构 data structure
数据结构中的排序方法 属于内部排序 直接插入排序
六种内部排序算法比较:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。包含实验报告和源代码设计。
插入排序之直接插入排序.cpp
直接插入排序 冒泡排序 快速排序 直接选择排序 堆排序 二路归并排序 C#源代码 使用C#实现的数据结构中的排序算法
c++实现的线性表排序算法 插入排序,希尔排序,冒泡排序,快速排序,堆排序,归并排序等
《数据结构》严蔚敏版 折半插入排序
数据结构课程中直接插入排序的示例程序 完整示例
数据结构用直接插入的方式排序,编写一个程序实现直接插入排序算法。
现在有 1 亿的数据,请选择合适的排序算法与数据结构,在有限的时间内完成进行排序。 选择排序算法、冒泡排序算法和插入排序算法的时间复杂度为O(n2),写法简单,逻辑易懂,但算力性价比不高,不适用于数据量较大...