时隔好几年，才发现算法的趣味性，比如堆排序。堆排序同时也是大学时自己未完成的数据结构作业之一，就像《高等数学》一样之后都是抄抄了事…… 个人理解，堆排序是一个有名的排序算法，比较适合优先级队列。虽然时间复杂度是O(nlogn)，论排序算法中比较快的还是快速排序。堆排序的特点是使用完全或近似完全二叉树来模拟一种父节点肯定比子节点大（最大堆）或者小（最小堆）的结果，并通过多次“删除”根节点并恢复结构来达到“模拟”排序的目的。实践中需要关注的是三点:

插入排序 插入排序最直观的解释是不断拿扑克牌时排序的动作。一开始你只有一张8，第二张是5，你把5放在8的左边。第三张是9，你放在8的右边。第四张是2，你放在最左边。拿这四张牌的过程可以认为是排序4个数字的过程。步骤可以归纳为： 拿起一张牌 -> 取下一个数 比较现有牌，具体来说是从右往左找到第一个不小于当前牌的位置 -> 将所有大于当前数的数字向右移动一位 放入牌 -> 放置数字 形象上来讲，放置数字的过程是多个数字右移的过程，所以不需要swap。Java代码如下： public void sort(int[] xs) { int len = xs.length; if (len <= 1) return; for (int i = 1; i < len; i++) { int x = xs[i]; int j = i; while (j > 0 && xs[j – 1] > x) {…

最近重新学习算法，先从几个排序算法开始。快速排序是比较有名的一个排序算法，基本原理我明白，但是之前只会筛选构造新序列分区的方式，现在要学的是原地分区的方式。 成果代码如下，使用Java编写（C/C++的数组和指针操作忘得差不多了）。 private void swap(int[] array, int i, int j) { if (i == j) return; System.out.println(String.format(“%d <-> %d”, i, j)); int a = array[i]; array[i] = array[j]; array[j] = a; } private int partition(int[] ns, int begin, int end) { int pivotIndex = (begin + end) / 2; int pivot = ns[pivotIndex]; swap(ns, pivotIndex,…