史上最简单十大排序算法(Python实现) |
您所在的位置:网站首页 › 随机数排序python › 史上最简单十大排序算法(Python实现) |
目录 十大排序算法(Python实现) 一. 算法介绍及相关概念解读 算法分类 相关概念 1. 交换排序 1.1 冒泡排序(Bubble Sort) 1.2 快速排序(Quick Sort) 2. 插入排序 2.1 简单插入排序(Insert Sort) 2.2 希尔排序(Shell Sort) 3.选择排序 3.1 简单选择排序(Select Sort) 3.2 堆排序(Heap Sort) 4. 归并排序 4.1 二路归并排序(Two-way Merge Sort) 5. 线性时间非比较类排序 5.1 计数排序(Counting Sort) 5.2 桶排序(Bucket Sort) 5.3 基数排序(Radix Sort) 十大排序算法(Python实现) 一. 算法介绍及相关概念解读算法分类 十种常见排序算法可以分为两大类: 非线性时间比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此称为非线性时间比较类排序。 线性时间非比较类排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此称为线性时间非比较类排序。
![]() 冒泡排序对n个数据操作n-1轮,每轮找出一个最大(小)值。 操作只对相邻两个数比较与交换,每轮会将一个最值交换到数据列首(尾),像冒泡一样。 每轮操作O(n)次,共O(n)轮,时间复杂度O(n^2)。 额外空间开销出在交换数据时那一个过渡空间,空间复杂度O(1) 快速排序基于选择划分,是简单选择排序的优化。 每次划分将数据选到基准值两边,循环对两边的数据进行划分,类似于二分法。 算法的整体性能取决于划分的平均程度,即基准值的选择,此处衍生出快速排序的许多优化方案,甚至可以划分为多块。 基准值若能把数据分为平均的两块,划分次数O(logn),每次划分遍历比较一遍O(n),时间复杂度O(nlogn)。 额外空间开销出在暂存基准值,O(logn)次划分需要O(logn)个,空间复杂度O(logn) 希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列,也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法(第4版)》的合著者Robert Sedgewick提出的。 3.选择排序 3.1 简单选择排序(Select Sort) 初始状态:无序区为R[1..n],有序区为空;第i趟排序(i=1,2,3…n-1)开始时,当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中-选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区;n-1趟结束,数组有序化了。简单选择排序同样对数据操作n-1轮,每轮找出一个最大(小)值。 操作指选择,即未排序数逐个比较交换,争夺最值位置,每轮将一个未排序位置上的数交换成已排序数,即每轮选一个最值。 每轮操作O(n)次,共O(n)轮,时间复杂度O(n^2)。 额外空间开销出在交换数据时那一个过渡空间,空间复杂度O(1)。 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |