我的软考之路(六)——数据结构与算法(4)之八大排序

排序是编程的基础,在程序中会经常使用,好的排序方法可以帮助你提高程序运行的效率,所以学好排序,打好基础,对于程序的优化会手到擒来。无论你的技术多么强,如果没有基础也强不到哪去。

不多说了,我们直接进入今天的主题。

我的软考之路(六)——数据结构与算法(4)之八大排序

总有人说排序很难,但是我总觉得很简单,我们只需要了解基本思想就好了,通过简单的例子来加深理解。

1、直接插入排序

(1)简介:直接插入排序,从字面意思可以看出,直接插入数据完成排序。

(2)基本思想:在插入第i个数时,假设前i-1数已经排好序了,只需要将第i个数插入到i-1中,使得这i个数也是顺序的。

(3)例如:

我的软考之路(六)——数据结构与算法(4)之八大排序

2、希尔排序(Shell排序)

(1)简介:希尔排序又称为缩小增量排序,是对直接插入排序方法的改进。

(2)基本思想:将整个序列分成多个子序列,然后分别进行直接插入排序,直到整个序列中的所有数基本有序时,再对整体进行一次直接插入排序。

(3)例如:

我的软考之路(六)——数据结构与算法(4)之八大排序

3、简单选择排序

(1)简介:简单选择排序也叫直接选择排序,其实说白了跟直接插入排序的道理特别简单,效率低。

(2)基本思想:首先在 n个数中选择一个最小的数,并将它从中删除,作为新的一组数的第一个;再在剩下的数中选择最小的数,将它从中删除,作为新的一组数的第二个。。。。如此反复,直到排序完成,最后得到一组从小到大排序的数。

(3)例如:

我的软考之路(六)——数据结构与算法(4)之八大排序

4、堆排序

(1)简介:堆排序是一个相当有用的排序技术,特别适用于对大量的记录进行排序。同时,堆排序也是对简单选择排序的改进。

堆的定义:n个元素的序列{K1,K2,...,Kn}当满足下列关系时,称为堆:Ki≤K2i且Ki≤K2i+1或者Ki≥K2i且Ki≥K2i+1。注意:堆树必须是一颗完全二叉树。

(2)基本思想:利用堆积树这种数据结构所设计的一种排序,可以利用数组的特点快速的定位指定索引的元素。

最大堆:父结点大于或等于儿子结点

我的软考之路(六)——数据结构与算法(4)之八大排序

最小堆:父结点小于或等于儿子结点

我的软考之路(六)——数据结构与算法(4)之八大排序

(3)例如:

将序列{20,60,26,30,36,10}调整为递增序列。

1、首先将数据建立完全二叉树,填充规则是按层次遍历将数据一一填入,最后构建最小堆;

我的软考之路(六)——数据结构与算法(4)之八大排序

2、提取堆顶并调整删除队顶后的元素为新堆;

3、重复第2步,直到堆空;

我的软考之路(六)——数据结构与算法(4)之八大排序

4、每次提取的堆顶依次排序即为递增序列。

我的软考之路(六)——数据结构与算法(4)之八大排序

5、冒泡排序

(1)简介:冒泡排序,就跟水里的物体一样,小的往上浮,大的往下沉。

(2)基本思想:将数组垂直排列,取出最后一个元素逐个向上交换,得到大数(小数),继续步骤一的操作,直到排序完成。

(3)例如:

我的软考之路(六)——数据结构与算法(4)之八大排序

6、快速排序

(1)简介:快速排序是目前内部排序中速度最快的一种排序算法。

(2)基本思想:选取一个数据(通常是数组的第一个数)作为关键数据,然后将所有比它小的数都放在它前面,所有比它大的数都放在它后面,这个过程称为一趟快速排序,再从分开的部分选取基准数,进行分组划分,重复执行,直到完成。

(3)例如:

我的软考之路(六)——数据结构与算法(4)之八大排序

7、归并排序

(1)简介:归并排序又称为二路合并操作,使用合并操作完成排序的算法。

(2)基本思想:将两个或两个以上的有序表合并成一个新的有序表,最后将所有的有序表合成一个整体有序表。

(3)例如:

我的软考之路(六)——数据结构与算法(4)之八大排序

8、基数排序

(1)简介:前面介绍的排序方法都是对元素进行的,基数排序是对元组进行的。

(2)基本思想:从低位到高位依次对待排序的数进行分配和收集,经过d趟分配和收集,就可以得到一个有序序列。

(3)例如:

我的软考之路(六)——数据结构与算法(4)之八大排序

排序算法对比

我的软考之路(六)——数据结构与算法(4)之八大排序

总结

人处理图像的能力是最强的,相信你通过这一张张的图,你已经学会了这八种排序。

后续博客的更新列表,敬请期待。

我的软考之路(一)——开篇(已更新)

我的软考之路(二)——J2SE宏观总结(已更新)

我的软考之路(三)——数据结构与算法(1)之线性表(已更新)

我的软考之路(四)——数据结构与算法(2)之树与二叉树(已更新)

我的软考之路(五)——数据结构与算法(3)之图(已更新)

我的软考之路(六)——数据结构与算法(4)之八大排序(已更新)

我的软考之路(七)——数据结构与算法(5)之查找(已更新)