归并排序

学习数据结构与算法
2021-05-17 14:29 · 阅读时长8分钟
小课

归并排序采用分治的思想,通过不断的将数组一分为二,直到不可再分,然后对已排序的子数组递归合并,最后使得整个数组有序,归并排序的最好、最坏以及平均时间复杂度都是O(NlogN)。

算法的主要思路是

  1. 选取数组中间位置,将数组分为两个子数组。
  2. 继续对两个子数组执行1~2步操作,直到子数组中只有一个元素。
  3. 递归合并有序的子数组。

下面是数组[6, 5, 12, 10, 9, 1]使用归并排序算法进行排序的过程。

加载中...

归并排序算法实现

加载中...

归并排序虽然在数组排序上效率低于快速排序,但是对链表进行排序时,归并排序通常是最佳选择,因为链表无法通过索引访问,如果使用快速排序效率会低很多,而归并排序对随机访问依赖较小,所以能够高效的完成链表的排序。

另外由于归并排序在排序过程中,左右子数组的排序并无依赖关系,所以可以并行提高效率。

下面是使用归并排序算法对链表进行排序的实现。

加载中...
归并排序排序算法