插入排序
基本思想
每一步将一个待排序的元素,按其排序码的大小,插入到前面已经排好序的一组元素的合适位置上去,直到元素全部插完为止
直接插入排序
代码实现
1 | //插入排序 |
下图只是演示到将16排序到前面的过程
直接插入排序的优化
1 | //插入排序 |
由于之前的序列都是有序的,这样的话就不用一个一个进行比较,只要先用二分查找找到插入的位置,这样的话本来需要搬运元素只需要搬运一次就行,很多元素不需要比较一次就搬运一次,这样会提高效率!
总结
元素集合越接近有序,直接插入排序算法的时间效率越高!
最优情况下:时间效率为$O(n)$
最差情况下:时间复杂度为$O(n^2)$
空间复杂度:$O(1)$,它是一种稳定的排序算法
希尔排序
又称缩小增量排序,是对直接插入排序的优化
很容易看出,经过这样的分组之后,许多比较大的数字都放在了后面,小数字都放在了前面,只要gap不断减小,分组不断变小,最后直到gap减到1的时候就和直接插入排序没什么区别了!
代码实现
1 | void ShellSort(int* arr,int len) |
总结
希尔排序是一种不稳定的排序,时间复杂度:$N^{1.25} 到 1.6N^{1.25}$
选择排序
基本思想
假设要排升序,每一趟选择一个最大的数字与最后的元素交换,这里所说的最后一个元素是会逐步向前调整的!
代码实现
1 | //选择排序 |
基本选择排序的优化
优化为每趟寻找最大值的同时找到最小值
1 | //选择排序的优化 |
只不过这种优化的方式需要注意一点(见下图),如果最小的元素恰好是最大的元素需要插入的位置,此时就需要将minPos设置为原来max的位置,因为最小值已经和maxPos位置的值交换了!
总结
时间复杂度:$n^2$
空间复杂度:$O(1)$
这是一种不稳定的排序
堆排序
堆排序有两个关键点
- 根据数组去建堆
- 交换首尾元素向下调整
代码实现
1 | void HeapAdjust(int *arr,int root,int len) |
总结
堆排序的时间复杂度:$N/2 *{log N}$其实就是$logN$
空间复杂度:$O(1)$
稳定性:不稳定
交换排序
冒泡排序
冒泡排序的思想非常简单,如下图,两两比较,每趟排序总可以把最大的放在最后面或者最小的值放在最后面,只需要进行(假设元素个数为n)n-1趟冒泡,便可以排序完成!
代码实现
1 | // 冒泡排序及其优化 |
总结
冒泡排序最好情况时间复杂度$O(n)$,冒泡排序最坏情况下时间复杂度 $O(1)$
冒泡排序空间复杂度$O(1)$
冒泡排序是一种稳定的排序算法
快速排序
基本思想
任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。
这样的话左边都是比基准值小的,在右边的都是比基准值大的,根据分治的思想,可以再把左边的序列选出一个基准值,在右边的序列也选择一个基准值,左边的排好了,右边的排好了,整个序列也就排好了!
代码实现_hoare版本
1 | //快速排序 |
前后指针法
这个方式其实不难理解,就是每次将key值移动到中间,在key左边的值都是比key小的值,key右边的值都是比key大的值,这样做分组的的话通过递归就可以完成排序!
1 | int PartSort3(int *array, int left, int right) |
- 本文作者: Tim
- 本文链接: https://zouchanglin.cn/2018/10/05/2732113479.html
- 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 许可协议。转载请注明出处!