还剩25页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
《数据结构排序》课件•引言•插入排序•选择排序•交换排序目•非比较排序•性能比较与选择合适的排序算法录contents01CATALOGUE引言排序的定义与重要性排序的定义排序是将一组数据按照一定的顺序排列的过程排序的重要性排序是数据处理、分析和挖掘的基础,对于数据检索、分析、预测等具有重要意义排序算法的分类按照时间复杂度分类线性时间复杂度排序如插入排序、冒泡排0102序等;非线性时间复杂度排序如快速排序、归按照稳定性分类0304并排序等稳定排序如冒泡排序、插入排序等;不稳定排序如快速排序、归并排序等050602CATALOGUE插入排序直接插入排序总结词直接插入排序是一种简单直观的排序算法,通过逐个比较待排序元素与已排序元素,将待排序元素插入到合适的位置详细描述直接插入排序的基本思想是将待排序元素插入到已排序序列中,使得已排序序列保持有序具体实现时,从第一个元素开始,依次将待排序元素插入到已排序序列的合适位置,直到所有元素都插入完毕希尔排序总结词希尔排序是插入排序的一种改进版本,通过比较相隔一定间隔的元素,使得数组中的部分有序子序列可以在较小的范围内进行比较和交换详细描述希尔排序的基本思想是将待排序元素分成若干个子序列,先对子序列进行直接插入排序,然后逐渐缩小子序列的间隔,重复进行直接插入排序,直到子序列的间隔为1时,整个数组就变得有序了折半插入排序总结词折半插入排序是插入排序的一种改进版本,通过二分查找法找到待排序元素在已排序序列中的位置,从而减少比较次数详细描述折半插入排序的基本思想是在直接插入排序的基础上,使用二分查找法找到待排序元素在已排序序列中的位置,然后将其插入到该位置这样可以减少比较次数,提高算法的效率03CATALOGUE选择排序简单选择排序01总结词简单直观,但效率较低02详细描述每次从未排序部分选择最小(或最大)的元素,将其放到已排序部分的末尾,重复此过程直到所有元素都排好序03时间复杂度On^204适用场景数据量较小,对效率要求不高的场合堆排序总结词详细描述高效稳定,但实现较复杂将数据重新组织成一个大顶堆(或小顶堆),然后依次将堆顶元素与堆尾元素交换并调整堆,直至整个数组有序时间复杂度适用场景Onlogn数据量大,对效率要求高的场合希尔排序(作为选择排序的变种)总结词详细描述改进型选择排序,效率较高先将整个数据分成若干个子序列,对每个子序列进行直接选择排序,逐步缩小整个数据的“粒度”,最后按全有序和部分有序的框架进行插入排序时间复杂度适用场景On^2-Onlogn数据量较大,且对效率有一定要求的场合04CATALOGUE交换排序冒泡排序总结词简单但效率较低的排序算法详细描述冒泡排序是一种简单的排序算法,它重复地遍历待排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成冒泡排序时间复杂度On^2适用场景数据量较小,对效率要求不高的场景快速排序总结词详细描述时间复杂度适用场景高效的平均情况下的排序算法快速排序是一种分而治之的排平均情况下Onlogn,最坏情数据量大,对效率有一定要求序算法,它将一个数组分为两况下On^2的场景个子数组,左边的元素都比右边的小,然后再递归地对这两个子数组进行快速排序,直到整个数组有序归并排序输入归并排序是一种采用分治法的排序算法,它将一个数标题稳定且易于理解的排序算法详细描述组分成两个子数组,分别对子数组进行排序,然后将两个有序的子数组合并成一个有序的数组总结词时间复杂度数据量大,对稳定性有一定要求的场景适用场景Onlogn05CATALOGUE非比较排序计数排序总结词详细描述适用场景优缺点计数排序是一种线性时间复计数排序的核心思想是统计计数排序适用于正整数数组,计数排序的优点是时间复杂杂度的排序算法,适用于正数组中每个元素的出现次数,尤其适用于元素范围较小的度低,为On+k,其中k为整数数组并根据出现次数将元素放到情况元素范围;缺点是需要知道正确的位置上该算法适用元素范围,且对于元素范围于正整数数组,对于非正整较大的情况,需要消耗大量数数组或负整数数组,需要的额外空间先进行适当的预处理桶排序•总结词桶排序是一种线性时间复杂度的排序算法,适用于均匀分布的数据•详细描述桶排序的核心思想是将数据分到有限数量的桶子里,然后对每个桶子里的数据进行排序,最后将各个桶子里的数据连接起来即可该算法适用于均匀分布的数据,对于非均匀分布的数据,需要适当调整桶的数量和大小•适用场景桶排序适用于均匀分布的数据,尤其适用于数据量较大且数据范围较小的情况•优缺点桶排序的优点是时间复杂度低,为On+k,其中k为桶的数量;缺点是需要消耗大量的额外空间,且对于非均匀分布的数据,需要进行适当的调整基数排序总结词详细描述基数排序是一种非比较整数排序算法,适用于正基数排序的核心思想是将整数按位数切割成不同整数和负整数数组的数字,然后按每个位数分别比较该算法适用于正整数和负整数数组,对于小数和浮点数数组,需要进行适当的预处理适用场景优缺点基数排序适用于正整数和负整数数组,尤其适用基数排序的优点是时间复杂度较低,为Onk,其于元素范围较小的情况中k为位数;缺点是需要消耗大量的额外空间,且对于位数较多的情况,需要进行适当的调整06CATALOGUE性能比较与选择合适的排序算法时间复杂度比较时间复杂度概念排序算法执行所需的时间随数据量变化的情况01On^2如冒泡排序、选择Onlogn如归并排序、快排序速排序0203On如计数排序、基数排0405Ologn如二分查找序空间复杂度比较01020304空间复杂度概念O1Ologn On排序算法所需额外空间的大小原地排序,如冒泡排序、选择归并排序、快速排序的递归调如堆排序的辅助数组排序用栈选择合适的排序算法根据数据量大小选择实际应用场景小规模数据可以选择简单直观考虑内存限制、实时性要求等的算法,大规模数据则需考虑因素效率根据数据特点选择稳定性考虑如数值范围小则适合计数排序,如需要保持相等元素原有顺序,有序数据适合插入排序,无序应选择稳定的排序算法数据适合选择或冒泡排序THANKS感谢观看。