[Collection与数据结构] 七大排序算法汇总

特性总结:

1. 元素越趋于有序,插入排序越快,因为遇到比较不符合条件的直接回break掉.
2. 时间复杂度:两层循环,O(n²)
3. 空间复杂度:只在数组本身上进行了操作,O(1)
4. 稳定性:稳定

其实我们观察上述代码,我们为什么说他是直接插入排序的升级版,是因为,它相比直接插入排序只是改变了每次走的步数.

特性总结:

1. 希尔排序是针对直接插入排序的优化
2. 当gap>1时都是预排序,目的是让数据越来越接近有序.当gap==1的时候,就是直接插入排序,这时数据已经趋于有序了,直接插入排序就会特别快.
3. 时间复杂度:目前仍然存在争议,一般认为是O(n^1.25~1.6n^1.25)
4. 稳定性:不稳定
5. 希尔排序其实就是把插入排序中的1变成了gap而已.

特性总结:

1. 时间复杂度:O(n²)
2. 空间复杂度:O(1)
3. 稳定性:不稳定
4. 这种排序方法虽然好理解,但是由于效率太低,日常开发中很少用.

特性总结:

1. 时间复杂度:O(n²)
2. 空间复杂度:O(1)
3. 稳定性:稳定

注意,在把根节点的元素和最后一个元素进行交换之后,向下调整的时候只需要调整根节点即可,因为除了被交换到堆底的那个元素之外,堆中只有根节点发生了改变,这里调整的道理和我们前面所学习的堆元素的删除道理是一样的.
特点总结:

1. 堆排序适用于海量数据排序,数据越多,堆排序效率越高.
2. 时间复杂度:复杂度主要集中于向下调整中,元素个数x树的高度,O(n*log₂n)
3. 空间复杂度:没有额外空间,O(1)
4. 稳定性:不稳定

之所以叫快速排序,说明它是真的快.快速排序整体思想为分治思想,就是把通过递归的思想把整个数组通过一定的方法切成二叉树的形式,之后对每科子树进行排序.
快速排序的方法有两种,一种是霍尔法,一种是挖坑法.

2.6.1 霍尔法

2.6.2 挖坑法

先把key(首)元素下标放入tmp中,让end向前移动,找到比tmp小的元素,填上key元素的坑,之后让start向后移动找到比tmp大的元素,填上上一个end的坑.以此类推,最后让tmp填上start和end相遇位置的坑.之后分治,递归重复上述操作.

2.6.3 数组分三块法

力扣OJ链接
与上面不同的是,我们这个算法分了三个区间,其中中间的区间全部是等于区间中一个元素的元素.右边是大于,左边是小于的.在分组之后,我们再向数组的右区间和左区间递归继续分组,直到数组有序-.

这里有一个需要注意的地方,我们在取比较基准元素的时候,需要随机选取,这样可以提高一些效率.

2.6.4 快速排序优化

• 由于快速排序越来越趋向有序,所以我们可以以分治之后数组的长度作为基准,当小于一定的值之后,就可以对分治区域使用插入排序.
• 为了防止出现二叉树单分支的情况而降低效率,所以我们需要在分治区间找到中间大小的元素,与首元素交换.

快速排序最终版: