对排序算法的复习——插入排序、希尔排序、堆排序、归并排序、快速排序、桶式排序、外部排序。
一、最简单的插入排序
插入排序由N-1趟排序组成,对于p=1到N-1趟,插入排序保证从0到位置p上的元素为已排序状态。什么意思呢,比如说我们要对如下一组整数进行插入排序(排序后要从小到大):
34, 8, 64, 51, 32, 21
当排序第一趟的时候,我们比较前两个数,也就是34和8,我们发现,34大于8,那么第一趟排序后的结果就是:
8, 34, 64, 51, 32, 21
当排序第二趟的时候,我们比较前三个数,也就是8,34和64,我们将64与34比较,发现64大于34,那么这趟排序就结束了(因为经过第一趟排序,我们知道34一定比前一个数大,也就是排序算法的定义规则),那么第二趟排序后的结果就是:
8, 34, 64, 51, 32, 21
当排序第三趟的时候,我们比较四个数,也就是将第四个数51,与第三位数比较,我们发现51小于64,既然小于,那么再让51与34比较,发现51大于34,那么到此,第三趟排序结束了,所以第三趟排序后的结果就是:
8, 34, 51, 64, 32, 21
以此类推,一直进行到第5趟(这些数的长度减一)为止,排序算法就结束了,数也就排序完了。这就是排序算法。
插入排序算法的性能不高,算是比较耗时的了,我们可以想想,因为不管怎么样都要进行N-1趟排序,那么肯定耗时了。我的git库里面有代码:https://github.com/hejiawang/Arithmetic.git 感兴趣的道友可以帮我指正一下。
对于给出的示例的完整的排序过程如图:
核心代码:
public static void insertionSort(int[] array) { int j; for (int i = 1; i < array.length; i++) { int temp = array[i]; for (j = i; j > 0 && temp < array[j - 1]; j--) { array[j] = array[j - 1]; } array[j] = temp; } }
二、希尔排序
希尔排序要使用一个增量序列(稍后就会明白),在使用增量h的一趟排序之后,对于每一个位置i 我们都有a[i] <= a[i+h],所以相隔h的元素都被排序了。
挺不好理解的,举个例子,比如我们要对如下的13个数从小到大进行希尔排序,
81, 94, 11, 96, 12, 35, 17, 95, 28, 58, 41, 75, 15
首先我们使用增量序列5进行排序,什么意思呢?就是在上面的这个数列中找第五个数,也就是12,让12这个数的左右两边的数进行比较,比如我们将81和35进行比较,81大于35,那么我们就将这两个数调换位置,然后94和17比较,11和95比较,96和28比较,凡是坐边大于右边的,我们都将这两个数调换位置,经过这样排序之后,我们能够保证,以12为中心的左右两边的数,第一个小于小于第5+1个数,第2个数小于5+2个数,以此类推;这次排序之后,从第五位也就是数字12开始数,在数5个数,也就是28,让12与58比较,35与41比较。。。。重复上一个步骤;然后从28开始在数5个数也就是15,发现15后面没数了。那么第一次的希尔排序就算结束了。
读起来感觉希尔排序挺麻烦的,但是,希尔排序确实挺麻烦的。。。^_^ 但是如果选对了增量序列希尔排序的效率还是和可观的。难就难在怎么选择增量序列。
上面的例子经过希尔排序的各个步骤如下:
核心代码:
public static void shellSort(int[] array) { int j; for (int gap = array.length / 2; gap > 0; gap /= 2) { for (int i = gap; i < array.length; i++) { int tmp = array[i]; for (j = i; j >= gap && tmp < array[j - gap]; j -= gap) { array[j] = array[j - gap]; } array[j] = tmp; } } }
三、堆排序
堆排序到现在还不太明白。。。不做记录了。以后机缘巧合弄明白了,在记下来。。。。
四、归并排序
归并排序就是将一个数组分成两份(也可以多分弄成多路归并排序),将两个数组的第一个数进行比较,把较小的那个数移到一个新的空数组中,然后重复这个操作,最后得到的新数组,就是一个经过排序的数组了。这就是归并排序,在外部排序中用归并排序的思想比较多,下面给出一个示例图:
五、快速排序
快速排序对Java货c++的基本类型的排序特别有用,快速排序就是在一个数组中选取一个数作为枢纽元,在这些数中,凡是比这个数小的,放在一边,比这个数大的放一边,然后在这两边中在按这种方式排序下去,知道排序完成。效率很好。
六、桶式排序
要使用桶式排序,就要知道数组中最大的数是多少,然后构建一个比这个数大一的一个空数组Array,把这个数组的各个项初始化为0,于是,当读到一个数a时,就在数组的Array[a]位置上增一,在所有的输入数据读入后,扫描数组Array,打印出排序后的表,就是经过排序的数了。。很有意思的一种排序:
七、外部排序
所谓外部排序就是没有内存的概念了,但是可以用磁带啊什么的,其他的思想就和归并排序一样了,还有多路归并排序,就是把原来的数组分割成对份,思想就是这样了,不重复了。。。
相关推荐
课程内容如下: 八大排序的详细讲解,求解递归式的复杂度,常用的几种算法和典例,贪心有活动选择,部分背包,迪杰斯特拉等,动规的有装配线调度,最大子段和,0-1背包,最长公共子序列(LCS),最长回文子序列的...
今天看到了一个算法,感觉以前学过的呢些算法都忘得差不多了,下午复习复习,忘记的上网搜搜,下面的全部编译通过,又学习了点东西。
昨晚上开始总结了一下常见的几种排序算法,由于之前我已经写了好几篇排序的算法的相关博文了现在总结一下的话可以说是很方便的,这里的目的是为了更加完整详尽的总结一下这些排序算法,为了复习基础的东西,从冒泡...
这个是很经常用到的,之前的项目中也有,而且对于几种排序我们都是用的是asort arsort 等PHP原生函数,没有自己去实现,所以就对一下的几个函数进行总结,这个会不断的进行补充,自己也可以好好的复习和总结
用C/C++复习一下常见的几种排序算法。是自己一行一行敲出来的代码。
讨论并比较所有通用的排序算法。对以下四种算法详细地进行了分析:插入排序、希尔排序、堆排序以及快速排序。堆排序平均情形运行时间的分析对于这一版来说是新的内容。本章末尾讨论了外部排序。 第8章讨论不相交集...
一、教材内容 使用教材《数据结构》C语言版 严蔚敏,清华大学出版社。 章节 去掉 第5、8、11、12...掌握几种说法 数据元素是…,数据项是… 数据结构中关系的四种基本结构 数据结构的形式定义 算法的五个特征
一、教材内容 使用教材《数据结构》C语言版 严蔚敏,清华大学出版社。 章节 去掉 第5、8、11、12...掌握几种说法 数据元素是…,数据项是… 数据结构中关系的四种基本结构 数据结构的形式定义 算法的五个特征
平衡二叉排序树的在平衡因子绝对值等于2时开始调整到绝对值为1或0,在平衡因子绝对值为2时,二叉排序树会出现四种不同的情况的树形,因此这时需要分别单独讨论来降低平衡因子。 1.2.7 平衡二叉树的调整方法 平衡...
自1995年首次发布以来,Java编程语言作为一种教学语言变得日益重要,现在已经成为初级计算课程斯坦福大学的标准语言。Java语言可以让学生编写高度交互式程序,这充分激发了他们的学习兴趣。但Java语言很复杂,老师和...
11.10 复习题 11.11 编程练习 第12章 搜索与排序 12.1 搜索 12.2 排序 12.3 评估算法效率 12.4 使用数据文件 12.5 小结 12.6 复习题 12.7 编程练习 第13章 数组与ArrayList类 13.1 ArrayList类回顾 13.2 HashMap类 ...
06_学员学习标准_排序及问题抛出 07_数组做函数参数退化问题剖析_传智扫地僧 08_数据类型基础提高 09_数据类型引申和思考 10_变量本质剖析和内存四区模型引出_传智扫地僧 11_c的学习重理解到位_对初学者_传智扫地僧 ...
(54) 在下列几种排序方法中,要求内存量最大的是(D) 注:要牢记,书中没有提到。 A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序 (55) 在设计程序时,应采纳的原则之一是(A) 注:和设计风格有关 A. 程序结构应有...
easy题目,喜欢考排序,链表,树(红黑树、二叉排序树、完全二叉树、B+树区别) Java基础:集合类、HashMap/HashTable/CurrencyHashMap这几个的区别以及不JDK版本的区别、其他面向对象的语法,NIO,BIO,AIO; JVM:...
07-MR程序的几种提交运行模式.avi 08-YARN的通用性意义.avi 09-yarn的job提交流程.avi 第四天 常见mr算法实现和shuffle的机制 01-复习.avi 02-hadoop中的序列化机制.avi 03-流量求和mr程序开发.avi 04-...
它包括对数据的采集、整理、存储、 分类、检索、排序、统计、维护、传输等一 系 列活动。 通常将数据处理分为两个操作层次:一 是数据采集、分类、组织、编码、存储、检 索、传输、维护等基本操作,这些基本操作 ...
07-MR程序的几种提交运行模式.avi 08-YARN的通用性意义.avi 09-yarn的job提交流程.avi 第四天 常见mr算法实现和shuffle的机制 01-复习.avi 02-hadoop中的序列化机制.avi 03-流量求和mr程序开发.avi 04-...
实验一 复习C++有关知识 实验目的: 通过实验掌握下列知识: 1、复习C++有关基本知识; 2、熟悉VC编程、编译和调试环境; 内容及步骤: 编写一个类Complex,定义复数的加法、减法、乘法和除法运算,...