常见排序算法归档

简介

最近找到一个把排序算法归纳的很全的博客，故在这里记录一下。

链接如下 : 常见排序算法【归档】, 界面大概是下面这个样子的。

下面用文字简单介绍一些堆排序和快速排序，内容也是来自上面的网站的，方便快速回忆。

堆排序

堆排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。

在堆中定义以下几种操作：

• 最大堆调整（Max-Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点；
• 创建最大堆（Build-Max-Heap）：将堆所有数据重新排序，使其成为最大堆；
• 堆排序（Heap-Sort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算；

快速排序

快速排序用到分治法。

分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

利用分治法可将快速排序的分为三步：

• 在数据集之中，选择一个元素作为” 基准”（pivot）。
• 所有小于” 基准” 的元素，都移到” 基准” 的左边；所有大于” 基准” 的元素，都移到” 基准” 的右边。这个操作称为分区 (partition) 操作，分区操作结束后，基准元素所处的位置就是最终排序后它的位置。
• 对” 基准” 左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

总结