简单实现
快速排序是比较经典、常用的算法,下面简要介绍其思路。对于一个数组,选取某个元素作为切分元素(比如第一个元素),然后把比这个元素小的都放到它前面,比这个元素大的都放到它后面,这样切分元素的最终位置就确定了,并且数组被划分为两个子数组。然后再用同样的方法分别对子数组进行排序,最终整个数组将变成有序的。
这里的关键是实现数组划分的方法,这里举例说明。假如要对数组a={5,3,6,5,8,4,7} 排序,选取a[0] 作为切分元素,排序过程如下:
5,3,6,5,8,4,7
i j
5,3,6,5,8,4,7
i j
5,3,4,5,8,6,7
ij
如上所示,刚开始i 指向数组第一个元素,而j 指向数组末尾元素后一个位置,i 从前往后扫描,直到找到一个大于等于切分元素时停下(这里是6 ),j 从后往前扫描,直到找到一个小于等于切分元素的时候停下(这里是4 ),然后交换这两个元素。然后继续寻找直到两个指针相遇,则本轮扫描结束。此时j<=i ,j 右边的元素均大于切分元素,交换a[j] 与切分元素即可。接着对两个子数组{5,3,4} 以及{8,6,7} 继续用刚才的方法排序,最终数组将全部有序。代码实现如下:
void sort(int[] a, int lo, int hi) {
if (hi <= lo)
return;
int j = partition(a, lo, hi);
sort(a, lo, j - 1);
sort(a, j + 1, hi);
}
int partition(int[] a, int lo, int hi) {
int i = lo, j = hi + 1;
int v = a[lo];
while (true) {
while (a[++i] < v)
if (i == hi)
break;
while (a[--j] > v)
if (j == lo)
break;
if (i >= j)
break;
swap(a, i, j);
}
swap(a, lo, j);
return j;
}
对于快速排序有几点说明:
优化
对于快速排序有3点优化思路:
-
对于小数组,可以采用插入排序,避免递归调用。例如,当if(hi <= lo + M) 时,就可以转到插入排序。
-
采用子数组的一部分元素的中位数来切分数组。这样做得到的切分更好,但代价是需要计算中位数。
-
如果数组中含有大量的重复元素,可以采用三向切分。将数组切分为三部分,分别对应于小于、等于和大于切分元素的数组元素。代码实现如下:
private static void sort1(int[] a, int lo, int hi) {
if (hi <= lo)
return;
int lt = lo, i = lo + 1, gt = hi;
int v = a[lo];
while (i <= gt) {
if (a[i] < v) {
swap(a, lt++, i++);
} else if (a[i] > v) {
swap(a, i, gt--);
} else {
i++;
}
sort(a, lo, lt - 1);
sort(a, gt + 1, hi);
}
}
另一种实现:单向扫描
快速排序的数组切分还有另一种单向扫描的版本,具体步骤是选择数组中最后一个元素作为切分元素,同样设置两个指针,指针i 指向数组中第一个元素前面一个位置,j 则指向数组中第一个元素。j 从前左右往右扫描,遇到小于等于切分元素时就把i 加一,然后交换i 和j 指向的元素。最后把i+1 位置的元素和切分元素交换即可完成一次数组划分。代码实现如下:
int partition(int[] a, int lo, int hi) {
int i = lo - 1, j = lo;
int v = a[hi];
while (j < hi) {
if (a[j] <= v) {
swap(a, ++i, j);
}
j++;
}
swap(a, i + 1, hi);
return i + 1;
}
(责任编辑:好模板) |