JAVA排序算法汇总.pdf
40墨值下载
1
第四讲排序算法
第一节 排序及其基本概念
一、基本概念
1 ．什么是排序
排序是数据处理中经常使用的一种重要运算。
设文件由 n 个记录 {R
1
， R
2
， …… ， R
n
} 组成， n 个记录对应的关键字集合为 {K
1
， K
2
， …… ， K
n
} 。所谓排序就是将
这 n 个记录按关键字大小递增或递减重新排列。
2 ．稳定性
当待排序记录的关键字均不相同时，排序结果是惟一的，否则排序结果不唯一。
如果文件中关键字相同的记录经过某种排序方法进行排序之后，仍能保持它们在排序之前的相对次序，则称
这种排序方法是稳定的；否则，称这种排序方法是 不稳定的 。
3 ．排序的方式
由于文件大小不同使排序过程中涉及的存储器不同，可将排序分成内部排序和外部排序两类。整个排序过程
都在内存进行的排序，称为内部排序；反之，若排序过程中要进行数据的内、外存交换，则称之为外部排序。
内排序适用于记录个数不是很多的小文件 ， 而外排序则适用于记录个数太多 ， 不能一次性放人内存的大文件 。
内排序是排序的基础，本讲主要介绍各种内部排序的方法。
按策略划分内部排序方法可以分为五类：插入排序、选择排序、交换排序、归并排序和分配排序。
二、排序算法分析
1 ．排序算法的基本操作
几乎所有的排序都有两个基本的操作：
（ 1 ）关键字大小的比较。
（ 2 ） 改变记录的位置 。 具体处理方式依赖于记录的存储形式 ， 对于顺序型记录 ， 一般移动记录本身 ， 而链式
存储的记录则通过改变指向记录的指针实现重定位。
为了简化描述，在下面的讲解中，我们只考虑记录的关键字，则其存储结构也简化为数组或链表。并约定排
序结果为递增。
2 ．排序算法性能评价
排序的算法很多， 不同的算法有不同的优缺点，没有哪种算法在任何情况下都是最好的。评价一种排序算法
好坏的标准主要有两条：
（ 1 ）执行时间和所需的辅助空间，即时间复杂度和空间复杂度；
（ 2 ）算法本身的复杂程度，比如算法是否易读、是否易于实现。
第二节 插入排序
插入排序的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的记录集中，使
记录依然有序，直到所有待排序记录全部插入完成。
一、直接插入排序
1 ．直接插入排序的思想
假设待排序数据存放在数组 A[1..n] 中，则 A[1] 可看作是一个有序序列，让 i 从 2 开始，依次将 A[i] 插入到有序
序列 A[1..i-1] 中， A[n] 插入完毕则整个过程结束， A[1..n] 成为有序序列。
2 ．排序过程示例 （用 【 】 表示有序序列）
待排序数据： 【 25 】 54 8 54 21 1 97 2 73 15 （ n=10 ）
i=2 ： 【 25 54
54
54
54 】 8 54 21 1 97 2 73 15
i=3 ： 【 8
8
8
8 25 54 】 54 21 1 97 2 73 15
i=4 ： 【 8 25 54 54
54
54
54 】 21 1 97 2 73 15
of 13
40墨值下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
下载排行榜
评论