数据结构和算法设计-第10章_排序11-10

1/45,第十章 排序,2/45,实验与课程安排,3/45,实验：第三次实验，13周周五(19 Nov)下午14:0016:00，2#机房第四次实验，14周周三(24 Nov)下午16:0018:00，1#机房本周五停课一次，下周三最后一次课期末考试时间： 15周周五（3 Dec）14:0016:00?答疑一次，具体时间？,4/45,10.1 概述,设R1 R2 R3 Rn 是n个记录，k1,k2, k3 kn为它们的关键字，排序就是将记录按关键字递增（或递减）的次序排列起来。,5/45,排序的分类,按记录的存放位置分类有 内部排序：待排记录存放在RAM中进行排序的过程 外部排序：待排记录数量很大，内存容纳不下，排序过程中尚需访问外存的排序过程按排序原则分类（内部排序） 插入排序 交换排序 选择排序 归并排序 基数排序,6/45,稳定性,在待排记录序列中，任何两个关键字相同的记录，用某种排序方法排序后相对位置不变，则称这种排序方法是稳定的，否则称为不稳定的。,待排序列： 49,38,65,97,76,13,27,49 排序后: 13,27,38,49,49,65,76,97 稳定排序后: 13,27,38,49,49,65,76,97不稳定,7/45,待排记录的存储顺序关键字类型定义 typedef int KeyType; 记录类型定义 typedef struct KeyType key; /关键字域 /其它域 RedType;,待排记录的存储,8/45,顺序表类型定义 typedef struct RedType rMAXSIZE+1; int length; SqList,9/45,10.2 插入排序,基本思想 依次将待排记录插入到已排好序的有序子表中，并使插入后的子表仍保持有序，直到全部记录插入完毕；初始时，有序子表中只有一个元素。,例 49 38 65 97 76 13 27 49 55 04,10/45,直接插入排序,例： 49 38 65 97 76 13 27 49 （49）38 65 97 76 13 27 49 （38 49）65 97 76 13 27 49 （38 49 65）97 76 13 27 49 （38 49 65 97） 76 13 27 49 （38 49 65 76 97）13 27 49 （13 38 49 65 76 97）27 49 （13 27 38 49 65 76 97）49 （13 27 38 49 49 65 76 97）,11/45,void InsertSort(SqList /插入正确位置 /InsertSort,12/45,如果 R1.i-1 是一个按关键字有序的有序序列，则可以利用折半查找实现“在R1.i-1中查找Ri的插入位置”，如此实现的插入排序过程为折半插入排序。,二、折半插入排序,13/45,void BiInsertionSort ( SqList &L ) / BInsertSort,/在 L.r1.i-1中折半查找插入位置；,for ( i=2; i=high+1; -j ) L.rj+1 = L.rj; / 记录后移,L.rhigh+1 = L.r0; / 插入,14/45,low = 1; high = i-1;while (low=high) ,m = (low+high)/2; / 折半,if (L.r0.key L.rm.key) high = m-1; / 插入点在低半区else low = m+1; / 插入点在高半区,/在 L.r1.i-1中折半查找插入位置；,15/45,14 36 49 52 80,58 61 23 97 75,i,low,high,m,m,low,low,m,high,14 36 49 52 58 61 80,23 97 75,i,low,high,m,high,m,high,m,low,例如:,再如:,插入位置,插入位置,L.r,L.r,16/45,10.3 交换排序,基本思想： 将待排记录中两两记录关键字进行比较，若逆序则交换位置（借助交换）。 例：49 38 65 97 76 13 27 49,起泡排序 49 38 65 97 76 13 27 49 38 49 65 76 13 27 49 97 一趟起泡排序后“最大数”沉底,17/45,快速排序,选定一记录R，将所有其他记录关键字k与该记录关键字k比较, 若 kk 则将记录换至R之后; 继续对R前后两部分记录进行快速排序，直至排序范围为1;,例 49 38 65 97 76 13 27 49 55 04,18/45,49 38 65 97 76 13 27 49,49,一趟快速排序,(2749),(9749),(1349),(i=j),19/45,int Partition(SqList /返回枢轴位置/Partition,20/45,27 38 13 49 76 97 65 49 13 27 38 49 49 65 76 97 13 27 38 49 49 65 76 97 13 27 38 49 49 65 76 97,两趟快速排序结束,三趟快速排序结束,快速排序,21/45,void Qsort(SqList ,void QuickSort(SqList ,22/45,10.4 选择排序,基本思想在待排记录中依次选择关键字最小的记录，放在最前面；再在剩余的记录中选择最小的记录排在次前面；.; 逐渐缩小范围直至全部记录选择完毕。,例 49 38 65 97 76 13 27 49,23/45,一、简单选择排序,49 38 65 97 76 13 27 49 1338 65 97 76 49 27 49 13 2765 97 76 49 38 49 13 27 3865 97 76 49 49 13 27 38 4965 97 76 49 13 27 38 49 4965 97 76 13 27 38 49 49 6597 76 13 27 38 49 49 65 76 97,24/45,void SelectSort(SqList /SelectSort,49 38 65 97 76 13 27 49,13 38 65 97 76 49 27 49,25/45,二、堆排序,一颗完全二叉树，如果满足下面的条件，则称其为堆：根结点关键字左、右孩子结点的关键字；左、右子树也是堆称为堆；,大根堆,不是堆,26/45,小根堆,不是堆,27/45,堆的另一定义 对于一个关键码序列K1,K2,Kn，如果满足KiK2i, KiK2i+1, (i=0,1, ,n/2-1 )，则称其为堆（大根堆）。,28/45,筛选操作(FilterDown),29/45,筛选操作(FilterDown),30/45,筛选操作(FilterDown),31/45,筛选操作(FilterDown),32/45,建堆,从堆的最后一个分支结点（第n/2个元素） ，自底向上逐步筛选把调整为堆,33/45,建堆,从堆的最后一个分支结点（第n/2个元素） ，自底向上逐步筛选把调整为堆,34/45,建堆,从堆的最后一个分支结点（第n/2个元素） ，自底向上逐步筛选把调整为堆,35/45,建堆,从堆的最后一个分支结点（第n/2个元素） ，自底向上逐步筛选把调整为堆,36/45,建堆,从堆的最后一个分支结点（第n/2个元素） ，自底向上逐步筛选把调整为堆,37/45,建堆,从堆的最后一个分支结点（第n/2个元素） ，自底向上逐步筛选把调整为堆,38/45,建堆,从堆的最后一个分支结点（第n/2个元素） ，自底向上逐步筛选把调整为堆,39/45,建堆,从堆的最后一个分支结点（第n/2个元素） ，自底向上逐步筛选把调整为堆,40/45,建堆,从堆的最后一个分支结点（第n/2个元素），自底向上逐步筛选把调整为堆,41/45,堆排序,建堆循环，直到堆为空： 将堆顶元素与堆最后的元素互换；将其余的元素筛选成堆；,42/45,建堆,43/45