排序算法
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)
空间复杂度：O(1)
插入排序
特点
stable sort、In-place sort
队伍中有一个被标记项x，其左侧都是（局部）有序，右侧未排序。让被标记项出列，向前与左侧一个个比较，若比被标记项大，向右移一位，直到遇到比被标记项小（或等于），插入被标记项。此时被标记项为x+1，重复之前过程，直到所有未排序项都插入到局部有序序列中合适的位置。
复杂度
最优复杂度：O(n)，当输入数组就是排好序的时候，而快速排序在这种情况下会产生O(n^2)的复杂度。
最差复杂度：O(n^2)，当输入数组为倒序时
空间复杂度：O(1)
适合场景
比较适合用于“少量元素的数组”
希尔排序（Shell）
n-增量排序
先将要排序的一组记录按某个增量d（n/2,n为要排序数的个数）分成若干组子序列，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。继续不断缩小增量直至为1，最后使用直接插入排序完成排序。
适合场景：对于多大几千个数据项的中等大小规模数组排序表现良好。
归并排序
特点：stable sort、Out-place sort
复杂度
最优复杂度：O(nlgn)
最差复杂度：O(nlgn)
快速排序
复杂度
最优复杂度
O(nlgn)
最差复杂度
O(n^2)
当输入数组已排序
可以通过随机化来改进（shuffle array 或者 randomized select pivot）,使得期望运行时间为O(nlgn)
堆排序
复杂度
O(nlgn)
思想
运用了最小堆、最大堆这个数据结构，而堆还能用于构建优先队列。
基数排序
手写排序算法
0 条评论
下一页
