K＆R Qsort示例与指针和arrays混淆

我发现很难理解下面的代码片段。 我理解指向function矫揉造成的指针，但我发现混淆在指示的行中。 

void qsort(void **v, int left, int right, int (*comp) (void *, void *)) { int i, last; void swap(int **v, int i, int j); if (left >= right) /* do nothing if array contains */ return; /* fewer than two elements */ swap(v, left, (left + right)/2); /* move partition elem */ [1] last = left; /* to v[0] */ [2] for (i = left + 1; i <= right; i++) /* partition */ [3] if ((*comp) (v[i], v[left]) < 0) [4] swap(v, ++last, i); [5] swap(v, left, last); /* restore partition elem */ [6] qsort(v, left, last - 1); [7] qsort(v, last + 1, right); [8] }

有人可以向我解释这个例程，特别是指示的行，只要告诉我它正在做什么，因为我无法想象这个qsort，我读的爱斯基摩指南，同时读k＆r说qsort例程是垃圾，过于复杂。 我只需要理解为什么它是这样写的，因为它对我来说没有意义。

谢谢，如果没有，请阅读此内容。

这是一段美丽的代码！

首先，了解quicksort背后的想法非常重要：

1）记下一个数字列表。

2）选择一个，称之为X.

3）制作两个列表，其中一个小于X的数字，以及所有数字中的一个更大。

4）对小于X的数字进行排序。对大于X的数字进行排序。

我们的想法是，如果我们幸运并为X选择一个好的值，那么小于X的数字列表与大于X的数字列表的大小相同。如果我们从2 * N + 1个数字开始，那么我们得到两个N个数字的列表。 每次，我们希望除以2，但我们必须排序N个数字。 我们可以将N除以2分多少次？ 那是Log（N）。 所以，我们排序N Log（N）次。 这很棒！

至于代码是如何工作的，这里是粗略的，带有一点草图。 我们会挑选一个小arrays:)

这是我们的arrays：[DACBE]

在开始时，左= 0，指向D.右= 4，指向E.

现在，按照代码，用您的标签：

[1]交换（v，0,2）[DACBE] – > [CADBE]

我们已经将我们选择的值交换出来并将其放在数组的开头。

[2] last = 0

这有点聪明……我们想要保留一个计数器，这样我们就知道哪些值更大，哪些更少…你会看到这种进展如何

[3] for（i = 1; i <= 4; i ++）

对于列表中的所有剩余元素……

[4] if（（* comp）（v [i]，’C’）<0）

如果i的值小于’C’……

[5] swap（v，++ last，i）;

把它放在列表的开头！

让我们运行3,4,5的代码

I = 1：

[CADBE]

if（’A’<'C'）

交换（’A’，’A’）（并且最后增加！）

[CADBE] – > [CADBE]（无变化）

最后= 1

I = 2：

[CADBE]

if（’D’<'C'）

失败。 继续。

I = 3：

[CADBE]

if（’B’<'C'）

交换（’B’，’D’）并且最后增加！

[CADBE] – > [CABDE]（看！它正在排序！）

最后= 2

I = 4：

[CABDE]

if（’E’<'C'）

失败。 继续。

好的，王牌。 所以循环给出的是[CABDE]，last = 2（’B’）

现在行[6] ….交换（左，最后）……那是交换（’C’，’B’）[CABDE] – > [BACDE]

现在，这个的魔力是……它已经部分排序了！ BA

所以现在我们对子列表进行排序!!

[7] – > [BA] – > [AB]

所以

[BACDE] – > [ABCDE]

[8] – > [DE] – > [DE]

所以

[ABCDE] – > [ABCDE]

我们完成了！

K＆R的快速是一个很好的编码的例子，但不是快速排序如何工作的一个很好的例子。 预先交换的目的不直观，身份互换效率低下且令人困惑。 我写了一个程序来帮助澄清这一点。 代码注释解释了这些问题。

我只在Linux下进行了编译和测试，但Visual Studio应该没有问题这个简单的vanilla控制台应用程序。 

 / ***************************** QUICK.CPP ***************** **********************
作者：David McCracken
更新：2009-08-14

目的：这说明了快速排序在K＆R“The C 
编程语言“（第二版，第120页）。许多程序员都很沮丧 
当他们试图从这个版本中了解一般的快速排序时 
显然不是关于quicksort的教程，而是关于指针的使用 
function。 我的程序修改原始文件只能在int上工作 
专注于分拣过程。 它可以打印全局列表和递归 
每个更改的子列表以跟踪排序决策过程。 我的节目也 
澄清两个令人困惑的方面，包括无法解释的交换 
通过比较其操作与两个进一步修改版本的操作。

原始的一个令人困惑的事情是将项目与自己交换。
代码（仅针对int进行修改）是：

 last = left;
 for（i = left + 1; i <= right; i ++）
    if（v [i] 
 #include 
 #include 
 #include 

 // ========================数据和声明===================== ==========
 #define DIM（A）（A / sizeof A [0]的大小）
 typedef unsigned int UINT;

枚举{SHOW_NOTHING，SHOW_GLOBAL = 1，SHOW_LOCAL1 = 2，SHOW_LOCAL = 4， 
        SHOW_INDEX = 8，SHOW_ALL = 0xFF};

 int showWhat = SHOW_NOTHING;

 int list0 [] = {4,0,2,5,1,3};
 int list1 [] = {0,1,2,3,4,5,6,7,8,9,10,11};
 int list2 [] = {11,10,9,8,7,6,5,4,3,2,1,0};
 int list3 [] = {11,9,7,5,3,1,0,2,4,6,8,10};
 int list4 [] = {11,0,10,1,9,2,8,3,7,4,6​​,5};
 static struct {int * list;  int cnt;  } lists [] = 
 { 
     {list0，DIM（list0）}，
     {list1，DIM（list1）}，
     {list2，DIM（list2）}，
     {list3，DIM（list3）}，
     {list4，DIM（list4）}，
 };

 int total [1000];
 int totalCnt;
 int * userData = 0;
 int userDataLen = 0;

 int递归;  //当前递归级别。
 int调用;  //调用sort函数的次数。
深度;  //最大递归级别。
 int交换;  //掉期数量。
 int比较;  //列表项的计数比较。
 int totCalls;
 int totDepth;
 int totCompares;
 int totSwaps;

 void（* sortFunc）（int * list，int left，int right）;

 char dArg ='A';  //命令行参数选择0,1,2,3,4或A.
 int dataList;  //如果dArg是数字，这是它的int值。

 // ==============================function================= ====================

 // ------------------------------ indent ----------------- ---------------------
 //为每个递归级别打印两个空格以缩进后续打印 
 //输出
 // ................................................ ............................
 void indent（void）
 {
     for（int indent = 1; indent  = 0）
     {
        开关（showWhat）
         {
        案例SHOW_NOTHING：
            返回;
         case SHOW_GLOBAL：//只有SHOW_GLOBAL
             if（local> 0）
                返回;  //这是一个本地人
            打破;  //没有图例的打印列表。
         default：// SHOW_GLOBAL，SHOW_LOCAL1，SHOW_LOCAL的某种组合
             if（local == 0）// global
             {
                 if（（showWhat＆SHOW_GLOBAL）== 0）
                    返回;
                 printf（“GLOBAL”）;
             }
             else if（showWhat＆SHOW_LOCAL ||（showWhat＆SHOW_LOCAL1 && local == 1））
             {
                缩进（）;
                 printf（“Local％d：”，local）;
             }
            其他
                返回;
         }
     }
     for（int * end = ia + cnt; ia 深度）
         depth =递归;  //首先调用recursion = 0，深度为0，即还没有递归。
     ++递归;
     show（total，totalCnt，0）;  // GLOBAL
    显示（列表+左，右 - 左+ 1,1）;  // LOCAL
     if（左<右）
     {
         swap（list + left，list +（left + right）/ 2）;
         ++互换;
        显示（列表+左，右 - 左+ 1,2）;
         last = left;
         for（i = left + 1; i <= right; i ++）
         {
             ++比较;
             if（list [i] 深度）
         depth =递归;  //首先调用recursion = 0，深度为0，即还没有递归。
     ++递归;
     show（total，totalCnt，0）;  // GLOBAL
    显示（列表+左，右 - 左+ 1,1）;  // LOCAL
     if（左<右）
     {
         swap（list + left，list +（left + right）/ 2）;
         ++互换;
        显示（列表+左，右 - 左+ 1,2）;
         last = left;
         for（i = left + 1; i <= right; i ++）
         {
             ++比较;
             if（list [i] 深度）
         depth =递归;  //首先调用recursion = 0，深度为0，即还没有递归。
     ++递归;
     show（total，totalCnt，0）;  // GLOBAL
    显示（列表+左，右 - 左+ 1,1）;  // LOCAL
     if（左<右）
     {
         last = left;
         for（i = left + 1; i <= right; i ++）
         {
             ++比较;
             if（list [i]  =（int）DIM（列表））
                 {
                     printf（“错误：坏数据列表选择器％c \ n”，dArg）;
                    返回1;
                 }
             }
            打破;
         case'S'：// show selector匹配bit-mapped showWhat或N或A.
             ++ CP;
             if（* cp！= 0 || toupper（* cp）！='N'）
             {
                 if（toupper（* cp）=='A'）
                     showWhat = SHOW_ALL;
                其他
                     showWhat = atoi（cp）;
             }
            打破;
        默认：
             if（！isdigit（* cp））
             {   
                 printf（“错误：没有选项％c \ n”，* cp）;
                返回1;
             }
             for（idx = 0; idx 
结果很快
这使用所有默认值，这对于比较性能最有用
三个不同的function。

 ====== krQuick ======
 4 0 2 5 1 3 
 0 1 2 3 4 5 
 Calls = 7，depth = 2，compare = 8，swaps = 20
 ---------------------------------
 0 1 2 3 4 5 6 7 8 9 10 11 
 0 1 2 3 4 5 6 7 8 9 10 11 
呼叫= 15，深度= 3，比较= 25，交换= 48
 ---------------------------------
 11 10 9 8 7 6 5 4 3 2 1 0 
 0 1 2 3 4 5 6 7 8 9 10 11 
呼叫= 17，深度= 5，比较= 30，交换= 62
 ---------------------------------
 11 9 7 5 3 1 0 2 4 6 8 10 
 0 1 2 3 4 5 6 7 8 9 10 11 
 Calls = 13，depth = 5，compare = 33，swaps = 56
 ---------------------------------
 11 0 10 1 9 2 8 3 7 4 6 5 
 0 1 2 3 4 5 6 7 8 9 10 11 
 Calls = 15，depth = 6，compare = 38，swaps = 60
 ---------------------------------
总计：调用= 67，深度= 21，比较= 134，交换= 246
 ====== krQuick2（没有身份互换）======
 4 0 2 5 1 3 
 0 1 2 3 4 5 
 Calls = 7，depth = 2，compare = 8，swaps = 16
 ---------------------------------
 0 1 2 3 4 5 6 7 8 9 10 11 
 0 1 2 3 4 5 6 7 8 9 10 11 
 Calls = 15，depth = 3，compare = 25，swaps = 28
 ---------------------------------
 11 10 9 8 7 6 5 4 3 2 1 0 
 0 1 2 3 4 5 6 7 8 9 10 11 
呼叫= 17，深度= 5，比较= 30，交换= 52
 ---------------------------------
 11 9 7 5 3 1 0 2 4 6 8 10 
 0 1 2 3 4 5 6 7 8 9 10 11 
 Calls = 13，depth = 5，compare = 33，swaps = 46
 ---------------------------------
 11 0 10 1 9 2 8 3 7 4 6 5 
 0 1 2 3 4 5 6 7 8 9 10 11 
 Calls = 15，depth = 6，compare = 38，swaps = 44
 ---------------------------------
总计：调用= 67，深度= 21，比较= 134，交换= 186
 ====== quick3（没有预换）======
 4 0 2 5 1 3 
 0 1 2 3 4 5 
 Calls = 7，depth = 3，compare = 10，swaps = 10
 ---------------------------------
 0 1 2 3 4 5 6 7 8 9 10 11 
 0 1 2 3 4 5 6 7 8 9 10 11 
 Calls = 23，depth = 11，compare = 66，swaps = 22
 ---------------------------------
 11 10 9 8 7 6 5 4 3 2 1 0 
 0 1 2 3 4 5 6 7 8 9 10 11 
 Calls = 23，depth = 11，compare = 66，swaps = 22
 ---------------------------------
 11 9 7 5 3 1 0 2 4 6 8 10 
 0 1 2 3 4 5 6 7 8 9 10 11 
 Calls = 15，depth = 7，compare = 46，swaps = 54
 ---------------------------------
 11 0 10 1 9 2 8 3 7 4 6 5 
 0 1 2 3 4 5 6 7 8 9 10 11 
 Calls = 19，depth = 6，compare = 37，swaps = 30
 ---------------------------------
总计：调用= 87，深度= 38，比较= 225，交换= 138

 ************************************************** *****************************

快速f0 s5 d1的结果
 S5格式最适合显示子列表在排序期间的更改方式。 以来 
只有交换后才会显示LOCAL，多余的身份交换（许多内容在此 
例子）很明显。

 ====== krQuick ======
 0 1 2 3 4 5 6 7 8 9 10 11 
 GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
 Local1：0 1 2 3 4 5 6 7 8 9 10 11 
 Local2：5 1 2 3 4 0 6 7 8 9 10 11 
 Local3：5 1 2 3 4 0 6 7 8 9 10 11 
 Local3：5 1 2 3 4 0 6 7 8 9 10 11 
 Local3：5 1 2 3 4 0 6 7 8 9 10 11 
 Local3：5 1 2 3 4 0 6 7 8 9 10 11 
 Local3：5 1 2 3 4 0 6 7 8 9 10 11 
 Local4：0 1 2 3 4 5 6 7 8 9 10 11 
 GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
   Local1：0 1 2 3 4 
   Local2：2 1 0 3 4 
   Local3：2 1 0 3 4 
   Local3：2 1 0 3 4 
   Local4：0 1 2 3 4 
 GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
     Local1：0 1 
     Local2：0 1 
     Local4：0 1 
 GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
       LOCAL1： 
 GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
       Local1：1 
 GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
     Local1：3 4 
     Local2：3 4 
     Local4：3 4 
 GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
       LOCAL1： 
 GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
       Local1：4 
 GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
   Local1：6 7 8 9 10 11 
   Local2：8 7 6 9 10 11 
   Local3：8 7 6 9 10 11 
   Local3：8 7 6 9 10 11 
   Local4：6 7 8 9 10 11 
 GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
     Local1：6 7 
     Local2：6 7 
     Local4：6 7 
 GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
       LOCAL1： 
 GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
       Local1：7 
 GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
     Local1：9 10 11 
     Local2：10 9 11 
     Local3：10 9 11 
     Local4：9 10 11 
 GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
       Local1：9 
 GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
       Local1：11 
 0 1 2 3 4 5 6 7 8 9 10 11 
呼叫= 15，深度= 3，比较= 25，交换= 48

 ************************************************** ******************************

快速f0 sa d1的结果
这与前一个示例相同，但显示了索引的其他详细信息
导致交换决定的价值观。 然而，杂乱往往模糊不清
实际发生在子列表中的是什么。

 ====== krQuick ======
 0 1 2 3 4 5 6 7 8 9 10 11 
 GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
 Local1：0 1 2 3 4 5 6 7 8 9 10 11 
 Local2：5 1 2 3 4 0 6 7 8 9 10 11 
 i = 1 @ i = 1左= 0 @左= 5最后= 0
 Local3：5 1 2 3 4 0 6 7 8 9 10 11 
 i = 2 @ i = 2 left = 0 @ left = 5 last = 1
 Local3：5 1 2 3 4 0 6 7 8 9 10 11 
 i = 3 @ i = 3 left = 0 @ left = 5 last = 2
 Local3：5 1 2 3 4 0 6 7 8 9 10 11 
 i = 4 @ i = 4 left = 0 @ left = 5 last = 3
 Local3：5 1 2 3 4 0 6 7 8 9 10 11 
 i = 5 @ i = 0 left = 0 @ left = 5 last = 4
 Local3：5 1 2 3 4 0 6 7 8 9 10 11 
 Local4：0 1 2 3 4 5 6 7 8 9 10 11 
 GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
   Local1：0 1 2 3 4 
   Local2：2 1 0 3 4 
   i = 1 @ i = 1左= 0 @左= 2最后= 0
   Local3：2 1 0 3 4 
   i = 2 @ i = 0 left = 0 @ left = 2 last = 1
   Local3：2 1 0 3 4 
   Local4：0 1 2 3 4 
 GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
     Local1：0 1 
     Local2：0 1 
     Local4：0 1 
 GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
       LOCAL1： 
 GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
       Local1：1 
 GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
     Local1：3 4 
     Local2：3 4 
     Local4：3 4 
 GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
       LOCAL1： 
 GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
       Local1：4 
 GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
   Local1：6 7 8 9 10 11 
   Local2：8 7 6 9 10 11 
   i = 7 @ i = 7 left = 6 @ left = 8 last = 6
   Local3：8 7 6 9 10 11 
   i = 8 @ i = 6 left = 6 @ left = 8 last = 7
   Local3：8 7 6 9 10 11 
   Local4：6 7 8 9 10 11 
 GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
     Local1：6 7 
     Local2：6 7 
     Local4：6 7 
 GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
       LOCAL1： 
 GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
       Local1：7 
 GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
     Local1：9 10 11 
     Local2：10 9 11 
     i = 10 @ i = 9 left = 9 @ left = 10 last = 9
     Local3：10 9 11 
     Local4：9 10 11 
 GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
       Local1：9 
 GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
       Local1：11 
 0 1 2 3 4 5 6 7 8 9 10 11 
呼叫= 15，深度= 3，比较= 25，交换= 48

魔术有用的谷歌关键词：QuickSort

例如google：quicksort的工作原理如下所示： http ：//www.angelfire.com/pq/jamesbarbetti/articles/sorting/001a_HowQuicksortWorks.htm等。

本质上，代码将快速排序的变体应用于指定的right边界之间的元素。

对于您已确定的线路：

  1. 将中间元素与第一个（ left ）交换。 它将成为“枢纽”。

  2. 跟踪更大和更小元素之间的边界。 这是枢轴所属的地方。

  3. 对于第一个之后的每个元素，
  4. 如果它小于枢轴，

  5. 在第一个更大元素之前移动它。

  6. 将枢轴移回原位。

  7. 递归地将qsort应用于数据透视之前的元素。 （较小的）

  8. 在透视后递归地将qsort应用于元素。 （较大的）

尝试将代码自己应用到数字列表中，看看它是否更有意义….

你的代码中有一个错误，最后的行： 

 qsort(v, left, last - 1); [7] qsort(v, last + 1, right); [8]

应该： 

 qsort(v, left, last - 1, comp); [7] qsort(v, last + 1, right, comp); [8]

或者我错过了什么？

此外，重用标准库的名称是不好的方式，特别是如果新函数的签名与lib中的签名不同。 标准库的函数qsort有这个原型： 

  void qsort(void *base, size_t nel, size_t width, int (*compar)(const void *, const void *));

如果你的程序有点大（多个目标文件），这可能会带来有趣的错误。 想象一下调用标准qsort函数的另一个模块，但是当你重新定义它时，使用兼容的签名，但是使用不同的语义，你会得到一个意想不到的bug。

嗨，我做了第87页的例子。可能有人会从中理解。 但在使用此代码之前，请参阅quicksort 

 /** * qsort.c * Quick sort using recursion */ #include  void qsort(int v[], int left, int right); int main() { int v[] = {9, 3, 4, 6, 7, 3, 1}; qsort(v, 0, 6); int i; for (i = 0; i < 7; i++) printf(" %d ", v[i]); printf("\n"); return 0; } void qsort(int v[], int left, int right) { int i, last; /* last is pivot */ void swap(int v[], int i, int j); if (left >= right) return; swap(v, left, (left + right) / 2); // swap mid element to front last = left; // set this position as pivot for (i = left + 1; i <= right; i++) { /*loop through every other element swap elements less than pivot ie bigger to right, smaller to left */ if (v[i] < v[left]) swap(v, ++last, i); // when swapping lesser element, record // where our pivot moves /* we don't swap elements that are bigger than pivot, and are to right. However we swap elements those are less than pivot. With ++pivot we are essentially going to find out, where our pivot will fit to be at the position, where all the elements before it are less than it and all after it greater. */ } // swap left(our pivot) to last(where pivot must go // ie all elements before pivot are less than it // and all elements above it are greater // remember they are lesser and greater // but may not be sorted still // this is called partition swap(v, left, last); // Do same(qsort) for all the elements before our pivot // and above our pivot qsort(v, left, last - 1); // last is our pivot position qsort(v, last + 1, right); // Each of above two qsort will use middle element as pivot and do // what we did above, because same code will be executed by recursive // functions } void swap(int v[], int i, int j) { int temp; temp = v[i]; v[i] = v[j]; v[j] = temp; }

最重要的部分是枢轴（将你的一只脚放在适当的位置，同时自由移动另一只脚）。 我们选择中间元素作为枢轴，将其置于前面，将其与所有其他元素进行比较。 如果它们小于我们的枢轴，我们交换它们并仅增加我们的枢轴位置（小心我们的枢轴元素仍然位于第一位）。 在我们完成循环后，我们将枢轴元素（首先是）带到这个地方（枢轴位置）。 在循环之后，我们在枢轴之前的所有元素都小于枢轴，并且所有那些在枢轴之上的元素大于枢轴。 在第一次循环时，它们没有排序。 因此，您必须再次将相同的排序算法递归应用于枢轴下方和枢轴上方的所有元素以对它们进行排序。

Interesting Posts

C错误：对’_itoa’的未定义引用

为什么这个程序没有为float和double数据类型提供输出？

Objective-C ++与Objective-C完全不同吗？

升级到Mojave后无法在Mac上编译C程序

如何使用指针复制字符串

在C：代理HTTP请求到另一台服务器

fgets（）函数无法接受来自命令提示符的消息

由ffmpeg和SDL制作的奇怪声音

如何在纯C中进行正则表达式字符串替换？

为什么我没有堆栈溢出？