10第三章基本排序7讲

1、1回 顾 23.1 查找n顺序查找n对分查找n分块查找n哈希查找o(n)o(log2n)o(log2(m+1)+n/m)o(1)33.3 排序交换排序插入排序选择排序堆排序二叉排序树41. 排序n ：将一个无序序列整理成按值非递减顺序排列的有序序列。 n 排序可以在不同的存储结构上实现。q基本排序是在顺序存储的线性表中实现的；q二叉排序树利用二叉树的链式存储结构实现无序表的有序化。n 三种基本排序方法：n交换排序 （如 冒泡排序和快速排序）；n插入排序 （如 简单插入排序和希尔排序）；n选择排序 （如 简单选择排序和堆排序）；52. 交换排序n交换排序的基本思想： 两两比较待排序记录的关键值，

2、并交换不满足顺序要求的偶对，直至全部满足为止。n交换排序的两种形式q冒泡排序q快速排序62.1 冒泡排序n冒泡排序的基本过程：q(1) 从表头开始向后扫描，依次比较相邻元素。如果为“逆逆序序”，进行互换。一次扫描后，最大元素排到表末端；q(2)从后先前扫描剩下的线性表，依次比较相邻元素，如有“逆序”，进行互换。一次扫描后，最小元素排到表前端；q(3)对剩下的线性表重复过程(1)(2)，直到消除了所有的逆序。最坏情况下的时间复杂度（工作量）为o(n(n-1)/2).72.2 快速排序n快速排序的提出q 冒泡排序只能在扫描过程中对相邻两个元素进行比较，消除一个逆序。q 能否找到一种办法，通过一次交

3、换来消除线性表中的多个逆序，从而大大加快排序的速度。 n快速排序基本思想q 从线性表中选取一个元素设为t。然后将线性表后面小于t的 元素移到前面，而前面大于t的元素移动到后面，这样将线性表分成两部分，即进行了一次线性表的分割。q 对分割后的各子表再按上述原则进行分割，一直到所有子表为空，即完成线性表的排序过程。最坏情况下的时间复杂度（工作量）为o(n(n-1)/2).82.3 快速排序的算法实现n实现步骤q首先，在表的第一个、中间一个或最后一个元素中选取中间项赋予t，设为p(k),再将表中第一个元素移到p(k)位置。q 设置两个指针i和j分别指向表的起始与中止位置，反复操作以下两步：n(1)

4、将j指针逐渐减小，并逐次比较p(j)与t，直到发现一个p(j)t为止，将p(i)移到p(j)的位置上；上述操作交替进行，直到指针i和j指向同一个位置(i=j)为止。93 简单插入排序n简单插入排序基本思想 把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。 把ai插入到a0，a1，.,ai-1之中的具体实施过程为:先把ai赋值给变量t，然后将t依次与ai-1,ai-2,.进行比较，将比temp大的元素右移一个位置，直到发现

5、某个j(0=j=i-1)，使得aj=t或j为(-1),把t赋值给aj+1。最坏情况下的时间复杂度（工作量）为o(n(n-1)/2).104 简单选择排序n1. 简单选择排序基本思想 每次从待排序的记录中选出关键字最小(或最大)的记录，顺序放在已排序的记录序列的最后，直到全部排完为止。n2. 基本步骤： 首先在所有的记录中选出键值最小的记录，把它与第一个记录交换，然后在其余的记录中再选出键值最小的记录与第二个记录交换，依次类推，直到所有的记录排序完成。 第i趟在 n-i+1(i=1,2,.n-1)个记录中选择键值最小的记录作为有序序列的第i个记录。最坏情况下的时间复杂度（工作量）为o(n(n-1

6、)/2).11n1. 堆定义： 或 n2. 堆的表示q一维数组表示q完全二叉树表示q堆顶元素为n个元素中的最大项n是一种选择排序5. 堆排序 221iiiihhhh221iiiihhhh125.1 堆举例n例：（91，85，53，36，47，30，24，12）918553364730241209118525333644753062471213n堆构造 q如以完全二叉树形式表示， 从最后一个非叶子结点（第n/2个 元素）开始，直到第一个元素为止，逐步进行调整建堆，最后就能够得到与此序列对应的 堆。 n例：（ 47， 91， 53， 85， 30， 12， 24， 36）5.2 构造一个堆4791

7、538530122436145.3 堆排序步骤 n1.首先，将无序序列以完全二叉树表示；n2.将给定的 无序序列构造堆 ；n3.将堆顶元素与堆中最后一个元素交换，然后将最后一个元素从原堆结构中删去，再将前面元素构成的 二叉树调整成堆。n4.反复进行（3）步，直到堆空为止。最坏情况下的比较次数为o(nlog2n).153.3 二叉排序树及其查找161 二叉排序树定义：n二叉树或者为空，或者是具有下列性质的 二叉树：q如根节点的 左子树不空，则左子树所有结点的值均小于根结点值；q如根节点的 右子树不空，则右子树所有结点的值均大于根结点值；q根节点的 左右子树也分别是二叉排序树。172。二叉排序树的构造n依次读入序列中的 每一格数据元素，并分别为之建立新结点，按下述方式插入到二叉排序树中：q如二叉排序树为空，则新结点位二叉排序树的根结点；q如二叉排序树不为空，则将新结点与根节点的 值比较，如小于根节点值，则插入到左子树中去，否则插入到右子树。183 二叉排序树的特性n中序遍历二叉排序树即可得到有序序列 ！n查找效率与有序表的 对分查找基本接近。n举例：q用二叉排序树对下序列排序 （53，61，12，37，90，