出于教育目的,我编写了自己的快速排序方法。为了改进它,我查看了 .NET 源代码以了解如何使用 LINQ OrderBy()
方法实现。
我找到了以下 Quicksort method :
void QuickSort(int[] map, int left, int right) {
do {
int i = left;
int j = right;
int x = map[i + ((j - i) >> 1)];
do {
while (i < map.Length && CompareKeys(x, map[i]) > 0) i++;
while (j >= 0 && CompareKeys(x, map[j]) < 0) j--;
if (i > j) break;
if (i < j) {
int temp = map[i];
map[i] = map[j];
map[j] = temp;
}
i++;
j--;
} while (i <= j);
if (j - left <= right - i) {
if (left < j) QuickSort(map, left, j);
left = i;
}
else {
if (i < right) QuickSort(map, i, right);
right = j;
}
} while (left < right);
}
我正在尝试了解内部工作原理。 据我所知,它看起来与 Hoare partition scheme 非常相似但有一些轻微的优化。
我不清楚的是:
- 为什么我们在分区后只递归主元的一侧? (取决于
if (j - left <= right - i)
的结果) - 为什么我们有一个
do { ... } while (left < right)
在整个事情?是因为我们只递归了上面建议的枢轴的一侧吗? - 为什么有
if (i < j)
交换前的条件测试 ?不是break;
声明之前够吗?
相比之下,这是我的实际实现 Quicksort 的样子(霍尔分区方案的直接实现)
void QuickSort(int[] map, int left, int right)
{
if (left < right)
{
int i = left - 1;
int j = right + 1;
int x = map[left + ((right - left) >> 1)];
while (true)
{
do { i++; } while (Compare(map[i], x) < 0);
do { j--; } while (Compare(map[j], x) > 0);
if (i >= j) break;
int temp = map[i];
map[i] = map[j];
map[j] = temp;
}
QuickSort(map, left, j);
QuickSort(map, j + 1, right);
}
}
最佳答案
Why do we recurse only one side of the pivot after partitionning ? (depending the result of the if (j - left <= right - i) )
最小化递归深度(和堆栈使用)。当我们尽快处理较大的分区并且只对较小的分区进行递归时,深度不会超过log(n)
Why do we have a do { ... } while (left < right) over the whole thing ?
left
之前和right
之后的项目是排序的,所以当所有数组排序时这些索引相遇
Why is there a if (i < j) conditional test before the swap ?
只是为了避免对相等索引进行不必要的交换
关于c# - 以下快速排序方法如何工作?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44587043/