20

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

这是算法

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);但是在哪里放置它以便在快速排序完成时打印？

4

7 回答 7

25

您没有正确实现基本情况终止，这导致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);
}
于 2012-11-30T15:36:50.737 回答
16

除了 Deestan 的回答，你也有这个错误：

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

它应该是：

for (int j = low; j < high; j++)
于 2012-11-30T15:49:12.487 回答
1

以防万一您想要一些较短的快速排序代码：

    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 (pivot)。

于 2015-07-07T13:39:44.537 回答
1

这是快速排序算法的最短实现（没有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)));
}
于 2018-08-03T08:14:09.800 回答
0

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

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();
*/
于 2017-02-01T07:09:33.143 回答
0 
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);



}
于 2017-12-01T11:06:48.497 回答
-1

QuickSort 的简单通用 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​​,聪明,快速,Here,Is,真的

这里要注意的一件重要事情是，这个经过优化的简单代码可以正确处理重复项。我尝试了几个发布的快速排序代码。那些没有为此（整数数组）输入提供正确的结果或只是挂起，例如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。因此，如果作者也想使用处理重复的代码，这将是一个很好的参考。

于 2020-05-16T21:36:14.573 回答