Java 快速排序两种实现

浏览数：37 / 时间：2015年06月08日

快速排序，只要学习过编程的人肯定都听说过这个名词，但是有时候写的时候还真蒙住了，网上搜罗了下以及查阅了"introduction to algorithm"，暂时找到两种实现快排的方式，记录如下：

1.通过挖坑，分治的方式，需要左右交替遍历

思想如下：

技术分享

代码实现：

 1     public static void quickSort1(int[] a, int s, int e) {
 2         if (s >= e)
 3             return;
 4         int m = a[s];
 5         int i = s, j = e;
 6         while (i < j) {
 7             while (a[j] > m && i < j)
 8                 j--;
 9             if (i < j)
10                 a[i++] = a[j];
11             while (a[i] < m && i < j)
12                 i++;
13             if (i < j)
14                 a[j--] = a[i];
15         }
16         a[i] = m;
17         quickSort1(a, s, i - 1);
18         quickSort1(a, i + 1, e);
19     }

2.将数组分为三个部分：小于中位数、大于中位数和未处理，是算法导论中提供的一种实现

思想如下：

技术分享

代码如下：

 1     public static void quickSort2(int[] a, int s, int e) {
 2         if (s >= e)
 3             return;
 4         int i = s - 1, j = s;
 5         int m = a[e];
 6         while (i <= j && i <= e && j <= e) {
 7             if (a[j] <= m) {
 8                 int tmp = a[++i];
 9                 a[i] = a[j];
10                 a[j++] = tmp;
11             }
12             else
13                 ++j;
14         }
15         quickSort2(a, s, i - 1);
16         quickSort2(a, i + 1, e);
17     }