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

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

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

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

 

1、直接插入排序

 

（1）简介：直接插入排序，从字面意思可以看出，直接插入数据完成排序。

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

（3）例如：

 

2、希尔排序（Shell排序）

 

（1）简介：希尔排序又称为缩小增量排序，是对直接插入排序方法的改进。

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

（3）例如：

 

3、简单选择排序

 

（1）简介：简单选择排序也叫直接选择排序，其实说白了跟直接插入排序的道理特别简单，效率低。

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

（3）例如：

 

4、堆排序

 

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

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

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

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

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

（3）例如：

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

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

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

3、重复第2步，直到堆空；

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

 

5、冒泡排序

 

（1）简介：冒泡排序，就跟水里的物体一样，小的往上浮，大的往下沉。

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

（3）例如：

 

6、快速排序

 

（1）简介：快速排序是目前内部排序中速度最快的一种排序算法。

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

（3）例如：

 

7、归并排序

 

（1）简介：归并排序又称为二路合并操作，使用合并操作完成排序的算法。

（2）基本思想：将两个或两个以上的有序表合并成一个新的有序表，最后将所有的有序表合成一个整体有序表。

（3）例如：

 

8、基数排序

 

（1）简介：前面介绍的排序方法都是对元素进行的，基数排序是对元组进行的。

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

（3）例如：

 

排序算法对比

 

总结

 

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

 

 

 

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

 

我的软考之路（一）——开篇（已更新）

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

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

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

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

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

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