第7章内部排序.ppt

第7章 内部排序 概 述 简单插入排序 简单插入排序 简单插入排序 简单选择排序 简单选择排序 冒泡排序 快速排序 快速排序 快速排序 快速排序 快速排序 快速排序 快速排序 ⑿ 23 32 38 54 77 60 第二趟排序结果 第二趟排序过程 ⒀ 23 32 38 54 77 60 初始状态 rk=77 i j ⒁ 23 32 38 54 60 [77] Rec[j]rk 交换 i=i+1 i j * * 1、排序——是数据处理领域中的一种重要运算，它 的功能是将一个记录的无序序列，重新排列成一 个按关键字有序的序列。排序的目的之一是方便 查找。 2、排序方法的稳定与不稳定： 相同记录在排序前后的相对次序保持不变的排序 是稳定的；否则为不稳定。 3、排序分为内部排序和外部排序。 1、基本原理： 把n个数据元素的序列分为两部分， （R1,…,Ri-1）为已排好序的有序部分， （Ri,Ri+1,…,Rn）为未排好序的部分。 这时，把未排序的部分的第1个元素Ri依次与R1, … , Ri-1比较，并插入到有序部分的合适位置上，使得（R1,…,Ri）变为新的有序部分。 算法设计： 保留 list[0]不用，从第i（i=2）个数据开始,将list[i]放在list[0]，如果list[i]list[i-1]，则从j=i-1开始递减操作，只要list[j]list[0]，都将它们后移，最后将list[0]赋给list[j+1]。 1 2 3 4 5 6 21 25 49 25 16 08 0 例：现有一组记录的关键字序列为{21,25,49,25*,16,08}，用直接插入排序法将之排序。 21 25 49 25* 16 08 0 1 2 3 4 5 6 0 1 2 3 4 5 6 21 i = 2 25 初始态 0 1 2 3 4 5 6 21 i = 3 25 49 21 25 49 25* 0 1 2 3 4 5 6 0 1 2 3 4 5 6 21 25 49 25* 16 i = 5 0 1 2 3 4 5 6 21 25 49 25* 16 08 i = 6 i = 4 16 08 25* 后移 插入 后移 后移 21 25 49 25* 16 08 0 1 2 3 4 5 6 完成态 08 从以上可以看出，排序前后25都在25*之前，其相对位置没有改变，故简单插入排序是稳定的。 看动画演示？ void insertion_sort(int list[ ], int N) /* perform a insert sort ascending on the list */ { int i,j; for (i=2;iN;i++) { if(list[i]list[i-1]) { list[0]=list[i]; for (j = i-1 ; list[0] list[j]; j- -) list[j+1]=list[j]; list[j+1]=list[0]; } } } Program（Straight Insertion Sort）: 1 2 3 4 5 6 21 25 49 25* 16 08 0 3、性能分析： 若待排序记录是有序的情况下，每插入一个记录 只进行 1 次记录比较，故整个过程只进行（n-1）次 比较；若待排序的每记录完全是逆序的情况下， 每