数据结构CC版第9章 应用排序.pptx

《数据结构CC版第9章 应用排序.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构（C语言版）项目九应用排序在本项中，通过1个工作任务，向读者展示排序的功能以及作用。为用户排序数据作铺垫。目录任务使用选择排序输出结果使用选择排序输出结果准备知识使用选择排序输出结果排序的概述排序分类直接插入排序冒泡排序直接选择排序简单排序算法的时间代价对比Shell排序快速排序归并排序堆排序多关键码排序链式基数排序1.排序的概述1.排序的概述排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内排序和外排序。若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。反之，若参加排

2、序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。2.排序分类2.排序分类稳定排序：假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字，在用某种排序法排序后，若这些相同关键字的元素的相对次序仍然不变，则这种排序方法是稳定的（stable）。本项目后面介绍的冒泡，插入，基数，归并属于稳定排序，选择，快速，希尔，堆属于不稳定排序。就地排序：若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间为O（1）,则称为就地排序。3.直接插入排序3.

3、直接插入排序直接插入排（insertsorting）序是一种最简单的排序方法。它的基本思想是：顺序地将待排序的记录按其关键码的大小插入到已排序的记录子序列的适当位置。子序列的记录个数从1开始逐渐增大，当子序列的记录个数与顺序表中的记录个数相同时排序完毕。4.冒泡排序4.冒泡排序冒泡排序（bubblesorting）也称起泡排序，是一种简单的排序方法，其基本思想是：首先将第一个记录和第二个记录做比较，若逆序即r[1].key>r[2].key，则将两个记录交换，然后再比较第二个记录和第三个记录，以此类推，直到第n-1个记录和第n个记录比较结

4、束，这样完成一趟冒泡排序，第一趟排序结束后，最大的记录被交换到第n个位置；之后再对前面n-1个记录依前面的过程进行第二趟冒泡排序，将关键字次大的记录交换到第n-1个位置。一般的，第i趟排序是从位置1到位置n-i+1依次比较相邻两个记录的关键字，并在逆序时交换相邻的记录，其结果是这n-i+1个记录中关键字最大的记录被交换到n-i+1的位置上。整个排序过程需进行k(1≤k

5、简单的排序方法，其算法思想和冒泡排序很类似。基本思想是：第一趟，从待排序记录中选出最小关键字的记录与第一个记录交换，第二趟再从剩余的数据中选出具有最小关键字的记录与第二个记录交换，以此类推，共进行n-1趟排序，将所有记录排好序。按照直接选择排序方法，排序过程如下图所示。5.直接选择排序直接选择排序示例6.简单排序算法的时间代价对比6.简单排序算法的时间代价对比插入排序时依次对前i个记录进行排序，而冒泡排序和选择排序则是依次对从剩余记录中找出第i小的记录，只是前者通过不断比较交换相邻的记录来寻找最小记录，而后者是先找到最小记录所在的位置，然

6、后直接交换到正确的位置，因此选择排序可以看做是对冒泡排序的一种改进算法。从这三种排序算法的具体实现中可以看出，他们都是通过两层循环来实现的，所以他们一般情况下的时间代价都是O(n2)。7.Shell排序7.Shell排序希尔排序(ShellSort)是对直接插入排序的一种改进方法，它出自D.L.Shell，因此而得名。Shell排序又称作缩小增量排序。该方法实质上是一种分组插入方法。按照希尔排序，其排序过程如下图所示。7.Shell排序希尔排序示例8.快速排序8.快速排序快速排序是一个非常重要的内排序算法，是对冒泡排序的一种改进。假设数组

7、的0单元不存储数据，用r[0]暂存支点记录。一趟快速排序的过程如下：(1)设置两个整数变量i,j，初始i,j分别指向待排序记录的第一个元素和最后一个元素，将r[i]复制到r[0]中。(2)从j所指记录开始，比较r[j].key和r[0].key，若r[j].key>r[0].key，则j--，重复这个过程，直到找到一个小于r[0].key的记录为止，将该记录复制到位置i处。(3)修改i=i+1，从i所指记录开始，依次向后比较r[i].key和r[0].key，若r[i].key

8、[0].key的记录，将该记录复制到位置j处。(4)修改j=j-1，重复(2)和(3)过程，直到i=j结束。(5)将r[0]复制到位置i(j)处。8.快速排序按照快速排序方法，排序过程如下图所