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

Presentation on theme: "1、基本概念 2、插入排序 3、交换排序 4、选择排序 5、归并排序 6、基数排序 7、外部排序"— Presentation transcript:

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

2 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)可以是主关键字，也可以是次 关键字，甚至是若干个属性的组合。

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

4 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; }

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

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

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

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

9 Shell排序的例

10 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;

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

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

13 快速排序算法 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;

14 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

15 直接选择排序算法与分析 直接选择排序算法 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)。

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

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

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

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

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