Algorithm 版 (精华区)

发信人: Sun (大灯泡), 信区: Theory
标  题: 快速排序算法实现
发信站: 哈工大紫丁香 (2000年08月29日08:56:44 星期二), 站内信件

以下摘自《程序设计实践》
                                ——Sun

最好的排序算法之一是快速排序( q u i c k s o r t )，这个算法是1 9 6 0 年
由C. A. R. Hoare 发明的。

快速排序是尽量避免额外计算的一个极好例子，其工作方式就是在数组中划分出小
的和大的元素：
从数组中取出一个元素(基准值)。
把其他元素分为两组：
    “小的”是那些小于基准值的元素；
    “大的”是那些大于基准值的元素。
递归地对这两个组做排序。

当这个过程结束时，整个数组已经有序了。快速排序非常快，原因是：一旦知道了
某个元素比基准值小，它就不必再与那些大的元素进行比较了。同样，大的元素也
不必再与小的做比较。这个性质使快速排序远比简单排序算法(如插入排序和起泡
排序)快得多。因为在简单排序算法中，每个元素都需要与所有其他元素进行比较。
快速排序是一种实用而且高效的算法。人们对它做了深入研究，提出了许多变形。
在这里要展示的大概是其中最简单的一种实现，但它肯定不是最快的。
下面的q u i c k s o r t 函数做整数数组的排序：

/* quicksort: sort v[0]..v[n-1] into increasing order */
void quicksort(int v[], int n)
{
    int i, last;
    if (n <= 1)     /* nothing to do */
        return;
    swap(v, 0, rand() % n);     /* move pivot elem to v[0] */
    last = 0;
    for (i = 1; i< n; i++)      /* partition */
        if (v[i] < v[0])
            swap(v, ++last, i);
    swap(v, 0, last);           /* restore pivot */
    quicksort(v, last);         /* recursively sort */
    quicksort(v+last+1, n-last-1);  /* each part */
}

函数里的s w a p 操作交换两个元素的值。s w a p 在q u i c k s o r t 里出现三次，
所以最好定义为一个单独的函数：

/* swap: interchang v[i] and v[j] */
void swap(int v[], int i, int j)
{
    int temp;

    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
}


--
    太阳就是个大灯泡。
    那灯泡是什么呢？
    是光光！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: sunner.hit.edu.cn]