一、时间复杂度
1、时间复杂度为O(n*n)的排序
冒泡排序,选择排序、插入排序(常量系数较低)

2、时间复杂度为O(n*logn)的排序
归并、快速(只是因为系数较低)、堆、希尔

3、时间复杂度为O(n)的排序:
基数排序、计数排序

二、空间复杂度
1、空间复杂度为O(1)的排序:
冒泡排序,选择排序、插入排序、堆排序、希尔排序

2、空间复杂度为O(logN)~O(N)的排序:
快速排序(取决于划分的情况)
3、空间复杂度为O(N)的排序:
归并排序(可以有华为O(1),但空间复杂度会上升)
4、空间复杂度为O(M)的排序:
基数排序、计数排序(M则为桶的数量,计数排序中为数组中最大的数-最小的数+1,基数排序为10(0——9))

三、稳定性
  概念:假定待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,则这种排序算法是稳定的,否则不稳定。
 
 稳定的排序算法:
  冒泡排序,插入排序,归并排序、计数排序、计数排序、桶排序
 
 不稳定的排序算法:
  选择排序、快速排序、堆排序、希尔排序
  例如
  选择排序:
  假设有一个数组为2 2 2 1,经过一次交换,1换到第一个2的位置,2则换到最后,破坏了原来的顺序;
  堆排序:
  假设有一个数组为5 5 5,建立大根堆后,第一个元素就排到了第三个元素的后面
  快速排序:
  假设有一个数组为4 3 3 3 5,如果随机选中中间的3作为划分值,则左右两边的两个3将会被划分到它的左边或右边,破坏了稳定性
  希尔排序:
  假设有一个数组为5 1 1 5,如果第二个1条2步,与第一个5交换位置,则顺序就被改变了
 
 
 
 

技术
©2019-2020 Toolsou All rights reserved,
关于多租户系统的思考unity 获取小车速度及前进或者后退(精华)2020年7月21日 ASP.NET Core 全局过滤器的使用rk3399_android7.1调试USB蓝牙模块小结继承jpa Repository 写自定义方法查询git拉取远程分支并切换到该分支 艾伟也谈项目管理,基层管理杂谈uboot设置nfs参数——linux kernel使用nfs方式加载根文件系统rootfs(六)el-select获取选中项label值mysql 修改主键