首页 > 代码库 > 我的软考之路(六)——数据结构与算法(4)之八大排序

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

        排序是编程的基础,在程序中会常常使用,好的排序方法能够帮助你提高程序执行的效率,所以学好排序,打好基础,对于程序的优化会手到擒来。不管你的技术多么强,假设没有基础也强不到哪去。

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

                                                      

    总有人说排序非常难,可是我总认为非常easy,我们仅仅须要了解基本思想就好了,通过简单的样例来加深理解。


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)之查找已更新


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