数据结构课件：第10章 排序1插入排序和交换排序

1、第10章 内部排序选择排序 (直接排序、堆排序)概述插入排序 (直接排序、折半排序、希尔排序)交换排序 (冒泡排序、快速排序)归并排序基数排序概述10.1 概述排序：将数据元素的一个任意序列，重新排列成一个按关键字有序的序列。 例：将关键字序列：52, 49, 80, 36, 14, 58, 61, 23 调整为：14, 23, 36, 49, 52, 58, 61, 80 若按主关键字排序则结果惟一若按次关键字排序则结果可以不惟一(因有相同关键字) 概述10.1 概述 设 Ki、Kj (1in, 1jn, ij ) 分别为记录 Ri、Rj 的关键字，且 Ki = Kj ，在排序前的序列中 R

2、i 领先于 Rj (即 i j )。若在排序后的序列中 Ri 仍领先于 Rj ，则称所用的排序方法是稳定的；反之，则称所用的排序方法是不稳定的。 例：设排序前的关键字序列为：52, 49, 80, 36, 14, 58, 36, 23 若排序后的关键字序列为：14, 23, 36, 36, 49, 52, 58, 80， 则排序方法是稳定的。 若排序后的关键字序列为：14, 23, 36, 36, 49, 52, 58, 80， 则排序方法是不稳定的。 概述10.1 概述内部排序和外部排序 若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序； 反之，若参加排序的记录数量很大，整个

3、序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。 插入排序10.2 插入排序直接插入排序 初始状态4938659776132749 R0 R1 R2 R3 R4 R5 R6 R7 R8 i =2 i =3 3849659776132749 i =4 3849659776132749 i =5 384965769713274976i =6 384965769713274913i =7 384965769713274927i =8 3849657697132749494938659776132749 3849387 趟 排序 1 趟 排序 2 趟 排序 排序过程：先将序列中第 1 个

4、记录看成是一个有序子序列， 然后从第 2 个记录开始，逐个进行插入，直至整个序列有序。 直接插入排序10.2 插入排序void InsertSort ( SqList &L ) / 对顺序表 L 作直接插入排序。 for ( i = 2; i = L.length; + i ) if (L.ri.key L.ri -1.key) / InsertSort 在 r1. i-1中查找 ri 的插入位置; 对于在查找过程中找到的那些关键字 不小于 ri.key 的记录，在查找的同 时实现记录向后移动； 插入 ri ;L.r0 = L.ri; / 复制为监视哨 L.ri = L.ri -1; for

5、( j = i - 2; L.r0.key L.r j .key; - - j ) L.r j + 1 = L.r j ; / 记录后移 L.r j + 1 = L.r0; / 插入到正确位置 直接插入排序性能分析 10.2 插入排序比较次数： 移动次数： 0 最好的情况：待排序记录按关键字从小到大排列（正序） 比较次数： 移动次数： 最坏的情况：待排序记录按关键字从大到小排列（逆序） 直接插入排序性能分析 10.2 插入排序 由于待排记录序列是随机的，取上述二值的平均值。所以直接插入排序的时间复杂度为O(n2)。 直接插入排序是“稳定的”：关键码相同的两个记录，在整个排序过程中，不会通过比较

6、而相互交换。折半插入排序10.2 插入排序(1) 基本思想 考虑到 L.r1,.,i-1 是按关键字有序的有序序列，则可以利用折半查找实现“L.r1,i-1中查找 L.ri 的插入位置”如此实现的插入排序为折半插入排序。例：有6个记录，前5个已排序的基础上，对第6个记录排序。 15 27 36 53 69 42 15 27 36 53 69 42 15 27 36 53 69 42 15 27 36 42 53 69 10.2 插入排序(high36 )( 4253 ) high mid lowlow highmid high low折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的

7、原理寻找插入位置。待排序元素越多，改进效果越明显。折半插入排序算法10.2 插入排序void BinsertSort(SqList &L) / 折半插入排序 int i,low,high,mid; for(i=2; i= L.length; +i) L.r0=L.ri; /将L.r i 暂存到L.r0 low=1; high=i-1; While(low=high) /比较，折半查找插入位置 mid=(low+high)/2; / 折半 if (L.r0.key=low; j ) L.rj+1=L.rj; / 记录后移 L.rlow=L.r0; / 插入 / BInsertSort折半插入排序

8、算法分析10.2 插入排序 折半查找比顺序查找快，所以折半插入排序就平均性能来说比直接插入排序要快。 折半插入排序减少了关键字的比较次数，但记录的移动次数不变，其时间复杂度与直接插入排序相同。 在插入第 i 个对象时，需要经过 log2i +1 次关键码比较，才能确定它应插入的位置。 折半插入排序是一个稳定的排序方法。2-路插入排序10.2 插入排序(1) 基本思想 2-路插入排序是在折半插入排序的基础上改进的，目的是减少排序过程中移动记录的次数，但为此需要n个记录的辅助空间。2-路插入排序10.2 插入排序(2) 具体做法 另设一个和 L.r 同类型的数组d，首先将 L.r1 赋值给d1 ，

9、并将d1看成是在排好序的序列中处于中间位置的记录，然后从 L.r中第 2 个记录起依次插入到d1之前或之后的有序序列中。先将待插入记录的关键字和d1 的关键字进行比较。 若 L.rid1.key，则将 L.ri 插入到d1 之前的有序表中。反之，插入到d1 之后的有序表中。【初始关键字】 49 38 65 97 76 13 27 49 排序过程中d 的状态如下：i=1: (49) i=2: (49) (38)i=3: (49 65) (38)i=4: (49 65 97) (38)i=5: (49 65 76 97) (38)i=6: (49 65 76 97) (13 38)i=7: (49

10、 65 76 97) (13 27 38)i=8: (49 49 65 76 97) (13 27 38)finalfirst2路插入排序过程示例：firstfinalfinalfirstfinalfirstfinalfirstfinalfirstfinalfirstfinalfirstvoid Path2Insertion(SqList &L, SqList &d) d0 = L1;/L中D的第一个记录为d中排好序的记录。 int first = 0, final = 0;/first、final分别指示d中排好序的记录的第1个和最后1个记录的位置 for (int i = 2; i = l

11、ength; +i) /依次将L的第2个最后一个记录插入d中。 if (Li dfinal) /待插入记录大于d中最小值，插入到dfinal之后 final = final + 1; dfinal = Li; else /待插入记录大于d中最小值，小于d中最大值，插入到d的中间(需要移动d数组) int j = final +;/移动d尾部元素以便按序插入记录。 while (Li dj) d(j + 1) % length = dj; j = (j - 1 + length) % length; dj + 1 = Li; for (int i = 1; i = length; i +) /循

12、环把d赋给L。 Li = d(i + first - 1) % length;/线性关系。 2-路插入排序10.2 插入排序 2-路插入排序只能减少移动记录的次数，而不能绝对避免移动记录。 2-路插入排序中，移动记录的次数约为n2/8 。 当L.r1是待排序记录中关键字最小或最大的记录时，2-路插入排序就完全失去了它的优越性。表插入排序10.2 插入排序(1) 基本思想 通过改变排序过程中采用的存储结构，减少在排序过程中进行“移动”记录的操作。利用静态链表进行排序，并在排序完成之后，一次性地调整各个记录相互之间的位置，即将每个记录都调整到它们所应该在的位置上。表插入排序10.2 插入排序#de

13、fine MAXSIZE 100 /静态链表容量Typedef struct RcdType rc; /记录项 int next; /指针项 SLNode; /表结点类型Typedef struct SLNode rMAXSIZE+1; /0号单元为表头结点 int length; /链表当前长度 SLinkListType; /静态链表类型(2) 待排记录序列的存储结构表插入排序10.2 插入排序(3) 具体做法 首先将静态链表中数组下标为“1”的分量(结点)和表头结点构成一个循环链表，然后依次将下标为“2”至“n”的分量(结点)按记录关键字非递减有序插入到循环链表中。10.2 插入排序vo

14、idTableSort(int*a,intn) nexthead=0=-1; for(i=1;in;i+) if(ai=ahead) nexti=head; head=i; else p=head; while(nextp!=-1&anextpai) p=nextp; nexti=nextp; nextp=i; 初始状态012345678MAXINT493865977613274910-i=3012345678MAXINT4938659776132749201-key域next域i=2012345678MAXINT493865977613274910-38123650i=4012345678M

15、AXINT49386597761327492310-9740i=5012345678MAXINT493865977613274923140-i=6012345678MAXINT4938659776132749231504-i=7012345678MAXINT49386597761327496315042-i=8012345678MAXINT493865977613274963150472-7645136227724938表插入排序10.2 插入排序(4) 表插入排序性能分析 从表插入排序的过程可见，表插入排序的基本操作仍是将一个记录插入到已排好序的有序表当中。和直接插排序相比，不同之处仅是以修

16、改2n次指针值代替移动记录，排序过程中所需进行的关键字间的比较次数相同。因此表插入排序的时间复杂度仍是O(n2)。表插入排序10.2 插入排序(4) 表插入排序性能分析 表插入排序的结果只是求得一个有序链表，则只能对它进行顺序查找，不能进行随机查找，为了能实现有序表的折半查找，尚需对记录进行重新排列。10.2 插入排序1.我们都能理解，优秀排序算法的首要条件就是2.于是人们想了许许多多的排序办法，目的就是为了提高排序的速度。3.而在很长的时间里，众人发现尽管各种排序算法花样繁多，但时间复杂度都是O(n2)，似乎没法超越了。4.计算机学术界充斥着“排序算法不可能突破O(n2)”的声音？速度10.

17、2 插入排序 终于有一天，当一位科学家发布超越了O(n2)新排序算法后，紧接着就出现了好几种可以超越O(n2)的排序算法，并把内排序算法的时间复杂度提升到了O(nlog2n)。“不可能超越O(n2) ”彻底成为了历史。希尔排序10.2 插入排序基本思想：先将整个待排记录序列分割成若干子序列,分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。技巧：子序列的构成不是简单地“逐段分割”，而是将相隔某个增量dk的记录组成一个子序列,让增量dk逐趟缩短（例如依次取5,3,1），直到dk1为止。优点：让关键字值小的元素能很快前移，且序列若基本有序时，再用直接插入排序

18、处理，时间效率会高很多。312345665499725251321234562525136549971123456132525654997123456132525496597增量3增量2增量1希尔排序过程希尔排序10.2 插入排序38例：关键字序列 T=(49, 38, 65, 97, 76, 13, 27, 49*, 55, 04) 请写出希尔排序的具体实现过程。0123456789104938659776132749*5504初 态第1趟 (dk=5)第2趟 (dk=3)第3趟 (dk=1)4913134938276549*975576042738 65 49*97551355760455

19、13270427044949*4949*763876 65 65 9797551327044949*3876 65 9713 27 0449* 76 97 ri算法分析：开始时dk 的值较大，子序列中的对象较少，排序速度较快；随着排序进展，dk 值逐渐变小，子序列中对象个数逐渐变多，由于前面工作的基础，大多数对象已基本有序，所以排序速度仍然很快。希尔排序算法描述10.2 插入排序void ShellInsert ( SqList &L, int dk ) /一趟希尔插入排序 /1.前后记录位置的增量是dk； /2.L.r0只是暂存单元，不是哨兵。当j=0时，插入位置已找到 for ( i=dk

20、+1; i=L.length; +i ) if ( L.ri.key0 & (L.r0.key L.rj.key);j -= dk) L.rj+dk = L.rj; / 记录后移，查找插入位置 L.rj+dk = L.r0; / 插入 /ShellInsert希尔排序算法描述10.2 插入排序void ShellSort (SqList &L, int dlta , int t) / 按增量序列dlta0.t-1对顺序表L作希尔排序 for (k=0; k1; i-) /i表示趟数，最多n-1趟 flag=0; /开始时元素未交换 for (int j=2; j=i; j+) if (RjRj

21、-1) /发生逆序 temp=Rj; Rj=Rj-1; Rj-1=temp; flag=1; if(flag=0) return; / Bubblesort冒泡排序算法分析10.3 交换排序正序： 只需进行一趟排序，在排序过程中进行n-1次关键字间的比较，且不移动记录；时间复杂度为O(n) 。逆序： 需要进行n-1趟排序，需要进行n(n-1)/2次比较，并作等数量级的记录移动。总的时间复杂度为O(n2) 。 起泡排序方法是稳定的。适合于数据较少的情况。快速排序10.3 交换排序背景 起泡排序的过程可见，起泡排序是一个增加有序序列长度的过程，也是一个缩小无序序列长度的过程，每经过一趟起泡，无序序

22、列的长度只缩小1。 试设想：若能在经过一趟排序，使无序序列的长度缩小一半，则必能加快排序的速度。快速排序10.3 交换排序(1) 基本思想 通过一趟排序将待排序列以枢轴为标准划分成两部分，使其中一部分记录的关键字均比另一部分小，再分别对这两部分进行快速排序，以达到整个序列有序。 通常取第一个记录的值为基准值或枢轴。快速排序10.3 交换排序(2) 具体做法 附设两个指针low和high，初值分别指向第一个记录和最后一个记录，设枢轴为key； 1.从high 所指位置起向前搜索，找到第一个不大于基准值的记录与枢轴记录相互交换； 2.从low 所指位置起向后搜索，找到第一个不小于基准值的记录与枢轴

23、记录相互交换。 3.重复这两步直至low=high为止。快速排序10.3 交换排序lowhigh设Rs=52 为枢轴例： 52 52 49 80 36 14 58 61 97 23 75 high23 lowlow80highhighhighhigh14lowlow52一趟快速排序算法描述10.3 交换排序int Partition (Elem R , int low, int high) R0 = Rlow; pivotkey = Rlow.key; while (low high) /从两端交替向中间扫描 while (low = pivotkey) - - high; Rlow = Rh

24、igh; /将比枢轴记录小的移到低端 while (low high & Rlow.key = pivotkey) + + low; Rhigh = Rlow; /将比枢轴记录大的移到高端 Rlow = R0; /枢轴记录到位 return low; /返回枢轴位置 / Partition快速排序算法过程 10.3 交换排序无 序 的 记 录 序 列无序记录子序列 (1)无序子序列 (2) 枢轴 一次划分 分别进行一趟快速排序 有 序 的 记 录 序 列 快速排序算法描述10.3 交换排序void QSort ( Elem R , int low, int high ) /对序列Rlow.hi

25、gh进行快速排序 if (low high-1) /长度大于1 pivot = Partition( L,low,high); /将Rlow.high一分为二 QSort(L,low, pivot-1); /对低子表递归排序，pivo是枢轴 QSort(L, pivot+1, high); / 对高子表递归排序 / QSortvoid QuickSort(Elem R, int n) /对记录序列进行快速排序 QSort(R, 1, n); / QuickSort076，129，256，438，301，694，742，751，863，937076，129，256，301，301，694，742

26、，751，863，937076，129，256，751，937，863，742，694，301，438076，129，256，438，301，694，742，694，863，937256，301，751，129，937，863，742，694，076，438例：以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，写出执行快速算法的各趟排序结束时，关键字序列的状态。原始序列： 256，301，751，129，937，863，742，694，076，438第1趟第2趟第3趟第4趟要求模拟算法实现步骤25607630112975125675143807

27、6，129，256，301，438，694，742，751，863，937时间效率：O(nlog2n) 因为每趟确定的元素呈指数增加空间效率：O(log2n)因为算法的递归性，要用到栈空间稳 定 性：不稳定 因为可选任一元素为支点。快速排序算法详细分析10.3 交换排序可以证明，函数Quicksort的平均计算时间是O(nlog2n)。实验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个。快速排序是递归的，需要有一个栈存放每层递归调用时的指针和参数(新的low和high)。最大递归调用层次数与递归树的深度一致，理想情况为 log2(n+1) 。因此，要求存储开销为

28、 O(log2n)。快速排序算法详细分析10.3 交换排序最好情况：如果每次划分对一个对象定位后，该对象的左侧子序列与右侧子序列的长度相同，则下一步将是对两个长度减半的子序列进行排序，这是最理想的情况。此时，快速排序的趟数最少。最坏情况：即待排序对象序列已经按其关键码从小到大排好序的情况下，其递归树成为单支树，每次划分只得到一个比上一次少一个对象的子序列。这样，必须经过 n-1 趟才能把所有对象定位，而且第 i 趟需要经过 n-i 次关键码比较才能找到第 i 个对象的安放位置，总的关键码比较次数将达到n2/2快速排序是否真的比任何排序算法都快？10.3 交换排序设每个子表的支点都在中间（比较均衡），则：第1趟比较，可以确定1个元素的位置；第2趟比较（2个子表），可以再确定2个元素的位置；第3趟比较（4个子表），可以再确定4个元素的位置；第4趟比较（8个子表），可以再确定8个元素的位置； 只需log2n 1趟便可排好序。基本上是！因为每