Jack Frost

数据结构与算法-冒泡、插入、选择算法优化写法(Java描述)

排序是我们经常要遇到的问题,而在编程中,一些基本排序算法是程序员必须会的基础。所以本博主根据自己的学习过程、优化算法的过程来给大家呈现一下一些排序算法的思路。

文章结构:1.排序总述,分类;2.冒泡排序的优化讲解;3.直接插入排序最优解的讲解;4.简单选择排序最优解讲解。


一、排序总述:(由于第一次写排序,先来个总述吧)

排序定义:使得序列成为一个按关键字而有序的序列。

排序的稳定性:原因:排序不仅针对主关键字,如果对于次关键字,因为待排序的记录序列中可能存在两个或两个以上的关键字相等的记录,排序结果就可能出现不唯一的情况。针对某些关键字项相同的项。

内排序与外排序:这里写图片描述

其中,冒泡排序和快速排序属于交换排序;简单选择排序和堆排序属于选择排序;直接插入排序和希尔排序属于插入排序。而我下面即将讲的三种排序算法都是一个划分有序区和无序区的排序算法(这个是很关键的思想喔)。


二、冒泡排序的优化讲解:

基本思路:两两比较相邻记录的关键字项,如果反序则交互,直到没有反序的记录为止。

形象过程如图(此图取自大话数据结构):

这里写图片描述

像这样遍历序列,从尾部开始把较小的值不断往前比较交换位置放到头部就是一个冒泡的过程。而我给的例子就是把较大的值不断往后冒泡。

普通冒泡排序版本

我们可以通过代入数据看这一过程,就会发现这样的写法是很多余的。比如{2,1,3,4,5,6,7,8,9},当i=1时,交换了2和1,序列已经有序,但是算法仍会执行后面的,也就是把i=2到i=9都执行了一遍,这就显得无聊多余臃肿了吧。所以我们有一个更好的思路去优化他们。

优化思路:就是上面的例子那样,他们交换一个位置排好队后,判断后面是不是已经排序好了,如果排序好了,也就不用再排了嘛,这样不就减低了冒泡的时间复杂度了吗?

优化代码如下:(给出一个完整的java代码例子)

此优化的冒泡排序时间复杂度为:还是n的2次方。当时运行次数为:n(n-1)/2次。


三、直接插入排序最优解的讲解(小数组排序中性能最好的排序算法

基本思路:将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表,通过对未排序的数据执行逐个插入至合适位置而完成排序工作。

做法过程:(1)将整个待排序序列划分为有序区和无序区,初始化有序区为待排序记录序列中的第一个,无序区包括所有剩余的待排序记录;(2)无序区的第一个记录插入到有序区的合适位置,无序区减一个记录,有序区加一个记录;(3)不断重复(2),直至无序区没有记录为止。

优化代码完整给出:


四、简单选择排序最优解讲解:

基本思路:在排序时找到合适的关键字再做交换,并且只移动一次就完成相应的关键字的排序定位。

做法:在要排序的一组数中,选出最小(或者最大)的一个数与第1个位置的数交换;然后在剩下的数当中再找最小(或者最大)的与第2个位置的数交换,依次类推,直到第n-1个元素(倒数第二个数)和第n个元素(最后一个数)比较为止。

优化代码完整给出:


好了,数据结构与算法-冒泡、插入、选择算法优化写法(Java描述)讲完了。欢迎在下面指出错误,共同学习!

转载请注明:【JackFrost的博客】

更多内容,可以访问JackFrost的博客

本博主最近会一直更新Java知识、数据结构与算法、设计模式的文章(因为最近在学习,哈哈哈),欢迎关注。

码字很辛苦,转载请注明来自JackFrost《数据结构与算法-冒泡、插入、选择算法优化写法(Java描述)》

Leave a Reply

Your email address will not be published. Required fields are marked *