选择排序
- 空间复杂度O1
- 方法 指定待排序数组首项为最小值,依次向后比较直到最后一位找出最小值并与首项进行交换
冒泡排序
- 每一轮从前往后依次比较两个元素的大小,如果不满足所需顺序,就把他们交换位置
- 这样每一轮中最大的数字一定会下沉到末尾,在下一轮扫描时就可以舍去末尾的数字
插入排序
- 从数组的首端开始,每次向后取一个数,从它的位置向前开始依次比较并交换,直到它大于等于它前面的数为止
归并排序
- 分治法
- 将数组拆分成两侧,使两侧各自有序后,从两个数组中依次取 较小的数放进新的数组中,取完之后拷贝回原数组
- 空间换时间 - 时间复杂度 O(n log n) 额外空间复杂度 O(n)
快速排序
- 使用双指针方法 每次取数组最后一个数,按照这个数将数组划分为三个部分(小于这个数,等于这个数,大于这个数)
- 然后将这个数与大于区的第一个数进行交换
- 然后中间的部分不动,左右两边的数组递归进行排序
堆排序
- 原理 : 大根堆小根堆]
- 1.建堆 : heapsize不断自增相当于heapinsert
- 2.排序 : 把堆上第一个数字与最后一个数字交换,然后heapsize–,恢复堆的状态,当堆的大小为0时排序完成
- (↑相当于每次取出一个最大值,故而必然有序)
- 大根堆升序小根堆降序
- 唯一一个空间复杂度O(1)且时间复杂度O(NlogN)的算法
计数排序
基数排序
- 现根据个位数字将数组分到桶里,然后把数据依次倒出来(放回原数组)
- 然后再根据第二位数字分到桶里,以此类推,一直到最后一位数字
- 后排序的优先级高,所以从个位数开始排
所有基于桶的排序都可以实现稳定性
插入排序,冒泡排序,归并排序可以实现稳定性
选择排序,快速排序,堆排序不稳定
| 时间复杂度 | 空间复杂度 | 稳定性 | |
|---|---|---|---|
| 选择 | N2 | 1 | x |
| 冒泡 | N2 | 1 | √ |
| 插入 | N2 | 1 | √ |
| 归并 | NlogN | N | √ |
| 快排 | NlogN | logN | x |
| 堆 | NlogN | 1 | x |
经过实验之后快排是最快的
需要稳定性时用归并
需要节约空间时用堆
