常见排序算法总结

冒泡排序

每次从左到右两两比较,把大的交换到后面,每次可以确保将前M个元素的最大值移动到最右边。

插入排序

插入排序的原理是从左到右,把选出的一个数和前面的数进行比较,找到最适合它的位置放入,使前面部分有序。

选择排序

选择排序的原理是,每次都从乱序数组中找到最大(最小)值,放到当前乱序数组头部,最终使数组有序。

希尔排序

将数组列在一个表中并对列分别进行插入排序,重复这过程,不过每次用更长的列(步长更长了,列数更少了)来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法,算法本身还是使用数组进行排序。

归并排序

分治思想,归并排序的思想就是先递归分解数组,再合并数组。
先考虑合并两个有序数组,基本思路是比较两个数组的最前面的数,谁小就先取谁,取了后相应的指针就往后移一位。然后再比较,直至一个数组为空,最后把另一个数组的剩余部分复制过来即可。
再考虑递归分解,基本思路是将数组分解成left和right,如果这两个数组内部数据是有序的,那么就可以用上面合并数组的方法将这两个数组合并排序。如何让这两个数组内部是有序的?可以再二分,直至分解出的小组只含有一个元素时为止,此时认为该小组内部已有序。然后合并排序相邻二个小组即可。

堆排序

  • 构造最大堆(Build Max Heap):首先将当前元素放入最大堆下一个位置,然后将此元素依次和它的父节点比较,如果大于父节点就和父节点交换,直到比较到根节点。重复执行到最后一个元素。
  • 最大堆调整(Max Heapify):调整最大堆即将根节点移除后重新整理堆。整理方法为将根节点和最后一个节点交换,然后把堆看做n-1长度,将当前根节点逐步移动到其应该在的位置。
  • 堆排序(HeapSort):重复执行2,直到所有根节点都已移除。

快速排序

分治法思想,选择一个基准数,把比这个数小的挪到左边,把比这个数大的移到右边。然后不断对左右两部分也执行相同步骤,直到整个数组有序。

总结

排序方法 平均时间 最好情况 最坏情况 辅助空间 稳定性
冒泡排序 O(n2) O(n2) O(n2) O(1) 稳定
插入排序 O(n2) O(n) O(n2) O(1) 稳定
选择排序 O(n2) O(n2) O(n2) O(1) 不稳定
希尔排序 O(nlog(n))~O(n2) O(n1.3) O(n2) O(1) 不稳定
归并排序 O(nlog(n)) O(nlog(n)) O(nlog(n)) O(n) 稳定
堆排序 O(nlog(n)) O(nlog(n)) O(nlog(n)) O(1) 不稳定
快速排序 O(nlog(n)) O(nlog(n)) O(n2) O(log(n))-O(n) 不稳定
打赏

发表评论

电子邮件地址不会被公开。 必填项已用*标注