软件技术基础第三章2基本排序.ppt

软件技术基础第三章2基本排序contents目录排序算法概述插入排序选择排序冒泡排序归并排序快速排序01排序算法概述0102排序算法的定义排序算法在计算机科学中扮演着非常重要的角色，因为它们可以应用于各种各样的计算和数据处理任务中。排序算法是一种能将一串数据按照特定顺序进行排列的算法。指将需要处理的所有数据都加载到内部存储器中进行排序。内部排序数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。外部排序排序算法的分类排序算法的时间复杂度取决于具体的算法和数据结构，不同的排序算法具有不同的时间复杂度。时间复杂度是指执行算法所需要的计算工作量，可以估算出程序对处理器的使用程度。常见的时间复杂度有：常数时间O(1)，线性时间O(n)，对数时间O(logn)，线性对数时间O(nlogn)，平方时间O(n2)，立方时间O(n3)，指数时间O(2^n)。排序算法的时间复杂度02插入排序比较待插入元素与已排序序列中的元素，找到合适的位置插入。重复上述过程，直到所有元素都插入到已排序序列中。将待排序的元素插入到已排序的序列中，从而得到一个新的、更长的已排序序列。插入排序的基本思想取出下一个元素，在已经排序的元素序列中从后向前扫描。重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。重复步骤2~5，直到所有元素都插入到已排序序列中。从第一个元素开始，认为该元素已被排序。如果该元素（已排序）大于新元素，将该元素移到下一位置。将新元素插入到该位置后。010203040506插入排序的实现过程当待排序序列已经有序时，时间复杂度为O(n)，其中n为序列长度。最好情况当待排序序列为逆序时，时间复杂度为O(n^2)。最坏情况时间复杂度为O(n^2)。平均情况插入排序只需要一个额外的存储空间来保存待插入的元素，因此空间复杂度为O(1)。空间复杂度插入排序的时间复杂度分析03选择排序每一趟从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置。直到全部待排序的数据元素排完。选择排序的基本思想在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。选择排序的实现过程最好情况时间复杂度：O(n^2)。最坏情况时间复杂度：O(n^2)。平均情况时间复杂度：O(n^2)。空间复杂度：O(1)。01020304选择排序的时间复杂度分析04冒泡排序比较相邻的元素：比较相邻的两个元素，如果前一个元素比后一个元素大，则交换它们的位置。针对所有的元素重复以上的步骤：除了最后一个已经排好序的元素。对每一对相邻元素做同样的工作：从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数。持续每次对越来越少的元素重复上面的步骤：直到没有任何一对数字需要比较，这表示数列已经排序完成。冒泡排序的基本思想比较与交换从起始位置开始，比较相邻的两个元素，如果前一个元素大于后一个元素，则交换它们的位置。每一轮比较后，最大的元素会被交换到序列的末尾。初始化设置两个指针i和j，分别指向待排序序列的起始位置和终止位置。迭代过程重复执行比较与交换操作，直到指针i和j相遇为止。此时，序列已经按照升序排列完成。冒泡排序的实现过程冒泡排序的时间复杂度分析最好情况当待排序序列已经有序时，冒泡排序只需要进行n-1次比较，时间复杂度为O(n)。最坏情况当待排序序列为逆序时，冒泡排序需要进行n(n-1)/2次比较和交换，时间复杂度为O(n^2)。平均情况冒泡排序的平均时间复杂度也为O(n^2)。因此，对于大规模数据的排序，冒泡排序并不是一种高效的算法。05归并排序