《数据结构及应用算法教程（修订版） 第3章 排序》由会员分享，可在线阅读，更多相关《数据结构及应用算法教程（修订版） 第3章 排序（50页珍藏版）》请在金锄头文库上搜索。
1、第3章 排序 3.1 概述 3.2 简单排序 3.3 先进排序 3.4 基数排序 3.5 各种排序方法的综合比较,3.1 概 述 排序的定义 排序的稳定性 排序的分类 内部排序方法的分类 1、什么是排序？ 排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。 例如：将下列关键字序列: 52, 49, 80, 36, 14, 58, 61, 23, 97, 75 调整为: 14, 23, 36, 49, 52, 58, 61 ,75, 80, 97,排序的确切定义: 假设含n个记录的序列为 R1, R2, ，Rn ,其相应的关键字序列为 K1, K2, ，
2、 Kn 对上述的记录序列排序就是确定序号1, 2, ,n的一种排列, p1, p2, , pn,使其相应的关键字满足如下的非递减的关系： Kp1Kp2Kpn 也就是使上述的记录序列成为一个按关键字有序的序列 Rp1, Rp2, ，Rpn 的操作称作排序。,2、排序的稳定性 当待排序记录中的各关键字ki ( i=1,2,n )都不相同时，排序结果惟一；当待排序记录中存在两个或两个以 上关键字相等的记录时，排序结果不惟一。 稳定性： 假设关键字ki=kj(ni1, 1jn,ij),并且在排序前记录ri领先rj, 若在排序后ri仍领先rj，则称排序是稳定 的；否则，称排序是不稳定的。,3、排序的分类
3、：内部排序和外部排序 若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之, 若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类 排序问题为外部排序。 4、内部排序的方法 内部排序的过程是一个逐步扩大记录的有序序列长度的过程。通常在排序的过程中，参与排序的记录序列中可 划分为两个区域： 1.有序序列区：其中的记录按关键字非递减有序。 2.无序序列区,一趟排序：使有序序列区中记录的数目增加一个或几个的操作，称为一趟排序。 基于不同的“扩大” 有序序列长度的方法，内部排序方法大致可分下列几种类型： 简单排序 先进排序 基数排序,待排记录的数据类型定义如下:
4、const MAXSIZE=20; / 待排顺序表最大长度 typedef int KeyType; / 关键字类型为整数类型 typedef struct KeyType key; / 关键字项 InfoType otherinfo; / 其它数据项 RcdType; / 记录类型 typedef struct RcdType rMAXSIZE+1; / r0闲置 int length; / 顺序表长度 SqList; / 顺序表类型,3.2 简单排序 选择排序 插入排序 起泡排序 希尔排序 各种排序方法的学习要点： 掌握基本思想 举例说明排序过程 书写算法 稳定性的判断 时间复杂度的分析,
5、3.2.1 选择排序 1、基本思想：从无序序列区Ri到Rn的n-i+1个记录中选出关键字最小的记录Rj和Ri交换，从而使有序序列区从R1到Ri-1扩大至R1到Ri。 2、举例： 一组关键字(491,38,65,492,76,13,27,52)进行选择排序。 初始( ) i=1 (13), 38, 65, 492, 76, 491, 27, 52 i=2 (13, 27), 65, 492, 76, 491, 38, 52 i=3 (13, 27, 38), 492, 76, 491, 65, 52 i=4 (13, 27, 38, 492) ,76, 491, 65, 52 i=5 (13,
6、27, 38, 492, 491) 76, 65, 52 i=6 (13, 27, 38, 492, 491, 52), 65, 76 i=7 (13, 27, 38, 492, 491, 52, 65),76,3、一趟选择排序算法（算法 3.1） void SelectPass( SqList k+ ) if ( L.rk.key L.rj.key ) j = k ； / 暂不进行记录交换，只记录位置 if ( i != j ) W=L.rj；L.rj =L.ri；L.ri = W； / 最后互换记录Rj 和Ri / SelectPass,算法 3.2 void SelectSort (Sq
7、List k+ ) / 在L.ri.L.length中选择key最小的记录 if ( L.rk.key L.rj.key ) j =k ； if ( i!=j ) W=L.rj；L.rj =L.ri；L.ri = W； / 与第i个记录交换 / SelectSort 4、稳定性：稳定的 5、时间复杂度：O(n2),3.2.2 插入排序 1、基本思想：是将当前无序序列区Ri到Rn中的记录Ri插入到有序序列区R1到Ri-1中，使有序序列区的长度增1。,2、举例 一组关键字(38,49, 65, 76, 27, 13, 91, 52)进行插入排序。此记录序列中的前4个记录已按关键字非递减有序排列，构
8、成了一个含有4个记录的有序序列：(38, 49, 65, 76)，现要将第5个(关键字为27)记录插入到上式的序列中去，以得到一个新的含5个记录的有序序列： ( 27, 38, 49, 65, 76)，称这个过程为一 趟插入排序。 3、一趟插入排序算法（算法 3.3） 实现“一趟插入排序”可分三步进行： （1）在R1.i-1中查找Ri的插入位置，R1.j.key Ri.key Rj+1.i-1.key； （2）将Rj+1.i-1中的所有记录均后移一个位置； （3）将Ri 插入(复制)到Rj+1的位置上。,利用L.r0分量“复制”待插入的记录，则在向前查找插入位置时，循环变量就不可能发生出界的情
9、况,称L.r0为“监视哨”。 void InsertPass( SqList / 插入到正确位置 / InsertPass,分析：（1）整个插入排序需进行n-1趟“插入”。（2）只含一个记录的序列必定是有序序列，故插入应从i=2起进行。（3）若第i个记录的关键字不小于第i-1个记录的关键字，插入就不不需要进行了。 void InsertSort ( SqList / 插入到正确位置 / if / InsertSort,4、稳定性：稳定的 5、时间复杂度：O(n2) (最坏情况: ) 3.2.3 起泡排序 1、基本思想：是通过对无序序列区中的记录进行相邻记录关键字间的“比较”和记录位置的“交换”
10、实现关键字较小的记录向“一头”飘移，而关键字较大的记录向“另一头”下沉，从而 达到记录按关键字非递减顺序有序排列的目标。 假设在排序过程中，记录序列R1到Rn分为无序序列R1到Ri和有序序列Ri+1到Rn两个区域，则本趟起泡排序的基本操作是：从第1个记录起，比较第1个记录和第2个记录的关键字，若呈“逆序”关系，则将两个记录交换，然后比较第2个记录和第3个记录的关键字，若呈“逆序”关系，则交换，依次类推，直至比较了Ri-1和Ri之后，该无序序列区中关 键字最大的记录将定位在Ri的位置上。,假设在排序过程中，记录序列R1.n的状态为： 2、举例说明: 初始关键字(491, 38,65,97, 76
11、, 13, 27, 492)进行起泡排序。,原始关键字: (491,38, 65, 97, 76, 13, 27, 492) 第1趟排序后：38 491 65 76 13 27 492 97 第2趟排序后：38 491 65 13 27 492 76 97 第3趟排序后：38 491 13 27 492 65 76 97第4趟排序后：38 13 27 491 492 65 76 97第5趟排序后：13 27 38 491 492 65 76 97第6趟排序后： 13 27 38 491 492 65 76 97 起泡排序结束。注意: （1）起泡排序的结束条件：在某一趟排序过程中没有进行 “交换
12、记录”。 （2）一般情况下，每经过一趟“起泡”,“i减1”,但并不是每趟都如此。,3、算法 void BubbleSort(SqList /一趟排序无序序列中最后一个记录的位置 / while / BubbleSort,38,27,49,15,66,53,72,81,94,27,38,15,49,53,66,15,38,15,27,void BubbleSort(SqList /记下进行交换 4、稳定性：稳定的 5、时间复杂度：O(n2),3.3 先进排序 3.3.1 快速排序（起泡法改进） 1、基本思想：通过一趟排序将待排记录序列分割成相邻的两个区域，其中一个区域中记录的关键字均比另一个区域
13、中记录的关键字小（区域内不见得有序），则可分别对这两个区 域的记录进行再排序，以达到整个序列有序。 2、假设待排序的原始记录序列为（Rs, Rs+1, , Rt-1, Rt）,则一趟快速排序的基本操作是：任选一个记录(通常选记录Rs)，以它的关键字作为“枢轴”，凡序列中关键字小于枢轴的记录均移动至该记录之前；反之，凡序列中关键字大于枢轴的记录均移动至该记录之后。 致使一趟排序之后，假设“枢轴”为Ri,记录的无序序列Rs到Rt将被分割成两部分: Rs到Ri-1和Ri+1到Rt，且使 Rj.key Ri.key Rk.key （ 其中：s j i-1、i+1 k t ),3、一趟快速排序的具体过程
14、： 假设枢轴记录的关键字为pivotkey，附设两个指针low和high,它们的初值分别为s和t。则:（1）将枢轴记录(假设选Rs)赋给临时变量R0（2）检测指针high所指记录，若Rhigh.key=pivotkey,则减小high,否则将Rhigh移至指针low所指位置，同时low+;（3）检测指针low所指记录，若Rlow.key=pivotkey,则增加 low,否则将Rlow移至指针high所指记录位置，同时high- - 重复进行上述两个方向的检测，直至low=high为止。此时low和high所指位置即为枢轴记录的位置，最后再将R0移至Rlow。,4、一趟快速排序算法(算法3.6
15、) int Partition (RedType R, int low, int high) pivotkey = Rlow.key; / 枢轴记录关键字 R0=Rlow； / 将枢轴记录移至数组的闲置分量 while (low=pivotkey) - -high; Rlow+=Rhigh; / 将比枢轴记录小的记录移到低端 while (lowhigh / 返回枢轴所在位置 ,31,暂存枢轴记录R0,12,12,68,68,23,23,45,45,31,31,快速排序的“一次划分过程”如下所示：,31,5、举例说明一趟快速排序的过程(假设49为枢轴记录) 初始关键字: ( 491 38 65
16、 97 76 13 27 492 ) 其一趟快速排序结果: ( 27 38 13) 491 (76 97 65 492 ) 总结：一趟快速排序又称“一次划分”。接着再对一次划分后的枢轴两侧的左右区域继续如法炮制，即整个快速排序的过 程可递归进行。 6、快速排序算法：若待排的原始记录序列中只有一个记录，则显然已有序，不再需要进行排序；否则首先对该无序的记录序列进行“一次划分”，之后分别对分割所得两个子序列“递 归”进行快速排序。,/对记录序列Rs.t进行快速排序 void QSort (RcdType R , int s, int t ) if (s t) / 长度大于1 pivotloc = Partition(R,
