第三章排序
第 1 页
学写的义 早期的计算机约有一半的时间花在排序操作上,虽然随着 计算机速度的提高,排序操作不再像早期那样占用计算机过多 的时间,但它仍然是信息处理中最常用,也是最重要的运算之 实际上,在计算机科学中,排序仍然是组织数据最基本的运 算,许多程序和软件均以它作为一个中间步骤。因此,人们设 计了大量的排序算法以满足不同的需求。 计算机图灵奖获得者,著名计算机科学家DE. Knuth在他的 著《 Art of Computer Programming》中列举分析了25中经典 排序方法,并且指出,这只是现有方法中的“一小部分
第 2 页 ◆学习的意义： 早期的计算机约有一半的时间花在排序操作上，虽然随着 计算机速度的提高，排序操作不再像早期那样占用计算机过多 的时间，但它仍然是信息处理中最常用，也是最重要的运算之 一。 实际上，在计算机科学中，排序仍然是组织数据最基本的运 算，许多程序和软件均以它作为一个中间步骤。因此，人们设 计了大量的排序算法以满足不同的需求。 计算机图灵奖获得者，著名计算机科学家D.E.Knuth在他的 巨著《Art of Computer Programming》中列举分析了25中经典 排序方法，并且指出，这只是现有方法中的“一小部分
团今金墨庐容 31排序的基本概念 32简单的排序方法 321插入排序 3.2.2起泡排序 33先进的排序方法 3.3.1快速排序 332归并排序 333堆排序 3.4基数排序 3.4各种排序方法的综合比较
第 3 页 3.1 排序的基本概念 3.2 简单的排序方法 3.2.1 插入排序 3.2.2 起泡排序 3.3 先进的排序方法 3.3.1 快速排序 3.3.2 归并排序 3.3.3 堆排序 3.4 基数排序 3.4 各种排序方法的综合比较 ◆主要内容：
3.1排序的基本概念 在很多情况下,相对于无序表而言,使用有序表可以提 高算法效率,因为有序表可以充分利用其有序性采用一些效 率较高的算法,例如,在进行数据元素的查找时,采用有序 表比无序表效率要高很多。 如何得到有序表?我们可以在构造顺序表的时候依顺序表 的有序性进行数据元素的插入,从而求得有序表。 更多的时候,我们需要对一个无序的顺序表进行“排序 将它转化为“有序”的顺序表
第 4 页 在很多情况下，相对于无序表而言，使用有序表可以提 高算法效率，因为有序表可以充分利用其有序性采用一些效 率较高的算法，例如，在进行数据元素的查找时，采用有序 表比无序表效率要高很多。 如何得到有序表？我们可以在构造顺序表的时候依顺序表 的有序性进行数据元素的插入，从而求得有序表。 更多的时候，我们需要对一个无序的顺序表进行“排序” ，将它转化为“有序”的顺序表。 3. 1 排序的基本概念
3.1排序的基本概念 排序的定义 排序是按关键字的非递减或非递增顺序对一组记录重新进行整 队(或)排列的操作 例1、高考考生信息管理系统提供了将考生按总分排序、按单科排序的功 能 例2、数学中的数列(1,13,15,17,19,姓名电话号吗 例3、英文字母表(A,B,C,D,E.Z) 例4、某单位的电话号码簿。 蔡颖 63214444 陈红 63217777 刘建平 63216666 王小林 63218888 张力 63215555
第 5 页 排序 是按关键字的非递减或非递增顺序对一组记录重新进行整 队(或)排列的操作. 姓名 电话号码 蔡颖 63214444 陈红 63217777 刘建平 63216666 王小林 63218888 张力 63215555 ... 3. 1 排序的基本概念 例1、高考考生信息管理系统提供了将考生按总分排序、按单科排序的功 能； 例2、数学中的数列（11，13，15，17，19，21） 例3、英文字母表（A, B, C, D, E Z ）。 例4、某单位的电话号码簿。 排序的定义