数据结构-排序课件.pptVIP

数据结构-排序ppt课件CATALOGUE目录排序算法概述插入排序选择排序交换排序归并排序基数排序各种排序算法的比较与总结01排序算法概述0102排序算法的定义排序算法在计算机科学中扮演着非常重要的角色，它们是许多计算任务的基础。排序算法是一种能将一串数据按照特定顺序进行排列的算法。指将需要排序的数据全部加载到内存中进行排序，例如：插入排序、选择排序、交换排序、归并排序等。内部排序指需要排序的数据量太大，无法全部加载到内存中，需要借助外部存储设备进行排序，例如：外部归并排序等。外部排序排序算法的分类排序算法的应用场景数据库系统需要对大量数据进行排序，以便进行高效的查询和检索操作。文件系统需要对文件和目录进行排序，以便用户可以更方便地浏览和管理文件。数据挖掘和分析中需要对数据进行排序，以便发现数据中的模式和趋势。计算机图形学中需要对图形数据进行排序，以便进行高效的渲染和操作。数据库系统文件系统数据挖掘和分析计算机图形学02插入排序将待排序的元素按其排序码的大小，逐个插入到已经排好序的有序序列中，直到所有元素插入完毕。从第一个元素开始，该元素可以认为已经被排序；取出下一个元素，在已经排序的元素序列中从后向前扫描；如果该元素（已排序）大于新元素，将该元素移到下一位置；重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；将新元素插入到该位置后；重复步骤2~5。最好情况下为O(n)，最坏和平均情况下为O(n^2)。基本思想算法步骤时间复杂度直接插入排序在直接插入排序的基础上，利用二分查找的思想来减少比较次数。从第一个元素开始，该元素可以认为已经被排序；取出下一个元素，在已经排序的元素序列中利用二分查找的方法找到其应该插入的位置；将该位置及其之后的元素后移一位，为新元素腾出空间；将新元素插入到该位置；重复步骤2~4。虽然比较次数减少，但移动次数并未改变，所以时间复杂度仍为O(n^2)。基本思想算法步骤时间复杂度折半插入排序希尔排序算法步骤选择一个增量序列t1，t2，…，tk，其中titj,tk=1；按增量序列个数k，对序列进行k趟排序；每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。基本思想先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行依次直接插入排序。时间复杂度最坏情况下为O(n^2)，最好情况下为O(n^1.3)。03选择排序基本思想在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。时间复杂度简单选择排序的时间复杂度为O(n^2)，其中n为待排序元素的个数。稳定性简单选择排序是不稳定的排序算法。简单选择排序基本思想：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。时间复杂度：堆排序的时间复杂度为O(nlogn)，其中n为待排序元素的个数。稳定性：堆排序是不稳定的排序算法。优点：堆排序在最坏的情况下也能保证时间复杂度为O(nlogn)，并且其空间复杂度为O(1)，是一种效率较高的排序算法。堆排序04交换排序010405060302基本思想：通过相邻元素之间的比较和交换，使得每一趟循环都能将最大（或最小）的元素“浮”到序列的一端。算法步骤1.从序列的第一个元素开始，比较相邻的两个元素，如果前一个元素比后一个元素大，则交换它们的位置。2.每一趟循环都将最大（或最小）的元素放到了正确的位置，因此下一趟循环可以少比较一次。3.重复执行上述步骤，直到整个序列都有序为止。时间复杂度：最好情况下为O(n)，最坏和平均情况下为O(n^2)。冒泡排序基本思想：通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序算法步骤1.选择一个基准元素，通常选择序列的第一个元素。2.将序列中比基准元素小的元素放到它的左边，比它大的元素放到它的右边。快速排序快速排序3.对基准元素左边的子序列和右边的子序列分别进行快速排序。时间复杂度：最好情况下