Python数据结构与算法-第7章-排序算法

一案例：电商平台商品列表案例：电商平台商品列表案例描述

假设我们是一家电商公司的技术团队，我们的电商平台上有数以万计的商品需要进行排序展示，以便顾客能够方便地找到自己感兴趣的商品。这些商品的排序需要根据不同的指标来进行，比如价格、销量、评分等上图为“案例实例”案例：电商平台商品列表案例实现实现形式（具体见课本案例）新建一个空的列表。从待排序商品列表中，取出价格最高的商品，并放入新列表的末尾。重复步骤2，直到待排序商品列表被取光。二排序算法排序算法排序算法的定义上图为“不同排序规则示例”排序算法是一种将一组数据按照特定规则进行重新排列的算法。其主要目的是将数据按照某种顺序排列，使得数据具有可读性、易于查找和操作。排序算法可以按照不同的规则进行排序，比如按照数字大小、字母顺序（ASCII码顺序）或其他自定义规则等。排序算法常见排序算法基于比较的排序算法插入排序选择排序冒泡排序快速排序归并排序非基于比较的排序算法桶排序计数排序基数排序排序算法排序算法分析时间复杂度空间复杂度稳定性排序算法排序算法分析上图为“稳定排序和不稳定排序示例”三插入排序插入排序算法原理上图为“插入排序算法示例”插入排序算法实现实现形式（具体见课本案例）从第一个元素开始，该元素可以认为已经被排序取出下一个元素，在已经排序的元素序列中从后向前扫描如果该元素（已排序）大于新元素，将该元素移到下一位置重复步骤3，直到找到已排序的元素小于或者等于新元素的位置将新元素插入到该位置后重复步骤2~5，直到所有元素均排序完毕插入排序算法分析时间复杂度（最好、最坏、平均）空间复杂度稳定性插入排序算法优化之希尔排序实现形式（具体见课本案例）选择增量分组与预排序逐渐缩小增量四选择排序选择排序算法原理上图为“选择排序算法示例”选择排序算法实现实现形式（具体见课本案例）从待排序序列中找到最小（或最大）的元素，将其与序列的第一个元素交换位置，使得第一个位置为最小（或最大）元素。从剩余的未排序序列中继续寻找最小（或最大）的元素，将其与序列的第二个元素交换位置，使得第二个位置为第二小（或第二大）元素。依次类推，重复步骤1~步骤2，直到所有元素都排序完毕选择排序算法分析时间复杂度空间复杂度稳定性五冒泡排序冒泡排序算法原理第1轮冒泡排序第3轮冒泡排序第5轮冒泡排序第2轮冒泡排序第4轮冒泡排序第6轮冒泡排序冒泡排序算法实现实现形式（具体见课本案例）从待排序列的第一个元素开始，依次比较相邻的两个元素，如果前面的元素大于（或小于）后面的元素，则交换它们的位置，使得较大的元素往后移动。继续重复上述过程，直到比较到待排序列的倒数第二个元素，此时最大（或最小）的元素会被交换到待排序列的最后一个位置。从待排序列的第一个元素开始，重复步骤1到步骤2，但是每次内循环的范围会减少一个元素，即不再考虑已经排序好的部分。冒泡排序算法分析时间复杂度（最好、最坏、平均）空间复杂度稳定性六快速排序快速排序算法原理上图为“快速排序分割过程基本思路”快速排序算法实现实现形式（具体见课本案例）选择基准元素分割过程递归过程合并过程快速排序算法分析时间复杂度（最好、最坏、平均）空间复杂度稳定性七归并排序归并排序算法原理上图为“归并排序过程示例”归并排序算法实现实现形式（具体见课本案例）分解递归进行排序并合并归并排序算法分析时间复杂度空间复杂度稳定性归并排序算法分析特征归并排序快速排序时间复杂度O(nlogn)平均情况O(n

log

n)，最坏情况O(n2)空间复杂度O(n)平均情况O(logn)，最坏情况O(n)稳定性稳定不稳定实现复杂度较简单较复杂归并排序和快速排序的比较八桶排序桶排序算法原理上图为“桶排序过程示例”桶排序算法实现实现形式（具体见课本案例）确定桶的数量分配元素到桶中对每个桶中的元素进行排序合并桶中的元素桶排序算法分析时间复杂度（最坏、平均）空间复杂度稳定性九计数排序计数排序上图为“统计元素出现次数过程示例”算法原理上图为“计数数组累加过程示例”上图为“反向填充输出有序序列过程示例”计数排序算法实现实现形式（具体见课本案例）统计元素出现的次数计算每个元素在有序序列中的位置根据位置将元素放置到有序序列中输出有序序列计数排序算法分析时间复杂度空间复杂度稳定性十基数排序基数排序上图为“基数排序过程示例”算法原理基数排序算法实现实现形式（具体见课本案例）确定排序的位数按照位数分组对每个位数进行排序基数排序算法分析时间复杂度空间复杂度稳定性十一小结与习题小结与习题本章小结常见的排序算法及其实现分类排序算法平均时间复杂度最好情况最坏情况空间复杂度是否原地稳定性基于比较的排序算法冒泡排序O(n2)O(n)O(n2)O(1)原地稳定选择排序O(n2)O(n)O(n2)O(1)原地不稳定插入排序O(n2)O(n)O(n2)O(1)原地稳定希尔排序O(nlogn)O(nlog2n)O(nlog2n)O(1)原地不稳定归并排序O(nlogn)O(nlogn)O(nlogn)O(n)非原地稳定快速排序O(nlogn)O(nlogn)O(n2)O(logn)原地不稳定非基于比较的排序算法计数排序O(n+k)O(n+k)O(n+k)O(k)非原地稳定桶排序O(n+k)O(n+k)O(n2)O(n+k)非原地稳定基数排序O(n×k)O(n×k)O(n×k)O(n+k)非原地稳定小结与习题习题

？希尔排序是哪种排序算法的优化?A.冒泡排序

B.插入排序C.快速排序

D.归并排序

？选择排序的时间复杂度是多少?A.O(n)

B.O(nlogn)C.O(n^2)

D.O(n^3)

？快速排序的空间复杂度是多少?A.O(n)

B.O(logn)C.O(nlogn)

D.O(1)小结与习题习题

？桶排序的时间复杂度是?A.O(n)

B.O(nlogn)C.O(n^2)

D.O(k)

？计数排序适用于哪种类型的待排序序列?A.元素取值范围较小

B.元素取值范围较大C.元素数量较小

D.元素数量较大

？希尔排序是通过一系列的间隔值来分割待排序序列的，这些间隔值通常是?A.2的幂

B.质数C.斐波那契数列

D.等差数列小结与习题习题×/√桶排序的时间复杂度是O(nlogn)。×/√计数排序是一种稳定的排序算法。×/√基数排序的时间复杂度取决于待排序序列的长度和每个元素的位数。×/√快速排序是一种稳定的排序算法。×/√归并排序的空间复杂度是O(n)。小结与习题习题

？假设我们有一个待排序的列表为：[5,3,8,4,2]，使用冒泡排序将其变为升序序列，经过第1轮冒泡排序后，列表变为____。经过第2轮冒泡排序后列表变为____。最终一共要经过____轮冒泡排序后，列表变为有序。

？基数排序适用于待排序元素的位数____且取值范围____的情况。十二实训任务实训任务任务

你是一名教务处的工作人员，负责管理学生成绩数据。现在你需要编写一个程序，对学生成绩进行排序，并输出排名结果，以便及时了解学生的表现情况。具体要求如下：1.从文件中读取学生成绩数