《[工学]数据结构第23讲_插入排序2和交换排序_c》由会员分享，可在线阅读，更多相关《[工学]数据结构第23讲_插入排序2和交换排序_c（26页珍藏版）》请在金锄头文库上搜索。
1、10.2 插入排序 直接插入排序 折半插入排序 2-路插入排序 表插入排序 希尔排序,4.表插入排序 1）基本思想 通过改变排序过程中采用的存储结构，减少在排序过程中进行“移动”记录的操作。利用静态链表进行排序，并在排序完成之后，一次性地调整各个记录相互之间的位置，即将每个记录都调整到它们所应该在的位置上。,#define MAXSIZE 100 /静态链表容量 Typedef struct RcdType rc; /记录项 int next; /指针项 SLNode; /表结点类型 Typedef struct SLNode rMAXSIZE+1; /0号单元为表头结点 int length
2、; /链表当前长度 SLinkListType; /静态链表类型,2）待排记录序列的存储结构,3）具体做法 首先将静态链表中数组下标为“1” 的分量（结点）和表头结点构成一个循环链表，然后依次将下标为“2”至“n”的分量（结点）按记录关键字非递减有序插入到循环链表中。,key域,next域,38,1,2,3,65,0,97,4,0,76,4,5,13,6,2,27,7,2,49,3,8,4）表插入排序性能分析 从表插入排序的过程可见，表插入排序的基本操作仍是将一个记录插入到已排好序的有序表当中。和直接插排序相比，不同之处仅是以修改2n次指针值代替移动记录，排序过程中所需进行的关键字间的比较次数
3、相同。因此表插入排序的时间复杂度仍是O(n2)。,4）表插入排序性能分析 表插入排序的结果只是求得一个有序链表，则只能对它进行顺序查找，不能进行随机查找，为了能实现有序表的折半查找，尚需对记录进行重新排列。,5.希尔排序 1）基本思想 又称为“缩小增量排序” 。先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序（接近最好情况，效率很高），因此希尔排序在时间效率上比前两种方法有较大提高。,增量 3,增量 2,增量 1,希 尔 排 序 过 程,void ShellInsert (
4、 SqList / 插入 /ShellInsert,2）希尔排序算法描述,void ShellSort (SqList / 一趟增量为dltak的插入排序 / ShellSort,希尔排序的时间复杂度较直接插入排序低。希尔排序的分析是一个复杂的问题，因为它的时间是和所取“增量”序列的函数密切相关。到目前为止，还没有求得一种最好的增量序列，但有大量的局部结论。 注意：应使增量序列中的值没有除1之外的公因子，并且最后一个增量值必须等于1。,3）希尔排序算法分析,第10章 内部排序 10.1 排序的基本概念 10.2 插入排序 10.3 交换排序 10.4 选择排序 10.5 归并排序 10.6 基
5、数排序 10.7 各种内部排序方法的比较,10.3 交换排序 1. 起泡排序 2. 快速排序,1）起泡排序的基本思想 小的浮起，大的沉底 具体做法： 第一趟：第1个与第2个比较，大则交换；第2个与第3个 比较，大则交换， 关键字最大的记录交换 到最后一个位置上； 第二趟：对前n-1个记录进行同样的操作，关键字次大 的记录交换到第n-1个位置上； 依次类推，则完成排序。,1.起泡排序,第 六 趟,起 泡 排 序 示 例,49,56,11,78,78,65,78,41,78,36,56,11,65,41,65,36,49,11,56,41,56,36,25,11,49,41,49,36,41,36
6、,void Bubblesort(ElemType R,int n) int flag=1; /当flag为0则停止排序 for (int i=n; i1; i-) /i表示趟数，最多n-1趟 flag=0; /开始时元素未交换 for (int j=2; j=i; j+) if (RjRj-1) /发生逆序 temp=Rj; Rj=Rj-1; Rj-1=temp; flag=1; if(flag=0) return; / Bubblesort,2）起泡排序算法描述,正序： 只需进行一趟排序，在排序过程中进行n-1次关键字间的比较，且不移动记录；时间复杂度为O(n) 。 逆序： 需要进行n-1
7、趟排序，需要进行n(n-1)/2次比较，并作等数量级的记录移动。总的时间复杂度为O(n2) 。 起泡排序方法是稳定的。适合于数据较少的情况。,3）起泡排序算法分析,2.快速排序 背景 起泡排序的过程可见，起泡排序是一个增加有序序列长度的过程，也是一个缩小无序序列长度的过程，每经过一趟起泡，无序序列的长度只缩小 1。 试设想：若能在经过一趟排序，使无序序列的长度缩小一半，则必能加快排序的速度。,1）基本思想 通过一趟排序将待排序列以枢轴为标准划分成两部分，使其中一部分记录的关键字均比另一部分小，再分别对这两部分进行快速排序，以达到整个序列有序。 通常取第一个记录的值为基准值或枢轴。,2）具体做法
8、 附设两个指针low和high，初值分别指向第一个记录和最后一个记录，设枢轴为 key； (1)从high 所指位置起向前搜索，找到第一个不大于基准值的记录与枢轴记录相互交换； (2)从low 所指位置起向后搜索，找到第一个不小于基准值的记录与枢轴记录相互交换。 (3)重复这两步直至low=high为止。,21,（ 21 03 37 13 91 09 ）,09,37,13,3）一趟快速排序算法描述 int Partition (Elem R , int low, int high) R0 = Rlow; pivotkey = Rlow.key; while (low = pivotkey) -
9、 - high; Rlow = Rhigh; /将比枢轴记录小的移到低端 while (low high /返回枢轴位置 / Partition,对记录序列Rlow.high进行快速排序算法 void QSort ( Elem R , int low, int high ) if (low high) /长度大于1 pivo = Partition( L,low,high); /将Rlowhigh一分为二 QSort(L,low, pivo-1); /对低子表递归排序，pivo是枢轴 QSort(L, pivo+1, high); / 对高子表递归排序 / QSort 对记录序列进行快速排序 void QuickSort(Elem R, int n) QSort(R, 1, n); / QuickSort,4）快速排序分析 最好的情形（左、右子区间的长度大致相等）,快速排序的最好时间复杂度应为O(nlog2n)。 最坏的情形（每次能划分成两个子区间，但其中一个是空），快速排序的最坏时间复杂度为O(n2)。 对n较大的情况，它是平均速度最快的排序算法，但当n很小时，此方法往往比其他简单排序方法还要慢。 快速排序是不稳定的。,
