最近评论
正在载入评论列表...
6.3 泛型代码开发：快速排序
排序是一种对许多应用都很重要的算法。排序需要作用于多种不同的类型，也需要紧凑的编码和很高的效率。因此，排序函数是泛型编码的首选。下面的代码实现了快速排序算法。快速排序算法是由C. Anthony R. Hoare创建的一个高效的、著名的排序算法，最初发表于1962年的论文《Quicksort》(Computer Journal,vol.5,no.1)。在各种排序算法中，快速排序可能是应用最广泛的内排序（排序时所有数据全部都存储在主存中）算法。
首先为特定类型编写快速排序算法程序，然后我们会看到，将它转换为泛型代码是非常容易的一件事情。下面的代码实现了快速排序算法。
文件 quicksort.cpp
// Quicksort
inline void swap(int& x, int& y)
{
int t;
t = x;
x = y;
y = t;
}
inline void order(int& x, int& y)
{
if (x > y) swap(x, y);
}
bool find_pivot(int *left, int *right,int *pivot_ptr);
int* partition(int *left, int *right, int pivot);
void quicksort(int *left, int *right)
{
int *p, pivot;
if (find_pivot(left, right, &pivot)) {
p = partition(left, right, pivot);
quicksort(left, p - 1);
quicksort(p, right);
}
}
通常使用递归实现快速排序，采用的基本思想是分而治之（divide and conquer）。假设在main()函数中将a声明为一个长度为N的数组。在为数组赋值后，可以调用下面的函数进行排序：
quicksort(a, a + N - 1);
函数的第一个参数是指向数组首元素的指针，第二个参数是指向数组最后一个元素的指针。在quicksort()的函数定义中，很容易就能明白这些指针分别代表数组的左边界和右边界。如果可能的话，函数find_pivot()选择数组中的一个元素作为中心元素（pivot element），函数partition()重新排列数组中的各个元素，使得第一部分的所有元素的值都小于中心元素的值，剩余部分的所有元素的值都大于或者等于中心元素的值。另外，函数partition()返回一个指向数组元素的指针，该指针左边的元素值都小于中心元素的值，指针右边的元素的值以及指针指向的元素的值，都大于或等于中心元素的值。一旦数组以中心元素为基准进行了重新排列，就可以将函数quicksort()作用于每个子数组。
bool find_pivot(int *left, int *right, int *pivot_ptr)
{
int a, b, c, *p;
a = *left; // left value
b = *(left + (right - left) / 2); // middle value
c = *right; // right value
order(a, b);
order(a, c);
order(b, c); // order these 3 values
if (a < b) { // pivot is higher of 2 values
*pivot_ptr = b;
return true;
}
if (b < c) {
*pivot_ptr = c;
return true;
}
for (p = left + 1; p <= right; ++p)
if (*p != *left) {
*pivot_ptr = (*p < *left) ? *left : *p;
return true;
}
return false; // all elements have same value
}
理想状态下，中心元素的选择应该使得每一步都能将数组分割成两部分，每一部分都有相同（或者近似相同）的元素数目。这将使函数quicksort()处理任务的总量达到最小值。因为预先不知道这个中心值是多少，所以要试图从数组的首元素，中间元素和最末元素中选出能够作为中心元素的中间值。为了进一步进行划分，要求至少有一个元素小于中心元素值。如果所有元素的值相同，则中心元素不存在，函数返回false。
int *partition(int *left, int *right, int pivot)
{
while (left <= right) {
while (*left < pivot)
++left;
while (*right >= pivot)
--right;
if (left < right) {
swap(*left, *right);
++left;
--right;
}
}
return left;
}
函数partition()完成了主要工作。这里详细解释一下该函数是如何工作的。假设有一个包含12个元素的数组a[]：
7 4 3 5 2 5 8 2 1 9 -6 -3
调用函数find_pivot()时，首先比较数组的首元素、中间元素和最末元素。中间元素5比这三个值中最小的值大，因此将这个值选为中心元素值。下面的仿真过程显示了函数partition()中的外部while循环每一次运行后的数组元素值。每次循环中被交换的元素由下划线标识。
未排序的数据 7 4 3 5 2 5 8 2 1 9 -6 -3
第一次循环后 -3 4 3 5 2 5 8 2 1 9 -6 7
第二次循环后 -3 4 3 -6 2 5 8 2 1 9 5 7
第三次循环后 -3 4 3 -6 2 1 8 2 5 9 5 7
第四次循环后 -3 4 3 -6 2 1 2 8 5 9 5 7
注意，在第四次循环后，下标为0~6的元素的值都已经小于中心元素的值，而剩下的元素的值都大于或者等于中心元素的值。因此在第四次循环结束后，partition()返回元素a[7]的地址，并结束运行。
将quicksort()转换为泛型函数
现在将快速排序算法转换成能够作用于泛型数据的通用算法，这里的关键是要识别出需要泛化的所有类型。最初的算法作用于int型数据，下面将一步步将其改变为作用于类型T。
文件 genericQuicksort.cpp
template <class T>
inline void swap(T& x, T& y)
{
T t;
t = x;
x = y;
y = t;
}
template <class T>
inline void order(T& x, T& y)
{
if (x > y) swap(x, y);
}
swap()函数与order()函数解析
■ template <class T>
inline void order(T& x, T& y)
编写模板的关键是要在模板代码开始处使用template，以及适当数量的类型标识符，通常使用标识符T1、T2等。正常情况下，在只有一种参数化类型时通常使用class T。函数通常使用T作为它的签名的一部分。稍后，在使用给定类型调用order()时（例如在order(x,y)中给定类型为double类型），编译器产生专门处理这个类型的代码。这里的一个不利方面是，对每一个不同类型使用order()函数时都会产生一个函数体。泛型编码能够使用void*避免产生多个函数体，也即避免代码膨胀（code bloat）。
■ {
if (x > y) swap(x, y);
}
这段代码与int类型的代码没有什么区别。如果特殊类型T没有定义运算符>，编译器会给出语法错误。
■ template <class T>
inline void swap(T& x, T& y)
{
T t;
这里，函数签名和块内变量都使用了类型T。
■ t = x;
x = y;
y = t;
}
这段代码应该能够正常工作，因为在所有类型中都定义了operator=。但是，用户需要检查operator=的语义是不是深复制语义，也就是说，要复制数据，而不是只复制指向数据的指针。
一旦理解了算法和它的泛型编码模式，很容易就能够找到特定的类型。这个例子中的特定类型是int类型，因此应该对它进行参数化并将其修改为一个参数化类型T。下面我们不再做任何说明，只是简单地给出剩余的代码。
// Forward declarations of auxiliary functions
template <class T>
bool find_pivot(T *left, T *right, T *pivot_ptr);
template <class T>
T* partition(T *left, T *right, T pivot);
template <class T>
void quicksort(T *left, T *right)
{
T *p, pivot;
if (find_pivot(left, right, &pivot)) {
p = partition(left, right, pivot);
quicksort(left, p - 1);
quicksort(p, right);
}
}
template <class T>
T *partition(T *left, T *right, T pivot)
{
while (left <= right) {
while (*left < pivot)
++left;
while (*right >= pivot)
--right;
if (left < right) {
swap(*left, *right);
++left;
--right;
}
}
return left;
}
template <class T>
bool find_pivot(T *left, T *right, T *pivot_ptr)
{
T a, b, c, *p;
a = *left; // left value
b = *(left + (right - left) / 2); // middle value
c = *right; // right value
order(a, b);
order(a, c);
order(b, c); // order these 3 values
if (a < b) { // pivot is higher of 2 values
*pivot_ptr = b;
return true;
}
if (b < c) {
*pivot_ptr = c;
return true;
}
for (p = left + 1; p <= right; ++p)
if (*p != *left) {
*pivot_ptr = (*p < *left) ? *left : *p;
return true;
}
return false; // all elements have same value
}
下面使用两种不同类型的数组测试这段代码。
文件 genericQuicksort.cpp
int main()
{
cout << "quicksort\n";
int a[12]={7, 4, 3, 5, 2, 5, 8, 2, 1, 9, -6, -3 };
for (int i = 0; i < 12; i++)
cout << a[i] << " , ";
quicksort(a, a + 11);
cout << "\n\nquicksorted\n";
for (int i = 0; i < 12; i++)
cout << a[i] << " , ";
cout << endl;
// Now use doubles
double b[6] = { 7.8, 4.9, 3.8, 5.0, 2.8, 5.3 };
for (int i = 0; i < 6; i++)
cout << b[i] << " , ";
quicksort(b, b + 5);
cout << "\n\nquicksorted\n";
for (int i = 0; i < 6; i++)
cout << b[i] << " , ";
cout << endl;
}
标准C语言库提供了qsort()函数，它是一个使用void*的快速排序泛型例程。在Al Kelley和Ira Pohl著的C by Dissection（第4版）一书中，对这种技术进行了展开讨论。
图书导读
