各种排序算法详解及优劣对比

2024-07-09 13:17| 来源: 网络整理| 查看: 265

从时间复杂度和空间复杂度进行考虑。

相关性：排序时是否需要比较元素

稳定性：相同元素排序后是否可能打乱

时间空间复杂度：随着元素增加时间和空间随之变化的函数

一.简单插入排序

插入排序，顾名思义就是基本操作是插入，不断把一个个元素插入一个序列中，最终得到排序序列。插入过程中需要一个个的处理未排序元素，最简单的方法就是按下标处理。处理一个元素时留下一个空位，如果该空位与已排序序列相连，就可以直接用作该序列的延伸位置，也就是简单插入排序。示意图及代码如下：

1.过程图解

2.代码实现 def insert_sort(lst): for i in range(1,len(lst)): x=lst[i] j=i while j>0 and lst[j-1] 0: # 从增量值开始遍历比较 for i in range(gap, len(arr)): j = i current = arr[i] # 元素与他同列的前面的每个元素比较，如果比前面的小则互换 while j - gap >= 0 and current < arr[j - gap]: arr[j] = arr[j - gap] j -= gap arr[j] = current # 缩小增量（间隔）值 gap //= 2 return arr 3.算法分析

比较性：排序时元素之间需要比较，所以为比较排序

稳定性：因为希尔排序是间隔的插入，所以存在相同元素相对顺序被打乱，所以是不稳定排序

时间复杂度：最坏时间复杂度O(n^2)平均复杂度为O(n^1.3)

空间复杂度：只需要常数个辅助单元，所以空间复杂度也为O(1)

记忆方法：插入排序是每轮都是一小步，希尔排序是先大步后小步，它第一个突破O(n2)的排序算法。联想起阿姆斯特朗登月之后说：这是我个人一小步，却是人类迈出的一大步。

三.简单选择排序

选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，所以称为：选择排序

设第一个元素为比较元素，依次和后面的元素比较，比较完所有元素找到最小的元素，将它和第一个元素互换

重复上述操作，我们找出第二小的元素和第二个位置的元素互换，以此类推找出剩余最小元素将它换到前面，即完成排序

1.过程图解

2.代码实现 def selection_sort(lst): for i in range(0,len(lst)): x=lst[i] minid=i for j in range(i,len(lst)): if j

【本文地址】

公司简介

联系我们