首页 > 代码库 > 排序算法(二)

排序算法(二)

    在上一篇排序算法的文章中介绍了插入排序,分别为直接插入排序和希尔排序。今天我们继续来介绍其他的排序算法。

1、选择排序:简单选择排序

定义:通过n-i(i<=i<=n)次关键字之间的比较,从n-i+1个记录中选出关键字最小的记录,并和第i个记录进行交换,当i等于n时所有的记录有序排列。

具体做法:看着有些复杂,还不知道其所以然。我来解释一下,就是在n条数据中我们要进行排序,就从这n条数据中查找最小(或最大)的一条记录,然后将这个记录与这个序列中的第一条数据调换位置,这时整个带排数据剩下n-1条数据了;再从这个n-1条数据中找出一条最小(或最大)的记录,放在这个n-1条数据中的第一个位置,此时待排序列还剩n-2条数据。以此类推直至将所有的数据都按照顺序排列完。

举例:下面举个例子结合图形来更好的说明简单选择排序。假设一个带排数列:5,8,1,4,9,7,3  将这个数列按照从大到小的方式进行排序。

 

从这7条数据中选择一条最小的数据,通过6次(n-i次)关键字的比较,从7个(n-i+1个)记录中找出关键字最小的记录,并与这7个(n-i+1个)数据中的第一个数据交换位置。所以第一次排序将序列中的51调换位置。此时序列变成

此时待排序列变成了8,5,4,9,7,3(除去已经排好序的第一个数1),在对8,5,4,9,7,3这个序列进行简单选择排序

按照上述方法,此时是从6条数据中选择一条最小的数据,通过5次(n-i次)关键字的比较,从6个(n-i+1个)记录中找出关键字最小的记录,并与这6个(n-i+1个)数据中的第一个数据交换位置。所以第一次排序将序列中的83调换位置。此时序列变成

就这样以此类推,不断缩小待排数列中的数,将排序号的数放入到前面的数列中,直至所有的数都排序完成。后面的比较不再赘述。下面说堆排序。

 

2、选择排序:堆排序

定义:要说堆排序,先得说说什么是堆。那么什么是堆呢?从定义的角度说就是对于n个元素的关键字序{K1 ,K2 ,K3,....,Kn}当且仅当满足(Ki<=K2i) and (Ki<= K2i+1)(Ki >= K2i) and( Ki>= K2i+1)关系时称其为堆。在一个堆中堆顶元素(即完全二叉树的根结点)均不小于或不大于其左右孩子结点,即堆顶元素为为该序列中的最大或最小元素,由此可分为大顶堆或小顶堆。

具体做法:而堆排序就是按照堆的定义排成一个序列(即建立初始堆),从而可以找出该堆中的最大关键字或最小关键字,而后再将剩余的关键字重新调整成新堆,再次得到最大的关键字或最小关键字。以此类推、如此反复,直至全部关键字排成有序序列为止。

举例:下面我们还是举个例子来说明。假设带排序列为9,12,3,6,15,7,5,按照从大到小的顺序排列。首先我们根据堆的定义将这个序列排成一个大顶堆,如下所示

此时输出堆顶元素15,剩下的关键字再调整形成一个新堆,如下所示:

此时输出堆顶元素次大的元素12,剩下的关键字再调整形成一个新堆,如下所示:

以此类推、如此反复,直至全部关键字排成有序序列为止。后面的过程同上,在这里不再赘述。

******************************************************************************************************

    由于篇幅的原因这篇文章先到这里,下一篇文章我将介绍交换排序、归并排序、基数排序,敬请期待!

 

 

 

 

 

排序算法(二)