排序算法中体现出的奇妙思想
110 浏览量
2020-12-22
08:18:32
上传
评论
收藏 139KB PDF 举报
排序算法中体现出的奇妙思想排序算法中体现出的奇妙思想
排序算法中的奇妙思想排序算法中的奇妙思想
注意：本文的重点是分析排序算法中体现的一些重要是算法思维，旨在掌握排序算法的核心思想，并举一反三，并不是排序算注意：本文的重点是分析排序算法中体现的一些重要是算法思维，旨在掌握排序算法的核心思想，并举一反三，并不是排序算
法的入门科普，故不会详细介绍各种算法，但也会给出各种算法的法的入门科普，故不会详细介绍各种算法，但也会给出各种算法的Python实现，本文的结构如下：实现，本文的结构如下：
十大排序算法总结
选择、冒泡、插入、希尔排序的算法实现
归并、快排、堆排、桶排的详细剖析（奇妙思想的发源地）
一、十大排序算法总结一、十大排序算法总结
排序方法排序方法 平均时间复杂度平均时间复杂度 最优时间复杂度最优时间复杂度 最差时间复杂度最差时间复杂度 空间复杂度空间复杂度 稳定性稳定性 适用情况适用情况
冒泡排序 O(n2) O(n) O(n2) O(1) 稳定 序列基本有序或较短
快速排序 O(nlogn) O(nlogn) O(n2) O(nlogn) 不稳定 不在乎内存使用
插入排序 O(n2) O(n) O(n2) O(1) 稳定 序列基本有序或较短
希尔排序 O(n2) O(n1.3) O(n2) O(1) 不稳定 不推荐
选择排序 O(n2) O(n2) O(n2) O(1) 稳定 要求交换次数较少
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定 对内存有需求
归并排序 O(nlogn) O(nlogn) O(nogn) O(n ) 稳定 追求稳定，不在乎内存
计数排序 O(n+k) O(n+k) O(n+k) O(n+k) 稳定 便于获取数组最值
桶排序 O(n+k) O(n2) O(n) O(n+k) 稳定 便于获取数组最值
基数排序 O(n*k) O(n)*l O(n*k) O(n+k) 稳定 便于获取数组最值
归纳归纳
选择、冒泡、插入是三个基础的算法，都是稳定排序，其中冒泡和插入的最有时间复杂度是最快的，因此基本有序或较短的时
间就没必要追求高级算法了。
堆排、快排、希尔分别是上述三个算法的进阶版，都是不稳定排序，各有各的特点，需重点掌握。
归并排序作为一种高级算法，体现的分治思想，需重点掌握。
计数、桶排、基数排序都是非比较排序算法，都用了哈希思想（利用索引信息），都是稳定排序，但使用场景受限，但它们的
算法思想常能巧妙的解决问题，需重点掌握思想。
黄色标记出的四种算法便是本文要重点分析的四种奇妙思想。
二、选择、冒泡、插入、希尔排序的算法实现二、选择、冒泡、插入、希尔排序的算法实现
冒泡排序
def bubble_sort(nums):
# 基本思想：每轮倒序遍历，将最小值移到左侧。
flag = True # 当上一轮未进行交换，说明已经有序，flag用来实现最优复杂度。
for i in range(len(nums)):
if not flag: break
flag = False
for j in range(len(nums) - 1, i):
if nums[j] < nums[j - 1]:
nums[j], nums[j - 1] = nums[j - 1], nums[j] flag = True
选择排序
def selection_sort(nums):
# 基本思想：每轮将第一个数和后面所有数比较，交换它和后面数中的最小值。
for i in range(len(nums)):
mini = i
for j in range(i + 1, len(nums)):
if nums[j] < nums[mini]:
mini = j
nums[i], nums[mini] = nums[mini], nums[i]
插入排序
def insert_sort(nums):
# 基本思想：类似扑克牌的抓牌，将每个元素插入到前面已经有序的序列中。
for i in range(len(nums) - 1):
if nums[i] > nums[i + 1]:
# 将nums[i + 1] 插入到 nums[: i+1]中
temp, j = nums[i + 1], i
while nums[j] > temp and j >= 0:
nums[j + 1] = nums[j] j -= 1
nums[j + 1] = temp
评论0