Quicksort没有正确排序

尝试从Quicksort的实现中学习，我无法找出为什么它没有正确排序。

使用此序列：

6,7,12,5,9,8,65,3

它返回：

3,5,7,8,9,65,12,6

它似乎有些不同，但不是全部。 我错过了什么？

这是我的代码：

static void Main(string[] args) { QuickSort qs = new QuickSort(); int[] arr = new int[] { 6, 7, 12, 5, 9, 8, 65, 3 }; foreach (int l in arr) { Console.Write(l + ", "); } int left = 0; int right = arr.Count() - 1; int[] arrr = qs.DoQuickSort(ref arr, left, right); Console.WriteLine("Sorted List: "); foreach (int i in arrr) { Console.Write(i + " "); } Console.ReadLine(); } public int Partition(int[] array, int left, int right, int PivotIndex) { int pivValue = array[PivotIndex]; array = Swap(ref array, PivotIndex, right); int storeIndex = left; for (int i = PivotIndex; i < right-1; i++) { if (array[i]  left) { int PivIndex = (left + right) / 2; int newPivIndex = Partition(array, left, right, PivIndex); DoQuickSort(ref array, left, newPivIndex - 1); DoQuickSort(ref array, newPivIndex + 1, right); } return array; } 

Answer 1

除了我对这个问题本身的评论之外，我想指出Swap()和DoQuickSort()方法不需要返回数组（根据我在注释中的注释说明数组是一个引用本身） 。 为此，您执行此任务的代码应如下所示：

 public int Partition(int[] array, int left, int right, int pivotIndex) { int pivValue = array[pivotIndex]; Swap(array, pivotIndex, right); int storeIndex = left; for (int i = left; i < right; i++) { if (array[i] <= pivValue) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, right); return storeIndex; } public void Swap(int[] arr, int first, int second) { int temp = arr[first]; arr[first] = arr[second]; arr[second] = temp; } public void DoQuickSort(int[] array, int left, int right) { if (right > left) { int pivIndex = (left + right) / 2; int newPivIndex = Partition(array, left, right, pivIndex); DoQuickSort(array, left, newPivIndex - 1); DoQuickSort(array, newPivIndex + 1, right); } } 

Answer 2

你要么被交给鱼，还是被教导如何钓鱼？

学习如何调试自己的程序，而不是依赖其他人为你做，这是一项将来很好地为你服务的技能。

当遇到这个问题时，我要做的第一件事就是用代码标记代码，指出每段代码的语义目的：

 // Choose a pivot halfway along the portion of the list I am searching. int PivIndex = (left + right) / 2; // Partition the array so that everything to the left of the pivot // index is less than or equal to the pivot, and everything to // the right of the pivot is greater than or equal to the pivot. int newPivIndex = Partition(array, left, right, PivIndex); // Recursively sort each half. DoQuickSort(ref array, left, newPivIndex - 1); DoQuickSort(ref array, newPivIndex + 1, right); 

好的，现在， 在这里的某个地方有一个错误。 哪里？ 开始列出您认为是真实的事实，并为每个事实写一个断言。 编写自己的帮助方法，如AllLessThan，它可以validation断言。

 // Choose a pivot halfway along the portion of the list I am searching. int PivIndex = (left + right) / 2; int pivotValue = array[PivIndex]; // Partition the array so that everything to the left of the pivot // index is less than or equal to the pivot, and everything to // the right of the pivot is greater than or equal to the pivot. int newPivIndex = Partition(array, left, right, PivIndex); Debug.Assert(array[newPivIndex] == pivotValue); Debug.Assert(AllLessThanOrEqual(array, left, newPivIndex, pivotValue)); Debug.Assert(AllGreaterThanOrEqual(array, newPivIndex, right, pivotValue)); // Recursively sort each half. DoQuickSort(ref array, left, newPivIndex - 1); Debug.Assert(IsSorted(array, left, newPivIndex)); DoQuickSort(ref array, newPivIndex + 1, right); Debug.Assert(IsSorted(array, left, right)); 

现在当你再次运行这个程序时，你的一个断言被违反的那一刻，你会得到一个弹出的框来告诉你这个bug的本质是什么。 继续这样做，用断言记录你的前置条件和后置条件，直到找到bug。

Answer 3

在Partition方法中，您的循环范围错误：

 for (int i = PivotIndex; i < right-1; i++) 

应该成为：

 for (int i = left; i < right; i++) 

查看相关的维基百科文章 ，其中说：

 function partition(array, left, right, pivotIndex) pivotValue := array[pivotIndex] swap array[pivotIndex] and array[right] // Move pivot to end storeIndex := left for i from left to right - 1 // left ≤ i < right if array[i] ≤ pivotValue swap array[i] and array[storeIndex] storeIndex := storeIndex + 1 swap array[storeIndex] and array[right] // Move pivot to its final place return storeIndex 

注意： left ≤ i < right