1、基本概念 2、插入排序 3、交换排序 4、选择排序 5、归并排序 6、基数排序 7、外部排序 十七、排序 1、基本概念 2、插入排序 3、交换排序 4、选择排序 5、归并排序 6、基数排序 7、外部排序

1、基本概念 ⑴排序的定义 设有n个对象的序列为 {R0，R1，· · ·，Rn-1} 其对应的关键字序列为 {K0，K1，· · ·，Kn-1} 对（0，1， · · ·，n-1）确定一种排列（p0，p1， · · ·，pn-1）， 使相应的关键字满足非递减（或非递增）关系： Kp0≤Kp1≤· · ·≤Kpn-1 即使n个对象的序列成为 {Rp0，Rp1，· · ·，Rpn-1} 这样一种操作称为排序。 其中：关键字Ki，(i = 0, 1,· · ·, n-1)可以是主关键字，也可以是次 关键字，甚至是若干个属性的组合。

基本概念(续) ⑵稳定的排序 设待排序的序列中有两个或两个以上相等的关键字Ki=Kj， (0≤i，j≤n-1，i≠j)，且在排序前的序列中Ri处于Rj之前(即 i<j)。若排序后Ri仍处于Rj之前，称此种排序方法是稳定的。 否则称这个排序方法是不稳定的。 ⑶内排序与外排序 根据在排序过程中数据对象是否完全在内存，予以区分。 内排序是指在排序期间数据对象全部存放在内存的排序； 外排序是指在排序期间因数据对象个数太多，按照排序过程 的要求，分若干批放在内存中进行的排序。 ⑷排序的时间开销 按照排序的特点，排序的时间开销用算法执行中关键字比较 次数和数据移动次数来衡量。一般情况下用平均时间估算， 特殊情况也有按最好情况或最坏情况进行估算的。

2、插入排序 ⑴直接插入排序 基本思想：从序列前端开始，把序列分成两部分，前面部分是 已排好序的，即当要处理Ri时， Rp0，Rp1，· · ·，Rpi-1已排好 序。只要用Ri的关键字与 Rpi-1 、Rpi-2、· · ·的关键字顺序比较， 找到插入位置后，将Ri插入，相关的对象向后顺移。反复这个 过程直到序列中所有对象都处理完毕。 void InsertionSort(SeqList<Datatype> & SortableList ) { int firstunsorted, position; Datatype temp; for (firstunsorted = 1; firstunsorted<n; firstunsorted + +) if SortableList[firstunsorted]<SortableList[firstunsorted-1] position = firstunsorted; temp = SortableList[firstunsorted]; do { SortableList[position] = SortableList[position-1]; position - -; } while ( postion>0 && SortableList[position-1]> temp; SortableList[position] = temp; }

直接插入排序的例 示意图 firstunsorted temp 小于等于temp 大于temp unsorted 小于等于temp

直接插入排序性能分析 最好情况： 排序前序列已按关键字大小从小到大排列，每一趟只需与比较1 次关键字，移动2次数据对象。总计关键字比较为n-1次，数据 移动2(n-1)次。 最坏情况： 序列处于反序状态。即每一趟必须与前面所有的关键字作比较， 并每做1次比较，就要移动1次数据。总计有n-1趟，因此 总比较次数为 总移动次数为 平均时间复杂度为O(n2) 稳定性：从算法看，显然是稳定的。

由于前端是有序序列，可以考虑用折半搜索法确定插入位置。 但由于移动次数无法再减少，因此，时间复杂度没有本质改 善。 ②链表结构的直接插入排序 其它直接插入排序 ①利用折半搜索确定插入位置 由于前端是有序序列，可以考虑用折半搜索法确定插入位置。 但由于移动次数无法再减少，因此，时间复杂度没有本质改 善。 ②链表结构的直接插入排序 head current R0 R1 Ri Rn-1 ∧ ∧ R0 R1 Ri Rn-1 ∧ Rp0 Rpi-1 ∧ Ri Rn-1 ∧

高级插入排序 ⑵Shell排序 产生Shell排序背景 当n不大，并且原序列基本有序的情况下，直接插入有其优势。 基本思想：先将待排序的序列分解成几个子序列，对子序列 进行直接插入排序，然后缩小间距再分解成几个子序列，继 续对它们进行直接插入排序，如此进行若干趟，等到整个序 列基本有序后，再对整个序列施行直接插入排序。 分解子序列的间隔(增量)，是一个递减的，又称为减小增量排 序。 增量的序列有：d[k] = 2t-k+1 － 1，其中t为排序总趟数，k为某具体趟次。最后一趟，增量肯定是1，表示对整个序列排序。 还有其它的取法：d = currentlengh d/2 + 1 d/3 + 1 等等

Shell排序的例 49 38 65 97 76 13 27 84 55 04 49 34 13 49 87 89 49 84 87 38 55 89 04 65 49 97 34 76 13 13 27 49 49 38 04 49 34 13 27 84 55 65 97 76 13 49 87 89 13 27 49 49 65 89 34 38 49 84 97 04 13 55 76 87 13 34 04 27 38 13 49 49 55 49 84 76 65 97 87 89 04 13 13 27 34 38 49 49 49 55 65 76 84 87 89 97

Shell排序算法 void ShellSort(SeqList<Datatype> & list) { int increment = size/3; while (increment>=1){ ShellInsert( list, increment); increment = increment/3; } Void ShellInsert(Seqlist<Datatype> & list, int increment) for(i = increment; i<size; i + +) { Datatype temp = list[i]; int j = i; while (j>=increment && temp<list[j-increment]){ list[j] = list[ j – increment]; j － =increment; list[j] = temp;

起泡排序效率低的原因是数据对象移动太慢。 一个对象在序列中正确的位置应具有哪些特征？ 3、交换排序 ⑴起泡排序 ⑵快速排序(quick sort) 起泡排序效率低的原因是数据对象移动太慢。 一个对象在序列中正确的位置应具有哪些特征？ 各关键字不大于Ri的关键字 Ri 各关键字大于Ri的关键字

快速排序的例 49 38 65 97 76 13 27 49 i j j 27 38 65 97 76 13 49 49 i i j 27 38 49 97 76 13 65 49 i j j 27 38 13 97 76 49 65 49 i i j 27 38 13 49 76 97 65 49 ij j 27 38 13 49 76 97 65 49 完成一趟排序 分别对{27，38，13}和{76，97，65，49}排序。

快速排序算法 void QuickSort(SeqList<T> &list, const int left, const int right) { if (left<right) { int position = Partition(list, left, right); QuickSort(list, left, position－1); QuickSort(list, position+1, right); } void Partition(SeqList<T> &list, const int low, const int high) int i = low; int j = high; Datatype temp = list[low]; while (i<j) { while ((i<j)&&(list[j]>=temp)) {j - -}; list[i] = list[ j]; list[j] = temp; while ((i<j)&&(list[i]<=temp)) {i + +}; list[j] = list[i]; list[i] = temp; return position;

i+1个数据对象时，前面i个对象Rp0，Rp1，· · ·，Rpi-1已排好序。 4、选择排序 ⑴直接选择排序 基本思想：从序列前端开始，把序列分成两部分，即当要处理第 i+1个数据对象时，前面i个对象Rp0，Rp1，· · ·，Rpi-1已排好序。 只要在 Ri 、Ri+1、· · ·、 Rn－1中选择关键字最小的，作为Rpi。反 复这个过程直到序列中所有对象都处理完毕。 直接选择排序的示意图 Rp0，Rp1，· · ·，Rpi-1 Ri Ri+1、· · ·、 Rn－1 Rp0，Rp1，· · ·，Rpi-1 Ri Ri+1、· · ·、 Rk 、· · ·、 Rn－1 Rp0，Rp1，· · ·，Rpi-1、Rk Ri+1、· · ·、 Ri 、· · ·、 Rn－1

直接选择排序算法与分析 直接选择排序算法 void SelectSort(SeqList<T> &list ) { for (int i = 0; i<size－1; i ++) SelectElement( list, i ); } void SelectElement(SeqList<T> &list, const int i ) int k = i; // 当前最小关键字所在位置 for (int j = i+1; j<size; j + +) if ( list[j]<list[k]) k = j; if ( k!= i) { temp = list[k]; list[k] = list[i]; list[i] = temp; 选择趟数为n－1，比较次数为n－i － 1，移动次数最好情况 为0次，最坏情况为3(n－1)。

锦标赛排序的基本思想：首先对n个关键字两两比较，得到 个比较的优胜者，作为第一批比较的结果保留下来，然 直接选择排序的缺点是经常重复比较。 锦标赛排序的基本思想：首先对n个关键字两两比较，得到 个比较的优胜者，作为第一批比较的结果保留下来，然 后对这 对象再作两两比较，如此反复，直到选出一个关 键字最小为止。 08 21 08 21 25 08 63 21 25 49 25 16 08 63

锦标赛排序的算法 结点的结构 template <class T> class DataNode { public:: Datatype data; // 数据项 int index; // 结点号，完全二叉树存储下标 int active; // 参选标志 } 算法中的要点 计算数组大小：外结点数是大于等于n的2的最小幂次数 树的结点数等于2倍外结点减1 左右兄弟的确定 算法的时间复杂度 辅助空间太多

堆排序 堆排序的基本思想 “堆化”数组，使用filterdown形成初始堆； 通过交换和调整(filterdown)堆进行排序。 堆排序的性能 堆排序的时间复杂度 堆排序的空间复杂度为常数

基数排序 建立在多关键字的基础上，通过“分配”与“收集”进行排序。 基本思想： 设有关键字：K1、K2、· · ·、Kd，首先按最低位关键字Kd对所有 对象进行一趟排序，然后按次低位关键字Kd-1在上一趟排序结果 再排序，依次类推，直到按最高位K1排序结束。 对单关键字情况，也可以将单关键字分解成若干位的子关键字 组，然后对这个子关键字组按多关键字处理。如关键字是6位整 数，位数是6，基数是10；如果4位英文字母组成的关键字，则 位数是4，基数是26(假设不分大小写)。 按照基数设定所需队列的个数；设置两各指针数组，分别存放 队列的头和尾， “分配”与“收集”工作就借助这两个数组中的指 针完成。

基数排序示意图 基数排序 rear front 1 2 3 4 d－1 d 1 2 3 4 d －1 d