你的位置:首页 > Java教程

[Java教程]排序算法分析


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

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

 

以上。