第9章 排序探讨.ppt

第九章 排序;10.1 概述;10.1 概 述;一、什么是排序？; 一般情况下， 假设含n个记录的序列为{ R1, R2, …， Rn } 其相应的关键字序列为 { K1, K2, …，Kn };二、内部排序和外部排序;三、内部排序的方法;　基于不同的“扩大” 有序序列长度的方法，内部排序方法大致可分下列几种类型：;待排记录的数据类型定义如下:; 10. 2 插 入 排 序;有序序列R[1..i-1];实现“一趟插入排序”可分三步进行：;直接插入排序（基于顺序查找）;一、直接插入排序; 对于在查找过程中找到的那些关键字不小于R[i].key的记录，并在查找的同时实现记录向后移动；;令 i = 2，3，…, n, 实现整个序列的排序。;初始关键字序列：【13】，6，3，31，9，27，5， 11 第一次排序： 【6, 13】, 3, 31, 9, 27, 5, 11 第二次排序： 【3, 6, 13】, 31, 9, 27, 5, 11 第三次排序： 【3, 6, 13，31】, 9, 27, 5, 11 第四次排序： 【3, 6, 9, 13，31】, 27, 5, 11 第五次排序： 【3, 6, 9, 13，27, 31】, 5, 11 第六次排序： 【3, 5, 6, 9, 13，27, 31】, 11 第七次排序： 【3, 5, 6, 9, 11，13，27, 31】 ;void InsertionSort ( SqList L ) { // 对顺序表 L 作直接插入排序。 for ( i=2; i=L.length; ++i ) if (L.r[i].key L.r[i-1].key) { } } // InsertSort;内部排序的时间分析：;对于直接插入排序：;时间效率： 因为在最坏情况下，所有元素的比较次数总和为（0＋1＋…＋n-1)→O(n2)。其他情况下也要考虑移动元素的次数。 故时间复杂度为O(n2) 空间效率：仅占用1个缓冲单元——O（1） 算法的稳定性：稳定; 因为 R[1..i-1] 是一个按关键字有序的有序序列，则可以利用折半查找实现“在R[1..i-1]中查找R[i]的插入位置”，如此实现的插入排序为折半插入排序。;void BiInsertionSort ( SqList L ) { } // BInsertSort;low = 1; high = i-1; while (low=high) { };14 36 49 52 80; 三、希尔排序（又称缩小增量排序）;将记录序列分成若干子序列，分别对每个子序列进行插入排序。;;void ShellInsert ( SqList L, int dk ) { for ( i=dk+1; i=n; ++i ) if ( L.r[i].key L.r[i-dk].key) { L.r[0] = L.r[i]; // 暂存在R[0] for (j=i-dk; j0(L.r[0].keyL.r[j].key); j-=dk) L.r[j+dk] = L.r[j]; // 记录后移，查找插入位置 L.r[j+dk] = L.r[0]; // 插入 } // if } // ShellInsert;void ShellSort (SqList L, int dlta[], int t) { // 增量为dlta[]的希尔排序 for (k=0; kt; ++t) ShellInsert(L, dlta[k]); //一趟增量为dlta[k]的插入排序 } // ShellSort;开始时d 的值较大，子序列中的对象较少， 排序速度较快；随着排序进展，d 值逐渐变 小，子序列中对象个数逐渐变多，由于前面 工作的基础，大多数记录已基本有序，所以 排序速度仍然很快。 时间效率：O(n(log2n)2) 空间效率：O（1）—因为仅占用1个缓冲单元 算法的稳定性：不稳定;练习：;10.3 快 速 排 序;一、起泡排序;例：关键字序列 T=(21，25，49，25*，16，08），请按从小到大的顺序，写出冒泡排序的具体实现过程。;void BubbleSort(Elem R[ ], int n) { while (i 1) {