一、概述
根据是否使用外存,排序可以分为内部排序和外部排序。若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序。反之,若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。
内排序的方法有许多种,按所采用策略的不同,可归纳为五类:插入排序、选择排序、交换排序、归并排序和分配排序。
其中,插入排序主要包括直接插入排序和希尔排序两种;选择排序主要包括直接选择排序和堆排序;交换排序主要包括气(冒)泡排序和快速排序。
二、实现
这里我们主要讨论插入排序、希尔排序、堆排序、归并排序和快速排序。
◎插入排序
最简单的排序算法之一是插入排序(insertionsort)。插入排序由N– 1趟(pass)排序组成。对于P= 1趟到P=N– 1趟,插入排序保证从位置0到位置P上的元素为已排序状态。插入排序利用了这样的事实:位置0到位置P– 1上的元素是已排过序的。
◎希尔排序
通过比较相距一定间隔的元素来工件各趟比较所用的距离随着算法的进行而减小,直到只比较相邻元素的最后一趟排序为止,因此希尔排序有时也叫做缩小增量排序(diminishing increment sort)。
增量序列的一种流行(但是不好)的选择是使用Shell建议的序列:ht=⌊N/ 2⌋和hk=⌊hk + 1/ 2⌋。
◎堆排序
由二叉堆的性质可知(可参考本人其它博文:优先队列(堆) - C语言实现(摘自数据结构与算法分析C语言描述)),建立一个N个元素的二叉堆需花费O(N)时间,然后我们执行N次DeleteMin操作。按照顺序,最小的元素先离开该堆。通过将这些元素记录到第二个数组,然后再将数组拷贝回来,我们得到N个元素的排序。由于每个DeleteMin花费时间O(log
N),因此总的运行时间是O(N log N)。
该算法的主要问题在于它使用了一个附加的数组。因此,存储需求增加一倍。避免使用第二个数组的聪明的做法是利用这样的事实:在每次DeleteMin之后,堆缩小了1。因此,位于堆中最后的单元可以用来存放刚刚删去的元素。
◎归并排序
归并排序以O(N log N)最坏情形运行时间运行,而所使用的比较次数几乎是最优的。这个算法的基本的操作是合并两个已排序的表。因为这两个表是已排序,所以若将输出放到第三个表中时则该算法可以通过对输入数据一趟排序来完成。基本的合并算法是取两个输入数组A和B,一个输出数组C,以及三个计数器Aptr,Bptr,Cptr,它们初始置于对应数组的开始端。A[Aptr]和B[Bptr]中的较小者被拷贝到C中的下一个位置,相关的计数器向前推进一步。当两个输入表有一个用完的时候,则将另一个表中剩余总分拷贝到C中。
该算法是经典的分治(divide-and-conquer)策略,它将问题分成一些小的问题然后递归求解,而治的阶段解得的各个答案修补到一些,分治是递归常有力的用法。
◎快速排序
正如它的名字所标示的,快速排序(quicksort)是在实践中最快的已知排序算法,它的平均运行时间是O(N
log N)。
像归并排序一样,快速排序也是一种分治的递归算法。将数组S排序的基本算法由下列简单的四步组成:
1.如果S中元素个数是0或1,则返回;
2.取S中任一元素v,称为枢纽元(pivot);
3.将(S中其余元素)分成两个不相交的集合:S1 = { x ∈
S - { v } | x ≤ v } 和S1 = {
x ∈ S - { v } | x ≥ v };
4.返回{quicksort(S1)后,继随v,继而quicksort(S2)}。
文件名:sort.h
文件名:sort.c
文件名:main.c
附录:上述代码中用到了Error、FatalError等函数,其实现如下(即fatal.h文件):
备注:本文摘自《数据结构与算法分析 C语言描述 Mark Allen Weiss著》,代码经gcc编译测试通过。
附件下载:http://download.csdn.net/detail/shuxiao9058/4212399#sort_20120407.tar.gz
分享到:
相关推荐
数据结构与算法分析-C语言描述;数据结构与算法分析-C语言描述;数据结构与算法分析-C语言描述;数据结构与算法分析-C语言描述;数据结构与算法分析-C语言描述;数据结构与算法分析-C语言描述;数据结构与算法分析-C语言...
数据结构与算法C语言版本,帮助数据结构快速入门
数据结构与算法分析--C语言描述(英文第2版)
数据结构与算法分析--C语言描述(英文第2版).chm
用C语言描述的数据结构与算法的入门教程,同时还介绍了部分机器学习的算法,另附带演示软件。
数据结构与算法分析--C语言描述 内容不错
操作系统实验报告--C语言实现银行家算法.doc
数据结构与算法分析-C语言实现,Mark Allen Weiss经典著作,让你对数据结构和算法分析有更加深刻认识和C语言编程的实现
《数据结构与算法分析(C语言描述)》(https://book.douban.com/subject/33419792/)
数据结构与算法分析-c语言分析是数据结构与算法方面的经典教材,对于提高算法能力有极大帮助。
《数据结构与算法分析:C语言描述》(英文版第2版)是数据结构和算法分析方面的经典教材。第2版更加精炼并强化了《数据结构与算法分析:C语言描述》(英文版第2版)创新的对算法和数据结构的讲授方法。通过C程序的实现,...
数据结构---C语言描述-(耿国华)-高等教育出版社出版-课后习题答案
原书曾被评为20世纪顶尖的30部计算机著作之一,作者Mark Allen Weiss在数据结构和算法分析方面卓有建树,他的数据结构和算法分析的著作尤其畅销,并受到广泛好评.已被世界500余所大学用作教材。 在本书中,作者更加...
数据结构与算法分析 C语言描述(原书第2版)课后习题参考答案
数据结构与算法分析:C语言描述(原书第2版)是《data structures and algorithm analysis in c》一书第2版的简体中译本。原书曾被评为20世纪顶尖的30部计算机著作之一,作者mark allen weiss在数据结构和算法分析...
数据结构与算法分析(C语言描述)【https://book.douban.com/subject/33419792/】程序代码
数据结构与算法分析-C语言描述>>编程练习. 课后习题的C语言实现.
数据结构与算法分析-c语言描述_课后答案以及源码,但是是英文版的,目前没发现中文版的,如有欢迎大家告诉我。
《数据结构与算法分析:C语言描述》曾被评为20世纪顶尖的30部计算机著作之一,作者在数据结构和算法分析方面卓有建树,他的数据结构和算法分析的著作尤其畅销,并受到广泛好评,已被世界500余所大学选作教材。...