最近重新学习算法，先从几个排序算法开始。快速排序是比较有名的一个排序算法，基本原理我明白，但是之前只会筛选构造新序列分区的方式，现在要学的是原地分区的方式。
成果代码如下，使用Java编写（C/C++的数组和指针操作忘得差不多了）。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
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, end); int index = begin; for (int i = begin; i < end; i++) { if (ns[i] < pivot) { swap(ns, index++, i); } } swap(ns, index, end); return index; } private void sort(int[] ns, int begin, int end) { if (begin >= end) return; int index = partition(ns, begin, end); sort(ns, begin, index – 1); sort(ns, index + 1, end); } public void sort(int[] ns) { sort(ns, 0, ns.length – 1); } |
说明一下自己在学习原地分区核心算法时候的理解，也就是上面partition方法的逻辑。
众所周知，快速排序基于一个基准点pivot，这也就是前两行代码做的事情。
|
1 2 |
int pivotIndex = (begin + end) / 2; int pivot = ns[pivotIndex]; |
接下来就是正式的分区。分区的目地是把小于基准点的数筛选到基准点左边去，大于的到右边去（以升序序列为例）。
为此，设置一个小于基准点的数字的索引index，初始为开始位置begin。找到任何一个小于基准点的数之后都需要和这个索引位置的数字做交换，以便把小于基准点的数集中起来。
其次，在筛选之前，为了避免基准点对于分区的影响，把基准点放到最后去。
执行具体举例：
|
1 2 3 4 5 6 7 |
[1, 2, 4, 3, 5] [1, 2, 5, 3, 4] (4) <–> (5) 交换基准点和最后一个数字 [1, 2, 5, 3, 4] 1 0 <–> 0 小于基准点的数字索引0，原地交换，索引变成1 [1, 2, 5, 3, 4] 2 1 <–> 1 小于基准点的数字索引1，原地交换，索引变成2 [1, 2, 5, 3, 4] 5 遇到一个大于基准点的数字，索引不增加 [1, 2, 3, 5, 4] 3 2 <–> 3 小于基准点的数字索引2，与当前数字交换，索引变成3 [1, 2, 3, 4, 5] 3 <–> 4 筛选结束，交换小于基准点索引位置数字和基准点数字 |
对比代码
|
1 2 3 4 5 6 7 8 |
swap(ns, pivotIndex, end); int index = begin; for (int i = begin; i < end; i++) { if (ns[i] < pivot) { swap(ns, index++, i); } } swap(ns, index, end); |
个人认为，理解了这一快，理论上快速排序基本的东西就差不多了。