排序算法
2018-08-15 16:35:28 0 举报AI智能生成
面试常考排序算法总结
作者其他创作
大纲/内容
排序算法
冒泡排序
特点
stable sort、In-place sort
通过两两交换，像水中的泡泡一样，小的先冒出来，大的后冒出来。
复杂度
最优复杂度：O(n^2)（当然，也可以进行改进使得最佳运行时间为O(n)）
最差复杂度：O(n^2)
空间复杂度：O(1)
选择排序
unstable sort，In-place sort
把所有项扫描一趟，从中选择出最小的一项。将该项与最左端交换位置（0）。再次扫描（从1开始），还是寻找最小的，和1交换。这个过程一致持续到所有项都排定。
最优复杂度：O(n^2)
最坏复杂度：O(n^2)
插入排序
队伍中有一个被标记项x，其左侧都是（局部）有序，右侧未排序。让被标记项出列，向前与左侧一个个比较，若比被标记项大，向右移一位，直到遇到比被标记项小（或等于），插入被标记项。此时被标记项为x+1，重复之前过程，直到所有未排序项都插入到局部有序序列中合适的位置。
最优复杂度：O(n)，当输入数组就是排好序的时候，而快速排序在这种情况下会产生O(n^2)的复杂度。
最差复杂度：O(n^2)，当输入数组为倒序时
适合场景
比较适合用于“少量元素的数组”
希尔排序（Shell）
n-增量排序
适合场景：对于多大几千个数据项的中等大小规模数组排序表现良好。
归并排序
特点：stable sort、Out-place sort
最优复杂度：O(nlgn)
最差复杂度：O(nlgn)
快速排序
最优复杂度
O(nlgn)
最差复杂度
O(n^2)
当输入数组已排序
堆排序
思想
运用了最小堆、最大堆这个数据结构，而堆还能用于构建优先队列。
基数排序
手写排序算法
0 条评论
回复 删除
下一页
