FunctionGHW

立志成为真正程序员的码农,伪全栈,目前主要写C#

堆排序(Heap Sort)算法学习

堆排序可以看作选择排序的进化版。选择排序通过遍历来选出最大(最小)元素, 堆排序利用数据结构二叉堆更快的选出最大(最小)元素。堆排序有两个优势: 1.)最好、最坏和平均时间复杂度均为\(O(nlogn)\); 2.)可以原地进行,空间复杂度\(O(1)\)。

继续阅读

归并排序(Merge Sort)是分治法的一个典型应用,相对于冒泡排序、插入排序和选择排序,其性能上有所提升,同时也是基于比较的排序算法中最好的算法之一。

归并排序的步骤如下:

  1. (Divide):将待排序序列(原问题)分成两个规模大致相等的子序列(子问题)
  2. (Conquer):递归地排序两个子序列,当子序列规模足够小的时候直接完成排序
  3. (Combine):合并两个已序的子序列得到原序列的排序结果
此算法中分解问题的过程类似于二分,关键步骤在合并。当分解出的子序列只有一个元素时,视为已序序列。

 

继续阅读