排序算法分析

我们都知道，在应届面试的时候，问到最多的就是快速排序，快速排序是最经典、最常用的排序算法，因为它的平均效率最优，也最稳定。

快速排序使用了分治的算法思想，分治算法本身理解起来很符合人类的思路（递归是很容易被理解的），其最关键的一步，就是划分了，算法导论上介绍了一种划分方法，和我在数据结构课上学的略有不同，昨晚，我把它们全都用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一个足够大的数组，然后对待排序数组遍历，将新数组键等于待排序数组中值的位置置为一（多个则继续增一），然后遍历新数组，即可得到待排序数组的顺序。这种算法不适合离散性数据，也不适合不知道范围的数据排序。

以上。

原标题：排序算法分析

关键词：排序