C#中的Sort()方法使用递归吗？

Question

我最近读到，C# 使用快速排序算法对数组进行排序。我想知道C#使用递归方法还是迭代方法？

我发现的是这个链接，在我看来他们使用迭代方法。我只是想知道C#是否真的使用了QuickSort算法的迭代实现？

Answer 1

有两件事：

1. C# 从 QuickSort 转移到 IntrospectiveSort，正如您的链接所示。您可以在

   Sort

   源代码中查看注释和兼容性支持。

2. 您引用的代码是递归的。接近循环末尾的是递归调用：

   private void IntroSort(int lo, int hi, int depthLimit)
   {
       while (hi > lo)
       {
           int partitionSize = hi - lo + 1;
           if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold)
           {
               // ... 
               InsertionSort(lo, hi);
               return;
           }
           // ...
           int p = PickPivotAndPartition(lo, hi);
           IntroSort(p + 1, hi, depthLimit); // <--- recursive call
           hi = p - 1;
       }
   }
   

   循环的下一次迭代采用 left 分区，递归调用采用 right 分区。

Answer 2

在该链接中，您可以看到它调用自身（递归）

2471    IntroSort(p + 1, hi, depthLimit)