1. 什么是排序?
排序是把无序的数据整理为有序的数据.
2. 排序种类划分?
根据排序中, 数据的移动方式划分为: 直接移动和逻辑移动两种.
根据排序排序中所使用的存储器划分为: 内部排序和外部排序.
内部排序就是数据操作只需要借助内存来完成.
外部排序就是需要借助外部存储设备, 如硬盘, u 盘, 软盘等等. 适用于数据量庞大的场景.
3. 排序算法优劣划分依据?
(1) 是否稳定. 也就是考虑在存在数据相等时, 排序后是否会引起相等数据位置的不确定. 可以确定相对位置的就是稳定排序. 反之, 就是不稳定排序.
(2) 时间复杂度. 用于衡量程序运行时间的函数.
(3) 空间复杂度. 用于衡量排序所用空间的函数.
4. 常用的内部排序算法有哪些?
(1) 冒泡排序.
冒泡排序如同气泡, 自下而上浮出水面.
原理: 将每一个元素和其他元素相比较, 如果这个元素小于其他元素, 就进行调换位置. 因此需要 (n-1)+(n-2)+...+(n-(n-1))=1+2+3+...+(n-1)=(n-1)n/2
因此时间复杂度为 O(n^2), 并且是稳定排序. 排序过程只需要一个额外的空间.
另外, 冒泡排序在其中一个元素没有发生交换位置时, 就已经是一个有序的数据. 循环可以提前结束. 是一个优化的方案.
(2) 选择排序
选择排序是遍历数据将每个最小的元素变换位置, 而达到最终的有序. 有点儿类似于冒泡排序, 但是选择排序不会进行频繁的位置交换, 只会从第一个元素开始, 查找最小的元素, 次小的等等, 最多只会有 n-1 次交换位置.
从执行次数来讲和冒泡排序一样. 时间复杂度也是 O(n^2).
注意: 选择排序不是稳定排序. 因为如果有和位置 0 相等的其他元素, 交换为之后, 相对顺序会发生改变, 因此不是稳定的.
空间上只需要 1 个额外空间.
(3) 插入排序
就是依次取一个元素, 直至取完, 将每一个元素插入, 直至最后一个元素.
需要的执行次数为: 1+2+...+(n-1)= n(n-1)/2, 时间复杂度为 O(n^2), 并且是稳定排序, 需要空间为一个额外的空间.
会进行大量的数据移动, 建议在链表上使用.
(4) 希尔排序
排序原理: 分组拆 (注意: 相反的可以分组合, 另一种排序算法)
就是先分成几个区块, 再减小间距, 直至间距为 1, 进行最后依次排序, 完成!!!
时间复杂度为 O(n^3/2), 稳定排序, 只需要一个额外的空间.
(5) 合并排序
由小集合到大集合的过程, 就相当于是分多个队伍, 各自排好自己的顺序, 再合到一起.
时间复杂度为 O(n*logn), 稳定排序, 需要一个与文件大小相同的空间.
(6) 快速排序法
又叫做分割交换排序法, 是目前公认最佳的排序法.
原理: 固定一个基准点, 确定一个基准点, 使左边的数据都小于右边的数据, 各自再进行排序.
时间复杂度为 O(nlog2N), 不是稳定排序法, 因为会进行位置交换. 空间复杂度最差为 O(n)
, 最佳情况为 O(log2N)
(7) 堆积排序法
运用二叉树的技巧, 树根大于等于左右子树, 将数据转换为堆积树. 然后依次从最大的树根处移除数据.
时间复杂度为 O(nlogN), 不是稳定排序, 需要一个额外的存储空间.
来源: http://www.bubuko.com/infodetail-3302884.html