登 录
注 册
< 编程语言
Python
Java
Go
SQL
数据结构与算法
定义与复杂度
数组与链表
栈、队列与递归
初级排序
中级排序
排序总结与优化
二分查找
跳表原理与实例
堆和堆排序
动态规划
选择合适的算法
热门推荐>>>
中台架构
中台建设与架构
Hadoop
源码分析-NN启动(三)
HBase
HBased对接Hive
Linux
Nginx高可用
Python
数据导出工具
Flink
3分钟搭建Flink SQL测试环境
Kafka
Kafka对接Flume
深度学习
卷积神经网络
MySQL
数据备份恢复
计算机系统
信号量同步线程
Hive
Hive调优参数大全
其他框架
Azkaban Flow1.0与2.0
ClickHouse
表引擎-其他类型
技术成长
最好的职业建议
精选书单
技术成长书单—机器学习
技术资讯
数据在线:计算将成为公共服务
开发工具
IntelliJ IDEA 20年发展回顾(二)
系统工具
Mac命令行工具
虚拟化
内存虚拟化概述
云原生
云原生构建现代化应用
云服务
一文搞懂公有云、私有云...
Java
Spring Boot依赖注入与Runners
Go
Go函数与方法
SQL
SQL模板
安全常识
一文读懂SSO
当前位置:
首页
>>
数据结构与算法
>>
初级排序
初级排序
2020-07-04 18:18:50 星期六 阅读:1356
####如何分析一个排序算法 1、执行效率 - 最好最坏和平均时间复杂度 时间复杂度的系数、常数、低阶 比较次数和交换次数 2、内存消耗 3、稳定性(也就是经过排序算法后,值相同的两个元素先后顺序是否改变,如果不改变,则是稳定算法) ####冒泡排序 冒泡排序只会操作两个相邻的数据,每次冒泡操作都会对相邻的两个元素进行比较。看是否满足大小关系,如果不满足就让他俩互换。一次冒泡会让至少一个元素移动到它应该在的位置。重复n次,就完成了n个数据的排序工作。 ```python def bubble_sort(arr): for i in range(len(arr)): flag = False # 用来判断本次循环是否有交换操作 # 第1次(i = 1)比较就找出第一大的元素,第二次比较找出第二大,依次类推 for j in range(len(arr) - i -1):if arr[j] > arr[j + 1] : tmp = arr[j + 1] arr[j + 1] = arr[j] arr[j] = tmp flag = True if flag == False: # 如果没有交换,则说明已经排序完毕直接跳出循环 break return arr ``` #####算法性能分析 1、空间复杂度为O(1),所以是原地排序算法; 2、没有改变相同大小的数据顺序,所以是稳定排序算法; 3、时间复杂度最好为O(n),最坏为O(n^2),平均复杂度通过分析也是O(n^2),但实际上复杂度与需要排序的4数组的有序度是有关系的,如果整个数组是有序的,这种情况我们称为满有序度。比较次数 = 满有序度 - 有序度,有序度越高,时间复杂度越低。所以,平均复杂度用O(n ^ 2)来判断其实是比较不严格的。 ####插入排序 将需要排序的数组分为两个区间,即已排序区间和未排序区间,初始已排序区间只有一个元素,就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素,在已排序区间中找到合适的位置插入,并保证已排序区间数据一直有序,重复这个过程,直到未排序区间中元素为空,算法结束。 ``` def insert_sort(arr): for i in range(len(arr)): value = arr[i] for j in range(i - 1, -1, -1): # 从当前正在比较的最后一位开始比较 if value < arr[j]: tmp = arr[j] arr[j] = arr[j + 1] # 数据移动 arr[j + 1] = tmp else: break return arr ``` #####算法性能分析 原地排序算法 稳定的排序算法 最好的情况下是遍历一个已经有序的数组,时间复杂度为O(n),而最坏、以及平均的时间复杂度是O(n^2) ####选择排序 有点类似插入排序,区分已排序区间和未排序区间,但是选择排序每次会从未排序的区间中找到出最小的元素来将其放到已排序区间的末尾。 ``` def select_sort(arr): for i in range(len(arr)): min_value = arr[i] # 每次比较都把当前元素当做最小值,因为前面的元素不可能比当前的元素的值还大 for j in range(i, len(arr)): if min_value > arr[j]: tmp = min_value # 如果当前最小值大于下一个元素的值,则交换这两个值的位置 min_value = arr[j] # 对最小值重新赋值 arr[j] = tmp arr[i] = min_value # 把本轮比较的最小值插入数组的末尾 return arr ``` #####算法性能分析 - 原地排序算法,空间复杂度为O(1) 最好、最坏和平均时间复杂度都为O(n^2) 不稳定排序算法。因为每次排序都要选择最小的元素并且移动。这样就破坏了稳定性。 比如 5,8,5,2,9 这样一组数据,使用选择排序算法来排序的话,第一次找到最小元素 2,与第一个 5 交换位置,那第一个 5 和中间的 5 顺序就变了,所以就不稳定了。正是因此,相对于冒泡排序和插入排序,选择排序就稍微逊色了。 ####为什么插入排序比冒泡排序更受欢迎 虽然冒泡排序和插入排序在时间复杂度上是一样的,都是 O(n2),但是如果我们希望把性能优化做到极致,那肯定首选插入排序。因为`插入排序的算法思路有很大的优化空间`。冒泡排序的数据交换要比插入排序的数据移动要复杂。 下面是自己亲自实践的结果,需要排序的数据规模是:总共10000个数组,每个数组里放200个元素(1至1百万)之间的随机值)。 使用冒泡排序执行需要25.45秒,而使用插入排序只需要0.66秒。快的不止一个数量级。