实现快速排序算法

Question

我从这本书中找到了快速排序算法

这就是算法

QUICKSORT (A, p, r)
if p < r
    q = PARTITION(A, p, r)
    QUICKSORT(A, p, q-1)
    QUICKSORT(A, q+1, r)

PARTITION(A, p, r)
x=A[r]
i=p-1
for j = p to r - 1
  if A <= x
     i = i + 1
     exchange A[i] with A[j]
exchange A[i+1] with A[r]
return i + 1

我编写了以下这段 C# 代码：

private void quicksort(int[] input, int low, int high)
{
    int pivot_loc = 0;

    if (low < high)
        pivot_loc = partition(input, low, high);
    quicksort(input, low, pivot_loc - 1);
    quicksort(input, pivot_loc + 1, high);
}

private int partition(int[] input, int low, int high)
{
    int pivot = input[high];
    int i = low - 1;

    for (int j = low; j < high-1; j++)
    {
        if (input[j] <= pivot)
        {
            i++;
            swap(input, i, j);
        }
    }
    swap(input, i + 1, high);
    return i + 1;
}



private void swap(int[] ar, int a, int b)
{
    temp = ar[a];
    ar[a] = ar[b];
    ar[b] = temp;
}

private void print(int[] output, TextBox tbOutput)
{
    tbOutput.Clear();
    for (int a = 0; a < output.Length; a++)
    {
        tbOutput.Text += output[a] + " ";
    }
}

当我调用这样的函数 quicksort(arr,0,arr.Length-1); 时，会出现以下错误 An unhandled exception of type 'System.StackOverflowException' occurred，这是因为传递了空数组... 当我调用这样的函数 quicksort(arr,0,arr.Length); 时，会出现错误 Index was outside the bounds of the array.，该错误发生在此行 int pivot = input[high];，但是数组已经成功传递。

我还想像这样打印它 print(input,tbQuick);，但在哪里放置它才能在快速排序完成后打印呢？

- a1204773

---

我不理解问题的最后一部分 - 打印的事情 - 因为您的代码没有显示您实际调用quicksort的位。为什么不在调用quicksort之后直接打印作为下一个语句呢？ - Deestan

因为我的代码有无限循环，所以我不知道在哪里放置打印语句才能只打印一次...现在好了。 - a1204773

只需将递归函数包装在另一个函数中，以便在排序完成时打印它。 - Sarien

该问题已被保护，因为它吸引了大量的答案，这些答案只是快速排序实现的副本，而不是真正回答问题。 - Peter Duniho

Answer 1

您没有正确实现基本情况终止条件，这会导致quicksort不停地递归自身并使用长度为 0 的子列表。

请将这部分改成：

if (low < high)
    pivot_loc = partition(input, low, high);
quicksort(input, low, pivot_loc - 1);
quicksort(input, pivot_loc + 1, high);

对于这个：

if (low < high) {
    pivot_loc = partition(input, low, high);
    quicksort(input, low, pivot_loc - 1);
    quicksort(input, pivot_loc + 1, high);
}

- Deestan

---

实际上，我第一次从这里http://www.algorithmist.com/index.php/Quicksort得到了代码，然后检查了书，它几乎是相同的... 没有看到。 - a1204773

Answer 2

除了Deestan的回答之外，你还有一个错误：

for (int j = low; j < high-1; j++)

应该是：

for (int j = low; j < high; j++)

- Eren Ersönmez

---

但是你是对的... 在将它改成“高”之后，它给出了正确的结果... 我不知道书中可能会有错误 o_0 - a1204773

这是2路还是3路快速排序？ - a1204773

标准的双向排序——在每次递归排序时，将分区细分为两个更小的分区。 - Eren Ersönmez

好的，谢谢。我想确认一下...我找不到任何好的三向快速排序算法...你知道如何做或者知道在哪里可以找到吗？ - a1204773

书本没有错误，如果你使用了 high-1，那么你应该使用 <=，这样你的语句就应该是 for (int j = low; j <= high-1; j++)。 - soccer7

Answer 3

这是快速排序算法的最短实现（无 StackOverflowException）

IEnumerable<T> QuickSort<T>(IEnumerable<T> i) where T :IComparable
{
    if (!i.Any()) return i;
    var p = i.ElementAt(new Random().Next(0, i.Count() - 1));
    return QuickSort(i.Where(x => x.CompareTo(p) < 0)).Concat(i.Where(x => x.CompareTo(p) == 0)).Concat(QuickSort(i.Where(x => x.CompareTo(p) > 0)));
}

- Ali Bayat

---

所提出的问题是关于作者代码中的“StackOverflowException”。这个答案并没有以任何方式回答那个问题。 - Peter Duniho

Answer 4

如果您想要一些更短的快速排序代码：

    IEnumerable<int> QuickSort(IEnumerable<int> i)
    {
        if (!i.Any())
            return i;
        var p = (i.First() + i.Last) / 2 //whichever pivot method you choose
        return QuickSort(i.Where(x => x < p)).Concat(i.Where(x => x == p).Concat(QuickSort(i.Where(x => x > p))));
    }

使用适当的方法获取p（枢轴点）。

- FBryant87

---

你误用了 Random。要么将一个 Random 参数传递到 QuickSort 函数中，要么引用方法范围之外的单个实例。初始化会重新生成对象种子，如果非常快速地执行，则可能导致不太随机的结果。 - Kjata30

如前所述，“p”可以通过任何最合适的方法获得-我在这里展示的是方法大小，但是您关于随机的观点是正确的。 - FBryant87

所提出的问题是关于作者代码中的“StackOverflowException”。这个回答并没有以任何方式回答那个问题。 - Peter Duniho

它并没有 - 但是许多人在查看不同的实现时会提到这个“实现快速排序算法”的问题。这取决于您是否限制自己使用特定的规则，或者允许该页面继续成功地作为许多人的学习资源。 - FBryant87

Answer 5

Code Implemented with Iteration With last element as Pivot
<code>https://jsfiddle.net/zishanshaikh/5zxvwoq0/3/    </code>

function quickSort(arr,l,u) {
 if(l>=u)
 {
  return;
 }


var pivot=arr[u];
var pivotCounter=l;
for(let i=l;i<u;i++)
{
    if(arr[i] <pivot )
    {
      var temp= arr[pivotCounter];
      arr[pivotCounter]=arr[i] ;
      arr[i]=temp;
      pivotCounter++;
    }
}


var temp2= arr[pivotCounter];
      arr[pivotCounter]=arr[u] ;
      arr[u]=temp2;


quickSort(arr,pivotCounter+1,u);
quickSort(arr,0,pivotCounter-1);



}

<code>https://jsfiddle.net/zishanshaikh/exL9cdoe/1/</code>

Code With first element as Pivot


//Logic For Quick Sort
function quickSort(arr,l,u) {
 if(l>=u)
 {
  return;
 }


var pivot=arr[l];
var pivotCounter=l+1;
for(let i=l+1;i<u;i++)
{
    if(arr[i] <pivot )
    {
      var temp= arr[pivotCounter];
      arr[pivotCounter]=arr[i] ;
      arr[i]=temp;
      pivotCounter++;
    }
}
var j=pivotCounter-1;
var k=l+1;
while(k<=j)
{
var temp2= arr[k-1];
      arr[k-1]=arr[k] ;
      arr[k]=temp2;
      k++;
      }

      arr[pivotCounter-1]=pivot;




quickSort(arr,pivotCounter,u);
quickSort(arr,0,pivotCounter-2);



}

- zishan shaikh

---

问题是关于作者代码中的“StackOverflowException”的。这个答案并没有以任何方式回答那个问题。 - Peter Duniho

Answer 6

一个简单的快速排序实现。

https://github.com/bharathkumarms/AlgorithmsMadeEasy/blob/master/AlgorithmsMadeEasy/QuickSort.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace AlgorithmsMadeEasy
{
    class QuickSort
    {
        public void QuickSortMethod()
        {
            var input = System.Console.ReadLine();
            string[] sInput = input.Split(' ');
            int[] iInput = Array.ConvertAll(sInput, int.Parse);

            QuickSortNow(iInput, 0, iInput.Length - 1);

            for (int i = 0; i < iInput.Length; i++)
            {
                Console.Write(iInput[i] + " ");
            }

            Console.ReadLine();
        }

        public static void QuickSortNow(int[] iInput, int start, int end)
        {
            if (start < end)
            {
                int pivot = Partition(iInput, start, end);
                QuickSortNow(iInput, start, pivot - 1);
                QuickSortNow(iInput, pivot + 1, end);
            }
        }

        public static int Partition(int[] iInput, int start, int end)
        {
            int pivot = iInput[end];
            int pIndex = start;

            for (int i = start; i < end; i++)
            {
                if (iInput[i] <= pivot)
                {
                    int temp = iInput[i];
                    iInput[i] = iInput[pIndex];
                    iInput[pIndex] = temp;
                    pIndex++;
                }
            }

            int anotherTemp = iInput[pIndex];
            iInput[pIndex] = iInput[end];
            iInput[end] = anotherTemp;
            return pIndex;
        }
    }
}

/*
Sample Input:
6 5 3 2 8

Calling Code:
QuickSort qs = new QuickSort();
qs.QuickSortMethod();
*/

- Bharathkumar V

---

所提出的问题是关于作者代码中的“StackOverflowException”。这个答案并没有以任何方式回答那个问题。 - Peter Duniho

Answer 7

一个简单通用的C#实现快速排序，可以使用第一个或最后一个值或任何其他中间值作为枢轴。

using System;

namespace QuickSort
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] arInt = { 6, 4, 2, 8, 4, 5, 4, 5, 4, 5, 4, 8, 11, 1, 7, 4, 13, 5, 45, -1, 0, -7, 56, 10, 57, 56, 57, 56 };
            GenericQuickSort<int>.QuickSort(arInt, 0, arInt.Length - 1);

            string[] arStr = { "Here", "Is", "A", "Cat", "Really", "Fast", "And", "Clever" };
            GenericQuickSort<string>.QuickSort(arStr, 0, arStr.Length - 1); ;

            Console.WriteLine(String.Join(',', arInt));
            Console.WriteLine(String.Join(',', arStr));

            Console.ReadLine();
        }

    }

    class GenericQuickSort<T> where T : IComparable
    {

        public static void QuickSort(T[] ar, int lBound, int uBound)
        {
            if (lBound < uBound)
            {
                var loc = Partition(ar, lBound, uBound);
                QuickSort(ar, lBound, loc - 1);
                QuickSort(ar, loc + 1, uBound);
            }
        }

        private static int Partition(T[] ar, int lBound, int uBound)
        {
            var start = lBound;
            var end = uBound;

            var pivot = ar[uBound];

            // switch to first value as pivot
            // var pivot = ar[lBound];

            while (start < end)
            {

                while (ar[start].CompareTo(pivot) < 0)
                {
                    start++;
                }

                while (ar[end].CompareTo(pivot) > 0)
                {
                    end--;
                }

                if (start < end)
                {
                    if (ar[start].CompareTo(ar[end]) == 0)
                    {
                        start++;
                    }
                    else
                    {
                        swap(ar, start, end);
                    }
                }
            }

            return end;
        }

        private static void swap(T[] ar, int i, int j)
        {
            var temp = ar[i];
            ar[i] = ar[j];
            ar[j] = temp;
        }
    }
}

输出：

-7，-1，0，1，2，4，4，4，4，4，4，5，5，5，5，6，7，8，8，10，11，13，45，56，56，56，57，57

A，And，Cat，Clever，Fast，Here，Is，Really

这里需要注意的一件重要的事情是，这个优化和简单的代码可以正确处理重复项。我尝试了几个发布的快速排序代码。它们不能为这个（整数数组）输入提供正确的结果，或者只是挂起，例如https://www.w3resource.com/csharp-exercises/searching-and-sorting-algorithm/searching-and-sorting-algorithm-exercise-9.php和http://www.softwareandfinance.com/CSharp/QuickSort_Iterative.html。因此，如果作者也想使用处理重复项的代码，这将是一个很好的参考。

- Arun Kumar

---

所提出的问题是关于作者代码中的“StackOverflowException”。这个答案并没有以任何方式回答那个问题。 - Peter Duniho