我们都知道，在应届面试的时候，问到最多的就是快速排序，快速排序是最经典、最常用的排序算法，因为它的平均效率最优，也最稳定。
快速排序使用了分治的算法思想，分治算法本身理解起来很符合人类的思路（递归是很容易被理解的），其最关键的一步，就是划分了，算法导论上介绍了一种划分方法，和我在数据结构课上学的略有不同，昨晚，我把它们全都用java实现了。
这个是算法导论的版本：
1 /** 2 * 快速排序的划分方法一：算法导论版本 sit的下一个比最后一个大 3 * 4 * @param begin 5 * @param end 6 * @return 7 */ 8 private int QuickMergeA(int begin, int end) { 9 System.out.print("初始：" + arr); 10 System.out.print(begin + " " + end); 11 int anchor = (int) arr.get(end); 12 int sit = begin - 1; 13 int temp; 14 for (int i = begin; i < end; i++) { 15 if ((int) arr.get(i) <= anchor) { 16 sit++; 17 temp = (int) arr.get(i); 18 arr.set(i, (int) arr.get(sit)); 19 arr.set(sit, temp); 20 } 21 } 22 temp = (int) arr.get(sit + 1); 23 arr.set(sit + 1, anchor); 24 arr.set(end, temp); 25 System.out.print(arr); 26 System.out.println(sit + 1); 27 return sit + 1; 28 }
不难看出，这个版本的划分思路是，从数组一端往另一端推进，对于比指定元素小的值，均放在左侧，比指定元素大的值，放在右侧。
然后我们再看我数据结构课本上学过的版本：
/** * 快速排序的划分方法二：数据结构课本版本 * * @param begin * @param end * @return */ private int QuickMergeB(int begin, int end) { System.out.print("初始：" + arr); System.out.print(begin + " " + end); int anchor = arr.get(end); int send = end - 1; int temp; int tbegin = begin; while (begin <= send) { while (arr.get(begin) <= anchor && begin <= end - 1) { begin++; } while (send >= tbegin && arr.get(send) > anchor) { send--; } if (begin < send) { temp = arr.get(begin); arr.set(begin, arr.get(send)); arr.set(send, temp); } if (begin >= send) { temp = arr.get(begin); arr.set(begin, arr.get(end)); arr.set(end, temp); } } System.out.print(arr); System.out.println(send + 1); return send + 1; }
可以看出，这种思路是两端推进的手段，两端同时推进，同样是左边存放比指定元素小的值，右边存放比指定元素大的值。
这两种方法遍历数组的推进方法虽然不同，但是其效率是一致的，划分一次都相当于是要遍历一次子数组。其划分的包装入口也是相似的：
/** * 快速排序入口 * * @param begin * @param end */ private void QuickSequence(int begin, int end) { // if (begin < end) { // int q = QuickMergeA(begin, end); // this.QuickSequence(begin, q - 1); // this.QuickSequence(q + 1, end); // } if (begin < end) { int q = QuickMergeB(begin, end); this.QuickSequence(begin, q - 1); this.QuickSequence(q + 1, end); } }
需要指明的是，测试上面方法的过程中，应该把arr数组设置为静态的，在java中，实现类似于C++的地址访问的情况，我经常使用静态变量。
最古老的排序算法是插入排序，之前学习数据结构的时候，对于各种排序算法总是混淆，比如对于快速排序和插入排序的算法思路都明白，但是总是把快速排序当成插入排序，插入排序当成快速排序。也许是当时两节课学了冒泡排序、快速排序、插入排序、堆排序等太多的排序算法吧，加上编程经验少造成的。
其实插入排序很容易和快速排序区分开。因为插入排序是真的“插入”。插入排序的基础是左侧数据已经排序准确，你要做的是把下一个数插入到有序数组的指定位置，你可以脑补扑克牌。
/** * 插入排序 */ private void InsertSequence() { for (int i = 0; i < arr.size(); i++) { int p = 0; while (p < i && arr.get(p) < arr.get(i)) { p++; } if (p < i) { int temp = arr.get(i); for (int k = i; k > p; k--) { arr.set(k, arr.get(k - 1)); } arr.set(p, temp); } } }
插入排序的代码很短，但是我们的经验是，短的代码代表思路简单，不代表效率高。其实是这样的，插入排序的效率是N^2,而快速排序的效率则是NlogN。插入排序是最朴素的排序算法，也是相对较慢的排序算法。
学数据结构的课程时，我非常喜欢堆排序。或许是因为它是最形象的排序算法。其实，堆排序利用特有的数据结构，高效的做了这么一件事，每次找出最小的数，然后从数组中删掉这个数，继续查找。
1 private void MaintainHeap(int length) { 2 int temp; 3 for (int i = length / 2 - 1; i >= 0; i--) { 4 if ((arr.get(i) < arr.get((i + 1) * 2 - 1)) 5 || ((i + 1) * 2 < length && arr.get(i) < arr 6 .get((i + 1) * 2))) { 7 if ((i + 1) * 2 < length) { 8 if (arr.get((i + 1) * 2) < arr.get((i + 1) * 2 - 1)) { 9 temp = arr.get(i); 10 arr.set(i, arr.get((i + 1) * 2 - 1)); 11 arr.set((i + 1) * 2 - 1, temp); 12 } else { 13 temp = arr.get(i); 14 arr.set(i, arr.get((i + 1) * 2)); 15 arr.set((i + 1) * 2, temp); 16 } 17 18 } else { 19 temp = arr.get(i); 20 arr.set(i, arr.get((i + 1) * 2 - 1)); 21 arr.set((i + 1) * 2 - 1, temp); 22 } 23 24 } 25 } 26 27 System.out.println(arr); 28 } 29 30 private void Heapsequence(int length) { 31 for (int i = length; i > 0; i--) { 32 this.MaintainHeap(i); 33 int temp = arr.get(0); 34 arr.set(0,arr.get(i - 1)); 35 arr.set(i - 1, temp); 36 } 37 }
堆排序的重要步骤是堆的维护。对于最大堆而言，要确保特定个元素构建的堆中，每个节点的值都大于其孩子节点，这通常的方法是，从最后一个有子节点的节点开始，遍历到根节点，对于这其间的每一个结点，如果其子节点存在大于当前节点的节点，则把最大的子节点同当前节点交换，并同时维护交换后的子节点的状态（这个子节点的子节点可能在交换后比子节点的值大）。
除了上面的排序算法，我们常见的还有冒泡排序之类。同时，我在算法导论上，还接触过计数排序、基数排序、桶排序等线性排序算法。因为其思路比较简单，所以这里只给出一般思路：
计数排序顾名思义，使用了一个计数数组，对于每一个值，初始计数为0，每新增一个，该计数就增加一，最后形成一个排序序列。计数排序的效率一般，但是由于其稳定，常常作为其它排序算法基本过程的算法使用。
基数排序是另外一种比较有意思的排序算法，它先从最低位对数据进行排序，然后再依次上升到最高位，而对每个数位的排序，他通常使用计数排序。
桶排序是效率最高的排序算法，但是它对数据要求较高，同时是一种以空间换时间的排序算法。它的方案是先new一个足够大的数组，然后对待排序数组遍历，将新数组键等于待排序数组中值的位置置为一（多个则继续增一），然后遍历新数组，即可得到待排序数组的顺序。这种算法不适合离散性数据，也不适合不知道范围的数据排序。
对于常规排序算法，冒泡排序适合只有少数数据不在正确位置上的数据，快速排序的平均效率最高，堆排序性能极不稳定，插入排序的效率较差。
以上。