数据结构中排序方法探究

《数据结构中排序方法探究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构中排序方法探究摘要：排序是数据处理领域中最常用的一种运算。排序的目的之一是方便查找。对于一个顺序存储的线性表，若不经过排序而查找，则时间复杂度为0(n),若在排序的基础上进行二分查找，则时间复杂度可提高到O(logn),效果是相当显著的。关键词：数据结构排序方法中图分类号：TP311文献标识码：A文章编号：1672-3791(2012)12(b)-0027-021排序的基本概念排序就是把一组记录按照某个领域的值的递增(由小到大)或递减(由大到小)的次序重新排列的过程。通常把用于排序的域称为排序域或排序项，把该域中的每一个值(它与一个记录相对应)称

2、为排序码。记录的排序码可以是记录的关键字，也可以是任何非关键字，所以排序码相同的记录可能只有一个，也可能有多个。对于具有同一个排序码的多个记录来说，若采用的排序方法使排序后记录的相对次序不变，则称此排序方法是稳定的，否则称为不稳定的。2排序的方法排序的方法很多，一般分为插入排序法、交换排序法、选择排序法、归并排序法四种。2.1插入排序法插入排序法包括直接插入排序和希尔排序。（1）直接插入排序：直接插入排序是一种最简单的排序方法。1）算法思想：直接插入排序的基本思想是：逐个处理待排序列中的记录，将其与前面已经排好序的子序中的记录进行比较，确定要插入的位置，

3、并将记录插入到子序中。具体做法如以下几点。%1开始时，把第①个记录看成是已经排好序的子序，这时子序中只有一个记录。%1从第②个记录起到最后一个记录，依次将记录和前面子序中的记录比较，确定记录插入的位置。%1将记录插入到子序中，子序记录个数加1,直至子序长度和原来待排序列长度一致时结束。2）算法分析。%1直接插入排序的时间复杂度为0（n2）。%1直接插入排序是稳定的。适用于记录个数较少的场合。（2）希尔排序：希尔排序又称缩小增量排序，是对直接插入排序的一种改进。1）算法思想：希尔排序的基本思想是：先将n个待排序记录序列分割成若干个子序列，然后对各子序列分别

4、进行排序，当整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。具体做法如以下几点。①取定一个正整数dl1)算法思想：直接选择排序的基本思想是：设n个待排序的记录存放在L.r［l..n］中,对n个待排序记录进行n-1趟扫描。%1第一趟扫描选出n个记录中关键字最小的记录，并与L.讥1］记录交换位置。%1第二趟扫描选出余下的n-1个记录中关键字值最的记录，并与L.r［2］记录交换位置。依此类推，直至第n-l趟扫描结束，所有记录有序为止。2)算法分析。%1直接选择排序时间复杂度为0(n2)。%1直接选择排序是不稳定的。(2)堆排序。1)堆排序的方

5、法：关键步骤有两个：第①是构造堆，即如何将一个无序序列建成初始堆垒；第②是调整堆，即如何在输出堆垒的根结点之后，调整剩余元素成为一个新的堆垒。首先考虑第二个问题，调整堆；然后再考虑第一个问题,构造堆。①调整堆。假设输出堆根结点之后，以堆的最后一个元素替代之。此时根结点的左子树和右子树均为堆垒，则只需要自上而下进行调整即可。首先将根结点与它的左、右子结点比较，如果根结点比它的两个子结点都小，则已经是堆垒;否则，让根结点与其中较小的子结点交换，先让根结点满足堆的性质。可能因为交换，使以交换后的结点为根的子树不再满足堆的性质，则重复向下调整。当调整使新的更小子

6、树依旧满足堆的性质时，重新建堆垒过程结束；当交换使新的更小的子树不再满足堆的性质时，继续按上述方法调整被破坏的更小子树。最坏的情况是直至调整到叶结点才结束。这种自上而下调整建堆的过程称为结点向下“筛选”。②构造堆。为构造初始堆，可以在已是堆的两个子序列上面加上它们的根结点，并且做必要的调整使之成为更大的堆垒。加上根结点后，可能不满足堆的定义，则可以用前述的"筛选”方法，使之成为堆。所以，从一个无序序列构造堆的过程就是反复“筛选”的过程。若将n个待排序记录的关键字序列看成是一个完全二叉树，则最后一个非叶子结点是第n/2个元素。首先，将n个叶子结点看成n个堆

7、，然后从第n/2个结点开始，依次将第n/2个结点，第n/2-l个结点，……，第1个结点按照堆的定义逐一加到它们的子结点上，直到建成一个完全的堆垒。2）算法分析。①堆排序在最坏的情况下，其时间复杂度也为0(nlog2n)0②堆排序是不稳定的。不适用于记录较少的情况。2.4归并排序法归并排序的基本思想是：将两个或两个以上的有序序列归并成一个有序序列。（1）两个有序序列的归并：将两个有序序列归并为一个新有有序序列，称为2-路归并，其核心是将一维数组中前后相邻的两个有序序列合并为一个有序序列。（2）一趟归并排序。1）算法思想：对于有n个记录的无序序列进行归并排序

8、，其基本思想是。%1将n个待排序的记录分成只含有1个记录的n个有序子序列。%1将