分析10第十章排序

1、2017年8月第十章 排序SortingData structures10.1 排序的基本概念排序：将数据元素按关键字递增或递减的次序排列内排序：待排序的数据全部在内存中外排序：待排序的数据不全在内存中排序的方法： 插入排序 交换排序 选择排序 归并排序 基数排序排序算法的性能指标： 时间复杂度 空间复杂度 算法的稳定性排序前：12,45,123,67,45,89稳定排序后：12,45, 45,67, 89, 123不稳定排序后：12, 45,45, 67, 89, 123排序用的数据元素的类型定义 typedef int KeyType; / 关键字类型 typedef struct Key

2、Type key; / 关键字项 InfoType data; / 其他数据项 RecType; / 数据元素类型10.2 插入排序 基本思想每次将一个待排序的元素,按其关键字大小插入到前面已经排好序的子表中的适当位置,直到全部元素都排好序为止。R0R1Ri-1RiRi+1Rn-1有序部分无序部分1、直接插入排序R0R1Ri-1RiRi+1Rn-1j=i-1/ 直接插入排序算法(非降序和升序)void InsertSort(RecType R , int n) int i, j; RecType temp; for (i=1; i=0 & temp.keyRj.key) Rj+1=Rj; /

3、将关键字大于Ri.key的记录后移 j-; Rj+1=temp; / 在j+1处插入Ri Ri0) for (i=gap;i=0 & tmp.key0; i-) / 将第i大的元素冒泡至Ri, for ( j=0; jRj+1.key) temp=Rj; Rj=Rj+1; Rj+1=temp; / 改进的冒泡排序算法(非降序和升序)void BubbleSort(RecType R , int n) int i, j, exchanged; RecType temp; for (i=n-1; i0; i-) / 将第i大的元素冒泡至Ri, exchanged=0; for ( j=0; jRj

4、+1.key) temp=Rj; Rj=Rj+1; Rj+1=temp; exchanged=1; if( !exchanged ) return; 最好情况（原始数据顺序有序）比较次数0交换次数时间复杂度复杂度O(n)最坏的情况（原始数据逆序有序）比较次数交换次数复杂度O(n2)n-1平均情况复杂度O(n2)空间复杂度 O(1)稳定性稳定2、快速排序基本思想a1:j-1ajajaj+1:naja1aian无序表划分49386597761327485541338448274976975565例. 无序表以 49 作为划分值，一趟划分后的部分有序表对a1:j-1快速排序aj对aj+1:n 快速排

5、序对子表快排划分元素划分(部分排序)的原理4938659776132748554jkr=R0r=R0; j=1; k=n-1;while(j=k) while( j=k & Rj=r.key) j+; while( j=r.key) k-; if(jk) tmp=Rj; Rk=Rj; Rk=temp; j+; k-; R0=Rk; Rk=r; 扫描方向1338448274976975565划分结果/ 快速排序算法(非降序和升序)void QuickSort(RecType R , int s, int t) int j, k;RecType r, temp; if (st) / 区间内至少存在

6、2个元素的情况 r=Rs; j=s+1; k=t; / 用区间的第1个记录作为划分值 while(j=k) while( j=k & Rj=r.key) j+; / 找下一个大于划分值的Rj while( j=r.key) k-; / 找下一个小于划分值的Rk if(jk) / 交换Rj, Rk tmp=Rj; Rk=Rj; Rk=temp; j+; k-; Rs=Rk; Rk=r; / 通过交换Rs, Rk，将划分元素存储到Rk QuickSort(R, s, k-1); / 对左区间递归快排 QuickSort(R, k+1, t); / 对右区间递归快排 最好情况时间复杂度最坏情况平均情

7、况空间复杂度 O(log2n)稳定性不稳定O(nlog2n)O(n2)O(nlog2n)10.4 选择排序1、直接选择排序/ 直接选择排序算法(非降序和升序)void SelectSort(RecType R , int n) int i, j; RecType temp; for (i=0; in-1; i+) for (j=i+1; jn; j+) if (Rj.keyRi.key) temp=Ri; Ri=Rj; Rj=temp; 每次从待排序的数据中选出关键字最小(最大)的元素，顺序地放在已排序的子表的最后，直到完成全部排序。最好情况时间复杂度最坏情况平均情况空间复杂度 O(1)稳定性

8、不稳定O(n2)O(n2)O(n2)2、堆排序 n 个关键字 K1, K2, Kn 的顺序表可看成是一棵完全二叉树的顺序存储表， 最小堆：KiK2i, KiK2i+1; 最大堆：KiK2i, KiK2i+1;这样的完全二叉树的根节点称为堆顶元素。显然，堆顶元素为顺序表的最大值或最小值。68790132459876513240无序表初始最大堆0876513249选择排序后重构堆并选择6879013245无序表9876513240初始最大堆/ 节点往二叉树根节点方向迁移一步的算法void Shift(RecType R , int low, int high) int i=low, j=2*i;

9、RecType temp=Ri; while (j=high) if(jhigh & Rj.keyRj+1.key) j+; if (tem.keys) / i 的初值为最后一个非终端节点 for ( i=s+(t-s+1)/2-1; i=1; i-) Shift(R, i, t);/ 最大堆排序算法(非降序和升序)void HeapSort(RecType R , int n) int i; RecType temp; CreateMaxHeap (R, 1, n); / 建立初始最大堆 for(i=n; i=2; i-) / 将堆顶元素交换到位置 i tmp=R1; R1=Ri; Ri=t

10、mp; Shift(R, 1, i-1); / 对R1:i-1重构最大堆 时间复杂度最坏情况平均情况空间复杂度 O(1)稳定性不稳定O(nlog2n)O(nlog2n)10.5 归并排序 将两个相邻的有序表子合并成单一有序表。二路归并排序过程示例：初始18 2 20 34 12 32 6 16 1 52 18 20 34 12 32 6 16 1 5第1趟2 18 20 34 6 12 16 32 1 5第2趟2 6 12 16 18 20 32 34 1 5第3趟1 2 5 6 12 16 18 20 32 34 第4趟第一个问题：怎样将相邻的两个有序表归并成单个有序表？void Merge

11、 (RecType R , int low, int mid, int high) / 非降序 RecType bn; int l=low, h=mid+1, k=l; while (l=mid) & (h=high) / 部分合并 if (Rl.keymid) while (h=high) bk+=Rh+; / 转储剩余部分 else while(llow 时,分割：MergeSort(low, (low+high)/2)Rlow R(low+high)/2R(low+high)/2+1 RhighR low R highMergeSort( (low+high)/2+1, high)有序子

12、表有序子表Merge(low, (low+high)/2, high)有序表/ 归并排序算法void MergeSort (low, high) int mid; if (lowhigh) mid=(low+high)/2; MergeSort(low, mid); MergeSort(mid+1, high); Merge(low, mid, high); 时间复杂度： O(nlog2n).空间复杂度： O(n).稳定性：稳定.10.6 基数排序每个关键字的值拆分成位，每位的取值个数称为基数 r，关键字的位数用 d 表示。如十进制 276，可拆分成三位 2, 7, 6, r=10, d=3.

13、对关键字的每一位（从低位到高位，反之亦然）： 将 n 个关键字按位的值“分配” 到 r 个队列； 按位值的大小顺序将 r 个队列中的元素进行“收集” ，构成包含全部关键字的部分有序表；5200例：114, 179, 572, 835, 309, 141, 646, 520141157221144835564663091799按第一位（最低位）做第一趟分配第一趟收集结果: 520, 141, 572, 114, 835, 646, 179, 309309011415202835364614141795727第二趟收集结果: 309, 114, 520, 835, 141, 646, 572, 1

14、79按第二位做第二趟分配第一趟收集结果: 520, 141, 572, 114, 835, 646, 179, 30917914111413093572520564668358最后的收集结果: 114, 141, 179, 309, 520, 572, 646, 835第二趟收集结果: 309, 114, 520, 835, 141, 646, 572, 179按第三位做第三趟分配时间复杂度： O(d(n+r).空间复杂度： O(n).稳定性：稳定.设初始线性表和最终有序表均用队列表示，则按平均时间将排序方法分为三类： （1）平方阶O(n2)排序，一般称为简单排序，例如直接插入、直接选择和冒泡排序； （2）线性对数阶O(nlog2n)排序，如快速、堆和归并排序； （3）线性阶O(n)排序，如基数排序（假设r、d为常量）。 本章小结排序方法时间复杂度空间复杂度稳定性平均情况最坏情况最好情况直接插入排序O(n2)O(n2)O(n)O(1)稳定希尔排序O(n1.3)O(1) 不稳定冒泡排序O(n2)O(n2)O(n)O(1) 稳定快速排序O(nlog2n)O(n2)O(