数据结构与算法课件：内部排序.ppt

导致快速排序效率不高的主要原因是划分时选择的枢轴不好在最左位置元素、中间位置元素及最右位置元素中选择中间值作为枢轴，划分后，两个部分都不会为空，每个部分中最少含有一个元素。枢轴的这种选择方法称为三元取中方法排序当n值很小时，它的优越性并不突出使用直接插入排序来替代快速排序快速排序需要一个栈作为辅助空间，故最坏情况下空间复杂度为O(n)第四节选择排序选择排序（selectionsort）算法重复地选择特定值放到其最终位置，从而完成一组值的排序。即对于数组中的每个位置，算法选出应该处在那个位置的值，并将它一次性地放置到位简单选择排序堆排序简单选择排序第一趟扫描时从全部n个元素中找到最小值放到数组的第一个位置第二趟扫描时从剩余的n-1个元素中找到最小值放到数组的第二个位置一般地，第k趟扫描时从n-k+1个元素中找到最小值放到数组的第k个位置。直到只剩余一个元素时，不需要再做任何处理，排序过程结束简单选择排序示例初始：42683526702579596365i=1:25683526704279596365i=2:25263568704279596365i=3:25263568704279596365i=4:25263542706879596365i=5:25263542596879706365i=6:25263542596379706865i=7:25263542596365706879i=8:25263542596365687079i=9:25263542596365687079堆排序?最小堆和最大堆例7-11设有数据序列：44,97,76,29,13,7,50,9,20，将它们建成最大堆，画出最后得到的堆的结果。例7-12初始最大堆，输出堆顶97，给出调整后的新堆堆排序堆排序划分段及合并段划分数据段时是按照一定的间隔数进行的，将相距等间隔数的元素放在同一个数据段内间隔数为3时所有下标等于3i(i≥0)的元素都分在第一个数据段中所有下标等于3i+1(i≥0)的元素分在第二个数据段中所有下标等于3i+2(i≥0)的元素分在第三个数据段中一般地，间隔数为k时，全部数据会分成k个数据段合并的过程易如反掌希尔排序的过程首次划分数据段每一个数据段看成是一个组，在组内进行直接插入排序依同样的机制，将全部数据划分为更长的数据段，数据段内的数据个数增多，段数减少每组内依次进行直接插入排序最后一趟排序的k值为1，也就是全部元素都在同一个组内，对所有元素进行直接插入排序增量序列di的取法取d0=m，di+1=?di/2?取d0=m，di+1=?(di+1)/2?取d0=m，di+1=?(di-1)/3?取d0=m，di+1=?(di-1)/2?希尔排序42,68,35,1,70,25,79,59,63,65,26,80,17,36增量为5黑色字是原始数据，红色字是组内排序后的数据结果：25,68,17,1,65,26,79,35,36,70,42,80,59,63d=54225???2526???2642???第一组??6868???7979???8080??第二组???3517???5935???1759?第三组????11???6336???3663第四组?????7065???6570????第五组25,68,17,1,65,26,79,35,36,70,42,80,59,63增量为3结果：1,35,17,25,42,26,59,63,36,70,65,80,79,68d=3251?125?7959?7070?5979?第一组??6835?6542?3563?4265?6368第二组???1717?2626?3636?8080??第三组最后一趟使用增量1，数据均在同一组内。这是第三趟排序结果：1,17,25,26,35,36,42,59,63,65,68,70,79,80用希尔排序方法对一个数据序列进行排序时，若第1趟排序结果为 9,1,4,13,7,8,20,23,15