快速排序和二分查找

发表于 分类于

排序算法中最快的是快速排序算法，搜索算法中最快的是二分搜索算法。我也最喜欢这2 个算法。 因为它们是使用递归实现的，代码简洁清晰，效率又非常高。

根据我的理解，算法的本质就是数学。根据输入和设定的目标，采用有限的步骤实现输出。 通常，使用计算机实现的算法，都会用到循环，这样才能发挥计算机高速运算的优势。

循环和递归是等效的，这已经被科学家所证明。数学上没有循环，只有递归的概念，因此使用递归代替循环表示算法有很多好处：

  1. 递归的代码要比循环简洁很多，也优雅很多。
  2. 递归的代码可以用数学方式建模，可以从数学角度验证其正确性。

很多函数式语言甚至没有循环的概念和关键字，强迫你使用递归来实现循环。如，ErLang 。 递归也有一些缺点，递归使用栈来保存函数地址和参数、返回值，而栈是有一定大小的， 过多的递归调用可能会造成栈溢出。但是，递归算法会容易转变为循环。我更欣赏递归的简洁， 除非真的出现栈溢出的问题，我是不会使用循环的。

二分搜索算法

算法描述

二分搜索算法用于针对已排序的集合进行搜索。

算法原理

  1. 找到排序数组的中间元素，如果它匹配目标值，那么就返回它在数组中的索引。
  2. 如果没有找到，那么判断中间值比目标值大还是小， 如果中间值比目标值大，那么就对第一个元素到middle-1 的元素递归这个过程。 如果中间值比目标值小，那么就对middle+1 到最后一个元素。
  3. 如果结束的索引小于开始的索引，返回-1 ，表示没有找到。
  4. 如果子集合有2 个元素，那么各自比较。因为Java 的整数除法会舍弃小数，如果数组只有2个元素， 那么middle 值一直都是第一个元素。

经过上述的递归过程，最终将返回匹配元素的索引，或者是-1 ，表示找不到。

二分搜索算法之所以速度快，是因为它每次可以把数组切分成两半，每次递归调用都能去除一半数据， 而不用匹配每一个数据。下面是代码，逻辑清楚，代码简单。

代码实现

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
/**
 * @param array
 * @param start
 * @param end
 *            这是最后一个元素的索引，第一次调用应该是array.length - 1
 * @param value
 * @return
 */
 
public static int binarySearch(int[] array, int start, int end, int value) {
    int middle = (start + end) / 2;
    if (end < start) {
        return -1;
    }
    if (end == (start + 1)) {
        if (array[start] == value) {
            return start;
        } else if (array[end] == value) {
            return end;
        }
    } else if (array[middle] == value) {
        return middle;
    } else if (value > array[middle]) {
        return binarySearch(array, middle + 1, end, value);
    } else if (value < array[middle]) {
        return binarySearch(array, start, middle - 1, value);
    }
    return -1;
}

上述代码稍加改变，就可以排序任意类型。如使用泛型，然后加上对Comparable 接口的实现即可。

快速排序算法

算法描述

二分搜索算法确实非常快，但是它只能用于已排序数组。如果数组未排序呢，该怎么办呢？ 简单，先用快速排序算法进行排序，然后再用二分搜索进行搜索。

先排序再搜索，要比匹配每一个元素快得多。搜索引擎，数据库索引也都使用了对数据集合的排序技术，这样搜索数据才会快速。

最慢，也是最容易想到的排序算法是插入排序算法：

  1. 遍历数组，找出最小的元素，把它放到第一个元素。
  2. 循环查找未排序的数组，直到整个数组排序。

这需要2 个嵌套的循环，意味着它的效率是O(n^2);

之所以插入排序的效率如此之地，是因为要找出整个数组中最小的数据，需要遍历整个数组的元素。

而插入排序聪明就聪明在它不查找整个数组最小、次小…的元素，而是每次仅仅把小于某个元素的值移到一边， 通过迭代最终自动实现排序。这就大大节约了排序所需的计算步骤。

快速排序算法理论

  1. 如果S中的元素个数是0或者1，那么返回。
  2. 选取S中的任一元素v，称为中心点。
  3. 将S集合中的元素分为2个部分：L={小于pivot的元素+pivot}和R={大于或者等于pivot的元素}
  4. 返回L和R

我们使用Java 使用的是就地排序的方式，因此不需要返回值。 因为Java 是一种可以修改变量的语言，用函数式语言的术语来说，就是有”副作用”。 我们利用这个副作用直接修改作为参数的Array ，不需要返回值

代码实现

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
30
31
32
33
34
35
36
37
38
/**
 * 快速排序，有副作用 从小到大
 *
 * @param array
 * @param start
 * @param end 这是最后一个元素的索引，第一次调用应该是array.length - 1
 */
 
public static void quickSort(int[] array, int start, int end) {
    // 有可能造成start>end 因为递归调用时j+1 ，可能引起j 比end 还大1 。 
            // 另外如果数组是空的，或者输入错误也会出现这种情况
    if (end <= start) {
        return;
    } else {
        // 取中间元素为中心点，然后移到最右边
        int sign = (start + end) / 2;
        int tmp = array[end];
        array[end] = array[sign];
        array[sign] = tmp;
        int j = start;
        for (int i = start; i <= end - 1; i++) {
            // 小于的元素和标记互换，等于的不能互换，否则会形成死循环
            if (array[i] < array[end]) {
                tmp = array[i];
                array[i] = array[j];
                array[j] = tmp;
                j = j + 1;
            }
        }
        // 把标记元素和第一个>= 它的元素位置互换
                    // 这样数组就分成2 个部分，一个部分比中心值小，一个部分比中心值大。
        tmp = array[j];
        array[j] = array[end];
        array[end] = tmp;
        quickSort(array, start, j);
        quickSort(array, j + 1, end);
    }
}

最后总结

  • Java 的Arrays 类也使用快速排序算法进行排序。但它的代码写得像天书一样。
  • 提高快速排序算法执行效率的主要方法是对中心点进行检测，希望选中的中心点有更大的概率是整个数组的中值。
  • 我的实现中简单的选择数组中间的值作为中心点，一般来说这样的选择效率还是不错的。
  • 注意上面的一项实现技术，我们使用把中心数据元素移到数组最后的方式实现了数组的就地比较。这是比较常用的技术， 把数据移到数组的最前面或者最后面，方便比较数据。
  • 另外，我的Java 快速排序代码使用了”副作用”，而在纯函数式语言，如Haskell,ErLang 中是没有”副作用”的， 也就是说变量不可以重新赋值。此时就需要返回值，每次都创建新的子数组。但函数式语言的数组处理功能很强， 也会做很多性能优化，因此函数式语言实现快速排序代码更加简单，没有”副作用”，也更加数学化。
  • JDK使用二分搜索和快速排序算法实现搜索和排序，足见上述两个算法的性能优势。