当前位置:文档下载 > 所有分类 > IT/计算机 > 计算机软件及应用 > 数据结构中排序方法的研究
免费下载此文档

数据结构中排序方法的研究

数据结构中排序方法的研究

作者:王海燕

来源:《科技资讯》2012年第35期

摘 要:排序是数据处理领域中最常用的一种运算。排序的目的之一是方便查找。对于一个顺序存储的线性表,若不经过排序而查找,则时间复杂度为O(n),若在排序的基础上进行二分查找,则时间复杂度可提高到O(logn),效果是相当显著的。

关键词:数据结构 排序 方法

中图分类号:TP311 文献标识码:A 文章编号:1672-3791(2012)12(b)-0027-02 1 排序的基本概念

排序就是把一组记录按照某个领域的值的递增(由小到大)或递减(由大到小)的次序重新排列的过程。通常把用于排序的域称为排序域或排序项,把该域中的每一个值(它与一个记录相对应)称为排序码。

记录的排序码可以是记录的关键字,也可以是任何非关键字,所以排序码相同的记录可能只有一个,也可能有多个。对于具有同一个排序码的多个记录来说,若采用的排序方法使排序后记录的相对次序不变,则称此排序方法是稳定的,否则称为不稳定的。

2 排序的方法

排序的方法很多,一般分为插入排序法、交换排序法、选择排序法、归并排序法四种。

2.1 插入排序法

插入排序法包括直接插入排序和希尔排序。

(1)直接插入排序:直接插入排序是一种最简单的排序方法。

1)算法思想:直接插入排序的基本思想是:逐个处理待排序列中的记录,将其与前面已经排好序的子序中的记录进行比较,确定要插入的位置,并将记录插入到子序中。具体做法如以下几点。

①开始时,把第①个记录看成是已经排好序的子序,这时子序中只有一个记录。

②从第②个记录起到最后一个记录,依次将记录和前面子序中的记录比较,确定记录插入的位置。

免费下载Word文档免费下载:数据结构中排序方法的研究

(下载1-1页,共1页)

我要评论

返回顶部