深入浅出排序算法(3)-快速排序

发表于 | 分类于 ， | | 阅读次数

概述

快速排序与归并排序一样也是基于分治算法的排序算法.所以它的实现方法也与其他的分治算法一样,需要进行分解子任务,处理子任务,归并子任务这些步骤.

但快速排序与归并排序不同,它是一种原地排序算法(不需要额外的辅助数组),且快速排序不使用中间值来分解任务,而是使用划分函数.

算法过程

  • 从数组中挑选出一个值,作为基准值 k.
  • 重新排序序列,将所有小于k的值放到k前面,所有大于k的值放到k后面(也可以理解为将数组a切分为两个子数组a[begin...k-1],a[k+1...end],其中前一个子数组都小于k,后一个子数组都大于k).
  • 递归地将两个子数组进行快速排序(递归到最底部时,子数组的大小是零或一,也就是已经排序好了.).

划分函数

划分函数就是上述步骤中的第二步,它将数组根据基准值进行重排序.根据基准值选择的位置不同,划分函数也有不同的实现方法,不过其根本思想都是将小于基准值的值放到前面,大于基准值的值放到后面.

使用末尾元素作为基准值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 使用末尾元素作为基准值来进行切分
private static int partitionUseEnd(Comparable[] a, int begin, int end) {
    Comparable pivot = a[end]; // 基准值,切分后的数组应满足左边都小于基准,右边都大于基准
    int i = begin - 1;
    for (int j = begin; j < end; j++) {
        // 如果j小于基准值则与i交换
        if (less(a[j], pivot)) {
            i++;
            swap(a, i, j);
        }
    }
    // 将基准值交换到正确的位置上
    int pivotLocation = i + 1;
    swap(a, pivotLocation, end);
    return pivotLocation;
}

使用首元素作为基准值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 使用首元素作为基准值来进行切分
private static int partitionUseBegin(Comparable[] a, int begin, int end) {
    Comparable pivot = a[begin];
    int i = begin;
    int j = end + 1;
    while (true) {
        // 从左向右扫描,直到找出一个大于等于基准的值
        while (less(a[++i], pivot)) {
            if (i >= end)
                break;
        }
        // 从右向左扫描,直到找出一个小于等于基准的值
        while (less(pivot, a[--j])) {
            if (j <= begin)
                break;
        }
        // 如果指针i与j发生碰撞则结束循环
        if (i >= j)
            break;
        // 将左边大于小于基准的值与右边小于等于基准的值进行交换
        swap(a, i, j);
    }
    // 将基准值交换到正确的位置上
    swap(a, begin, j);
    return j;
}

代码实现

了解了划分函数的实现,剩下就只需要递归地调用快速排序不断地分解子任务即可.

注意,快速排序与归并排序不同,它不需要进行归并(划分后就已经是有序的了),并且是先进行划分函数,再分解任务.

1
2
3
4
5
6
7
8
9
10
11
12
public static void sort(Comparable[] a) {
    sort(a, 0, a.length - 1);
}
private static void sort(Comparable[] a, int begin, int end) {
    if (begin >= end)
        return;
    int k = partitionUseEnd(a, begin, end);
    sort(a, begin, k - 1);
    sort(a, k + 1, end);
}

本文作者为SylvanasSun(sylvanassun_xtz@163.com),转载请务必指明原文链接.

分享