数据结构chapter-10(2)堆排序算法-

第第页数据结构chapter10(2)堆排序算法1、数数据据结结构构数数据据结结构构DATASTRUCTURE,DS授课教师：郭艳授课教师：郭艳授课班级授课班级:191091-4授课班级授课班级:1910914中国地质大学计算机学院中国地质大学计算机学院2021年春年春上堂课要点回顾上堂课要点回顾?排序排序排序的定义和类型排序的定义和类型?排序的定义和类型排序的定义和类型?排序算法的衡量标准排序算法的衡量标准?排序算法排序算法?直接插入排序直接插入排序?直接选择排序直接选择排序?冒泡排冒泡排序序序序?希尔排序希尔排序?堆排序堆排序堆排序堆排序第第十九十九次次课课第第十九十九次次课课阅读：阅读：朱战立，第266-275页习题：习题：作业17数据结构课程内容数据结构课程内容???直接选择排序直接插入排序?

2、???????堆排序希尔排序冒泡排序直接选择排序??????基数排序归并排序快速排序堆排序算法堆排序算法?先建初始最大堆先建初始最大堆???对对n个结点产生堆的过程是从个结点产生堆的过程是从i=开始到开始到0，反复调用筛选算法，每次将，反复调用筛选算法，每次将x[i]~x[n-1]建成最大堆建成最大堆最终将最终将[0][1]建成初始最大堆建成初始最大堆??12/?n，，最终将最终将x[0]~x[n-1]建成初始最大堆建成初始最大堆?进行进行n-1趟堆排序趟堆排序?设设i表示趟数，从表示趟数，从n-1到到0，每趟，每趟?交换交换堆顶记录堆顶记录x[0]与当前未排序子序列的最终一个与当前未排序子序列的最终一个记录记录x[i]，，x[0]定位在正确位置定位

3、在正确位置记录记录x[i]，，x[0]定位在正确位置定位在正确位置?重新调整重新调整，把，把x[0]“拉下来”，使记录“拉下来”，使记录x[0]~x[i-1]成成为最大堆为最大堆为最大堆为最大堆【堆排序算法】【堆排序算法】voidHeapSort(DataTypex[],intn)voidHeapSort(DataTypex[],intn)/*用堆排序法对记录用堆排序法对记录x[0]~x[n--1]排序排序*/{inti;{;/*将将x[0]~x[n--1]建成初始的最大堆建成初始的最大堆*/for(i=n/2-1;i=0;i)(;;)HeapAdjust(x,n,i);for(i=n--1;i0;i){/*交换堆顶记录与当前未排序子

4、序列的最终一个记录交换堆顶记录与当前未排序子序列的最终一个记录x[i]的位置的位置*/swap(x,0,i);/*重新调整，把重新调整，把x[0]“拉下来”，使记录“拉下来”，使记录成为最大堆成为最大堆x[0]~x[i--1]成为最大堆成为最大堆*/HeapAdjust(x,i,0);}}}堆排序算法分析?不稳定排序算法不稳定排序算法?总时间代价为总时间代价为O(nlog2n)?一一次建堆次建堆，，n次删除堆顶并重新调整次删除堆顶并重新调整次建堆次建堆，，n次删除堆顶并重新调整次删除堆顶并重新调整?建堆：建堆：O(n)?删除堆顶并重新调整为堆删除堆顶并重新调整为堆:O(log2n)?删除堆顶并重新调整为堆删除堆顶并重新调整为堆:O(log2n)?空间

5、代价为空间代价为O(1)10.4.2快速排序?算法思想：算法思想：?选择选择轴值轴值〔〔pivot〕〕?将序列将序列划分划分为两个子序列为两个子序列L和和R，，使得使得L中的中的?将序列将序列划分划分为两个子序列为两个子序列L和和R，，使得使得L中的中的全部记录都小于或等于轴值，全部记录都小于或等于轴值，R中的全部记中的全部记录都大于轴值录都大于轴值，，即轴值已经定位在正确位置即轴值已经定位在正确位置录都大于轴值录都大于轴值，，即轴值已经定位在正确位置即轴值已经定位在正确位置对子序列对子序列L和和R递归递归进行快速排序进行快速排序LR?对子序列对子序列L和和R递归递归进行快速排序进行快速排序轴值选择〔SelectPivot〕?尽可能尽可能使使L和和R

6、的长度相等的长度相等?选择策略：选择策略：选择最左边的记录选择最左边的记录?选择最左边的记录选择最左边的记录?选择中间记录，须将中间记录和最左边记录选择中间记录，须将中间记录和最左边记录互换互换互换互换?选择平均值，须将平均值的记录和最左边记选择平均值，须将平均值的记录和最左边记录互换〔可使录互换〔可使L和和R的长度相等〕的长度相等〕?随机选择随机选择，，须将选择的须将选择的记记录和最录和最左边记左边记录录互互随机选择随机选择须将选择的录和最录须将选择的录和最录换换划分过程〔Partition〕?划分是整个快速排序的关键划分是整个快速排序的关键?划分后使得划分后使得L中全部记录位于轴值左边，中全部记录位于轴值左边，R中记录位于轴值右边中记录位于轴值右

7、边即轴值已经定位即轴值已经定位R中记录位于轴值右边中记录位于轴值右边，，即轴值已经定位即轴值已经定位于正确位置于正确位置LR例例：：初始关键字初始关键字：：[465513429451770]temp.key例例：：初始关键字初始关键字：：[465513429451770]进行进行一一次交换后次交换后[17]55134294517[70]ijj进行次交换后进行次交换后：：[17]55134294517[70]进行二次交换后进行二次交换后[17]551342945[5570]ji进行二次交换后进行二次交换后：：[17]551342945[5570]ij进行三次交换后：进行三次交换后：[175]1342945[5570]jiii进行四次交换后：进行四次交换

8、后：[1751342]94[945570]jij完成一趟排序：完成一趟排序：[1751342]46[945570]二趟排序之后二趟排序之后[135]17[42]46[7055]94ij二趟排序之后二趟排序之后：：[135]17[42]46[7055]94三趟排序之后：三趟排序之后：[5]13174246[55]7094【快速排序的轴值选择函数】intSelectPivot(intlow,inthigh){/*参数参数lhih分别表示待排序序列的左右端分别表示待排序序列的左右端{/*参数参数low,high分别表示待排序序列的左右端分别表示待排序序列的左右端下标下标*///选择选择最左记录最左记录作为轴值作为轴值//选择选择最左记录最左记录作为轴值作为

9、轴值returnlow;}}【快速排序的分割函数】intPartition(DataTypex[],intlow,inthigh){//分割后轴值已到达正确位置分割后轴值已到达正确位置{//分割后轴值已到达正确位置分割后轴值已到达正确位置DataTypetemp;//存放轴值的临时变量存放轴值的临时变量itil//i为左指针为左指针j为右指针为右指针inti=low;//i为左指针为左指针，，j为右指针为右指针intj=high;//将轴值存放在临时变量中将轴值存放在临时变量中//将轴值存放在临时变量中将轴值存放在临时变量中temp=x[i];//开始分割开始分割ij不断向中间移动不断向中间移动直到相遇直到相遇//开始分割开始分割，，i,j不断向中间

10、移动不断向中间移动，，直到相遇直到相遇while(itk){inti,j,k,power=1;LQueue*tub;tub=(LQueue*)malloc(sizeof(LQueue)*d);f(i0idi++)for(i=0;id;i++)QueueInitiate(for(i=0;im;i++){if(i==0)power=1;elsepower=power*d;for(j=0;jn;j++)jjj{k=a[j].key/power-(a[j].key/(power*d))*d;QueueAppend(}}k=0;for(j=0;jd;j++)while(QueueNotEmpty(tub[j])!=0)while(QueueNotEmpty(t

11、ub[j])!=0){QueueDelete(k++;}}}}基数排序算法分析?稳定稳定的排序算法的排序算法?空间代价：空间代价：ＯＯ(d)?d个子个子序列的头尾指针序列的头尾指针?d个子个子序列的头尾指针序列的头尾指针?时间代价：时间代价：ＯＯ(m(n+d))?对于对于n个记录个记录执行执行一一次安排和收集的时间为次安排和收集的时间为?对于对于n个记录个记录，，执行次安排和收集的时间为执行次安排和收集的时间为O(n+d)?不需要移动记录本身，只需要修改记录的不需要移动记录本身，只需要修改记录的next指指针针针针?当当d或或m较小时，这种方法较为节约时间较小时，这种方法较为节约时间10.7排序方法的性能比较10.7排序方法的性能比较算法最大时算法最

12、大时间间平均时平均时间间最小时间帮助空最小时间帮助空间代价间代价稳定稳定性性间间间间间代价间代价性性直接插入排直接插入排序序O(n2)O(n2)O(n)O(1)稳定稳定序序折半插入排折半插入排序序O(n2)O(n2)O(nlog2n)O(1)稳定稳定序序冒泡排序冒泡排序O(n2)O(n2)O(n)O(1)稳定稳定直接选择排序直接选择排序O(n2)O(n2)O(n2)O(1)不稳定不稳定算法最大时间平均时间最小时间帮助空算法最大时间平均时间最小时间帮助空间代价间代价稳定稳定性性间代价间代价性性Shell排序排序O(n3/2)O(n3/2)O(n3/2)O(1)不稳不稳定定定定快速排序快速排序O(n2)O(nlog2n)O(nlog2n)O(log2n)

13、不稳不稳定定归并排序归并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定稳定归并排序归并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定稳定堆排堆排序序O(nlog2n)O(nlog2n)O(nlog2n)O(1)不稳不稳序序(g2)(g2)(g2)()不稳不稳定定基数排序基数排序O(m(n+d))O(m(n+d))O(m(n+d))O(d)稳定稳定基数排序基数排序O(m(n+d))O(m(n+d))O(m(n+d))O(d)稳定稳定小结?n很小或基本有序时n很小或基本有序时直接插入排序直接插入排序比较有比较有效效?盼望以最快速度选择出若干最大或最小盼望以最快速度选择出若干最大或最小?盼望以最快速度选择出若

14、干最大或最小盼望以最快速度选择出若干最大或最小元素，元素，堆排序堆排序或直接选择最合适或直接选择最合适?综合性能综合性能快速排序最正确快速排序最正确作业作业17