《数据结构复习(9)》由会员分享，可在线阅读，更多相关《数据结构复习(9)（10页珍藏版）》请在金锄头文库上搜索。
1、数据结构复习（9）,中国科学院研究生院,排序-Wang Wenjie,排序（1）,排序 (sorting) 是计算机程序设计中的一种重要运算。它的功能是将一个数据元素 (或记录) 的任意序列，重新排列成一个按关键字有序的序列。假设含 n 个记录的序列为 R1 ,R2 ,Rn 其相应的关键字序列为 K1，K2，Kn 需确定1，2，n的一种排列p1，p2，pn，使其相应的关键字满足如下的非递减（或非递增）关系 Kp1Kp2Kpn 。即使初始的的序列成为一个按关键字有序的序列 Rp1，Rp2，Rpn 这样一种操作称为排序。,排序-Wang Wenjie,排序（2）,性质：稳定排序/不稳定排序如果在对
2、象序列中有两个对象ri和rj，它们的关键码 ki = kj，且在排序之前，对象ri排在rj前面。如果在排序之后，对象ri仍在对象rj的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的,排序-Wang Wenjie,排序（3）,内排序与外排序: 内排序是指在排序期间数据对象全部存放在内存的排序；外排序是指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。,排序-Wang Wenjie,插入排序,直接插入排序思想：将一个元素向一个有序序列插入做法：0位监测哨，从一个元素逐步扩大有序序列。 折半插入排序改进直接插入，将一个元素用折半法插
3、入有序序列 2-路插入排序减少直接插入法的移动元素的个数，分成2路子有序序列 插入排序是稳定的排序方法,排序-Wang Wenjie,希尔排序,算法思想：先将整个待排序记录分割成若干个子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再进行一次全体记录的插入排序。具体做法：按照一定间隙抽取子序列，各子序列排序，逐步缩小间隙，扩大正序趋势结果。 希尔排序是不稳定的排序方法,排序-Wang Wenjie,快速排序,起泡排序：思想：逐次抽出最大、次大、次次大-。 具体做法：依次比较第i个关键字和第i+1 个关键字，大者排后，一趟得到最大值。（i=1,2,3,4,-n-1) 起泡排序是稳定的排
4、序方法快速排序：思想：一趟排序将序列分成两个部分，前者小于某个值，后者大于某个值。之后再次分别快速排序。做法：选取任意记录为“枢轴”，如序列的第一个记录为“枢轴”。 快速排序是不稳定的排序方法,排序-Wang Wenjie,堆排序,思想：每趟选取最小关键字、次小关键字、次次小关键字-。做法：建立一个完全二叉树，任何非终端结点的值均不大于其左、右孩子结点的值。输出堆顶，将其余的元素建立新的堆。 堆排序是不稳定的排序方法,排序-Wang Wenjie,归并排序,思想：将两个或两个以上的有序表组合成一个新的有序表。做法：先认为原始序列中每个关键字是一个序列，两两有序归并，逐步扩大子序列尺寸 二路归并排序是稳定的排序方法,排序-Wang Wenjie,基数排序（最低位优先）,思想：多级关键字排序，低位优先，逐步向高位。做法：一次分配和收集为一趟，三个关键字需要三趟。 基数排序是稳定的排序方法,
