排序是计算机执行的最常见的功能之一，而快速排序是执行此操作的最有效方法之一。本文演示了图形调试器在学习快速排序工作原理方面的实用性。

DDD（数据显示调试器）是一个免费的可视化前端，可以控制许多流行的调试器。本文使用 DDD 来完成一个简单的 C 语言快速排序实现。

首先，找到 DDD 的副本并安装它。RPM 软件包可在 rpmfind.net 上找到，Debian 软件包可在 debian.org 上找到。本文是使用 Red Hat 7.3 上的 DDD 3.3.1 版本编写的。本文还做出以下假设：1) 您拥有一台增强型 GNU/Linux 计算机并已插入电源；2) 您了解基本的 C 语言概念，包括数组、循环和递归；3) 您有一个功能强大的 C 编译器，例如 GNU 的 GCC。即使您对编程一无所知，也请尝试单步执行代码。这对您有好处。

CAR Hoare 在一篇广为引用的 1962 年论文中描述了快速排序算法，并且它在 40 年后的今天仍然被广泛使用。快速排序的分而治之方法可能是它获得“快速”前缀的原因；通过将较小元素与较大元素分离，它消除了许多比较的需要。相比之下，选择排序将每个元素与每个其他元素进行比较。这并不是说快速排序总是更快或它是排序的最佳方法；只是了解它很酷。本文中的实现不是经过优化的或可扩展的快速排序。它仅适用于整数数组。

此代码主要借用自 Brian W. Kernighan 和 Rob Pike 的 编程实践

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* from: The Practice of Programming (pp: 32-34)
 *   by: Brian W. Kernighan and Rob Pike
 */
/* swap: interchange v[i] and v[j] */
void swap( int v[], int i, int j )
{
  int tmp;
  tmp = v[i];
  v[i] = v[j];
  v[j] = tmp;
}
/* quicksort: sort v[0]..v[n-1] into increasing
 * order
 */
void quicksort( int v[], int n )
{
  int i = 0, last = 0;
  if ( n <= 1 )              /* nothing to do */
    return;
  swap( v, 0, rand() % n );  /* move pivot elem
                                to v[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 );      /* sort smaller
                                values */
  quicksort( v+last+1, n-last-1 );  /* sort larger
                                       values */
}
void print_array( const int array[], int elems )
{
  int i;
  printf("{ ");
  for ( i = 0; i < elems; i++ )
    printf( "%d ", array[i] );
  printf("}\n");
}
#define NUM 9
int main( void )
{
  int arr[NUM] = { 6, 12, 4, 18, 3,
                  27, 16, 15, 19 };
  /* commented out to aid in predictability
   * srand( (unsigned int) time(NULL) ); */
  print_array(arr, NUM);
  quicksort(arr, NUM);
  print_array(arr, NUM);
  return EXIT_SUCCESS;
}

将代码保存到名为 easy_qsort.c 的文件中。接下来，编译代码

$ gcc -Wall -pedantic -ansi -o qsortof -g \
easy_qsort.c

GCC 最重要的参数是 -g，它将调试符号添加到代码中。

尝试运行程序以确保一切正常

$ ./qsortof
{ 6 12 4 18 3 27 16 15 19 }
{ 3 4 6 12 15 16 18 19 27 }

第一行输出是未排序的数组，第二行是运行快速排序函数后的数组。

那么它是如何工作的呢？让我们转向我们的新朋友 DDD

$ ddd qsortof

这将启动 DDD。关闭任何弹出的提示和关于：帮助窗口，您应该看到类似于图 1 的内容。

图 1. 刚启动的 DDD

现在打开行号显示是一个好主意。单击编辑-->首选项-->源代码菜单中“显示源代码行号”旁边的复选框。现在我们可以添加断点并开始调试了。

首先，通过单击边距中的行号来选择“nothing to do”行。然后，单击“在 () 处设置/删除断点”按钮，然后单击浮动命令工具中的“运行”按钮。

此时，您应该在带有断点的行上看到一个红色停止标志，并在同一行上看到一个绿色箭头（即将执行的代码）。让我们使用 DDD 来显示一些内部信息。

首先，选择“数据-->显示局部变量”。接下来，选择“数据-->显示参数”，然后选择“状态-->回溯”。最后，在控制台窗口中键入 graph display v[0]@n，然后按 Enter 键。这将显示 v[] 数组的元素 0 到 n（参见图 2）。

图 2. 在 if (n <= 1) 处中断

断点已设置，以便在我们给定的数组包含一个或更少元素时不执行任何操作。由于这是一个递归快速排序，因此当传入只有一个元素的数组时，此测试对于结束递归是必要的（稍后详细介绍）。

在此测试之后，我们选择我们的主元并将其移动到数组的开头。单击“下一步”按钮，直到绿色箭头指向对 swap 函数的调用。 “下一步”继续到下一行，而不会进入子例程调用。 “步进”将尝试步入其他子例程。现在，再次单击“下一步”以查看会发生什么。

我的机器交换了 v[] 的第 0 个和第 1 个元素，这意味着 rand() % n 返回 1。如果您调试此程序几次，您可能会注意到 rand() % n 始终返回 1。不是很随机，您说？在本例中，通过注释掉对 srand() 的调用，伪随机生成器永远不会被种子化，并且 rand() 返回可预测的结果。

选择的主元将用于分隔小于自身和大于自身的数字。主元被移动到 v[0]，因为在我们检查整个数组之前，我们不知道它应该在哪里。

“partition”循环遍历数组的每个元素并将其与主元（在我的例子中是数字 12）进行比较。 Last 先递增，因此索引 1 处的元素与自身交换（我知道这是一种浪费）。优化此算法留给受虐狂的读者作为练习。请注意，您可以随时单击“中断”，然后单击“运行”以重新开始。

单击“下一步”直到 i 等于 3 且 last 等于 2（在图形数据窗口中观察局部变量显示）。分区循环内的“if”测试现在将 18 与 12 进行比较。测试失败（下一步），因此 i 递增（下一步），并且 last 仍然等于 2。

持续“下一步”直到 i 等于 9。我的数组现在是 { 12 6 4 3 18 27 16 15 19 }。再次单击“下一步”，3 与 12 交换，位于较小数字和较大数字之间。

在将主元值恢复到其原始位置后，我们递归调用 quicksort，发送指向 v[0] 的指针并告诉它期望一个三元素数组（较小的数字）。然后我们再次递归调用 quicksort，发送指向 v[4] 的指针并声明一个五元素数组（较大的数字）。这些 quicksort 调用再次递归，直到只有单元素数组被传递到递归调用中。只有到那时，递归调用才会返回——最深层的调用先返回——直到我们返回到带有已排序数组的主函数。 呼！

如果您深入到递归的 quicksort() 调用中，您会注意到 v[0]@n 显示已禁用。添加一个按钮可以轻松地重新创建此显示。要创建按钮，请单击“命令-->编辑按钮...-->数据按钮”。在文本输入字段中，输入

graph display v[0]@n // Varray

一个名为 Varray 的按钮应该在数据窗口顶部弹出。当 v[0]@n 显示读取（已禁用）时，右键单击显示并选择“取消显示”。然后，单击新的 Varray 按钮。如果它仍然被禁用，请尝试“下一步”几次并再次单击按钮。

之前，我让您打开了堆栈回溯窗口。当您深入到 quicksort() 调用中时，通过单击回溯窗口中的其他行来检查堆栈会很有趣。您可以看到如何到达当前的调用上下文以及堆栈中不同点的数据外观。

如果您真的病态且扭曲，请尝试“查看-->机器代码窗口”以查看正在执行的实际汇编程序指令。

DDD 非常适合显示链表和其他数据结构。试试看！另外，我已经提到这个快速排序实现远非优化。要查看高度优化的版本，请查看 GNU C 库中的 qsort.c。

资源