GESP-4级-24 简单排序算法（课件）.pptxVIP

24.简单排序算法;

本章内容

介绍插入法、冒泡法、简单选择法排序的思想及实现方法。

介绍一些特殊排序需求的实现方法。;

口爸爸：抱一，你们中午在学校吃饭，是按照什么顺序排队打饭的呀?

口抱一：一年级、二年级的时候是在教室吃饭，有食堂阿姨把饭菜用小推车送过来,然后老师一般让我们按学号排队打饭。三年级开始是去食堂吃饭，下课了排好队，老师带着我们去食堂打饭。

口爸爸：那你们上体育课的时候，是怎么排队的呀。

口抱一：上体育课的时候，有时是按学号排队，有时是按身高从矮到高排队。爸爸,你到底想问什么呀?这跟我们今天要学的编程有联系吗?

口爸爸：有呀，我们今天要学排序，所以让你对比一下在学校的各种顺序。;

1.排序及排序函数

口排序的例子在生活中处处可见。上体育课的时候，老师可能要求学生按学号顺序排成一列，也可能要求按身高从矮到高的顺序排列。一次考试结束，老师可能会对分数按从高到低的顺序排序。;

1.排序及排序函数

顺序，指事物在空间上或时间上排列的先后。程序中的排序，一般指对数据按指定的顺序（如从大到小或从小到大）排序。对数据进行排序是数据处理中经常要用到的操作。

本章介绍三种简单（效率较低）的排序算法的思想及实现，这些算法对训练学生的编程能力和算法的理解能力非常重要。但必须要说明的是，现代编程语言一般都提供了一些排序函数，这些排序函数都采用效率较高的排序算法，且能适应各种排序情形，详见下一章内容。在程序设计竞赛里，最重要的是排序思想的应用及排序函数的使用。;

2.字典序

口整型和浮点型等数值型数据可以按大小关系排序，西文字符可以按ASCII编码值的大小关系排序。

口字典序的说法源自于字典中的单词是按字母顺序排列的，比如addend排在

address前面。除了单词可以按字典序排序外，任何字符串(比如数字字符串)都可以按字典序排序，排序时按照这些字符的编码(如ASClI码)顺序排序。;

2.字典序

具体来说，2个字符串按字典序比较的方法是：从2个字符串的第1个字符开始比较，如果相???则看下一个字符，直到出现不相等的字符为止，不相等字符的大小关系就决定了2个字符串的顺序。

例如，按照字典序，数字字符串“72391”排在“7258”前面。

甚至，n个整数的若干个排列，也可以按字典序排序，比如按字典序，“143256”应该排在“165234”的前面。;

解题报告——冒泡法排序;

冒泡法排序

题目描述：

输入n个数，对这n个数按从小到大的顺序排序。

输入描述：

输入数据第一行为正整数n,2≤n≤20,接下来第二行，有n个整数，用空格隔开。

输出描述：

输出占一行，为排序后的n个整数，用空格隔开。

样例输入：样例输出：

81327303849657697

4938659776132730;

分析：

“冒泡”这个词很形象地描述“冒泡法”排序的思想。在烧开水时，由于水泡中含有空气,比重比较小，所以水泡会冒上来。在“冒泡法”排序过程中，较大的数逐—“沉”到底部，而较小的数也相对“浮上来”。;

假设按从小到大的顺序排序，需要排序的n个数已经存放在数组a中。

冒泡法的基本思路是：

①比较第0个数与第1个数，若为逆序，即a[0]a[1]，则交换；然后比较第1个数与第2个数；依次类推，直至第n-2个数和第n-1个数比较为止。第0趟排序的结果是最大的数被安置在最后一个元素位置上，这个数就不用参与后续的比较了。排序的趟数从第0趟开始计数主要是为了与“数组元素的下标是从0开始计数”一致。注意，冒泡法有个特点，就是比较和交换相邻2个数。

②对前n-1个数进行第1趟冒泡排序，结果使次大的数被安置在第n-1个元素位置，这个数也不用参与后续的比较了。

③如此重复上述过程，共经过n-1趟冒泡排序后，排序结束。;

(a)第0趟比较

444

522

250

00