快速排序不能正确排序 [英] Quicksort not sorting correctly

问题描述

试图从做快速排序的实现学习，我不能找出为什么它不排序正确。

使用这个序列：

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

它返回这样的：

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

这似乎有点排序，但不是全部。有什么我错过了

下面是我的代码：

 静态无效主要（字串[] args）
 {
快速排序QS =新的快速排序（）; 
 
 INT [] =改编新INT [] {6，7，12，5，9，8，65，3}; 
 
的foreach（中间体升的ARR）
 {
 Console.Write（L +，）; 
} 
 
 INT左边= 0; 
 INT右= arr.Count（） -  1; 
 
 INT [] = arrr qs.DoQuickSort（REF改编，左，右）; 
 Console.WriteLine（排序清单：）; 
的foreach（INT我arrr）
 {
 Console.Write（1 +）; 
} 
 
 
 
到Console.ReadLine（）; 
} 
 
公众诠释分区（INT []数组，诠释左，右INT，INT PivotIndex）
 {
 INT pivValue =阵列[PivotIndex] 
 
阵列=交换（REF阵列，PivotIndex，右）; 
 
 INT storeIndex =左; 
 
的for（int i = PivotIndex; I<右1;我++）
 {
如果（阵列[1]  -  = pivValue）
 {
 =阵列交换（REF阵，我，storeIndex）; 
 storeIndex = storeIndex + 1; 
} 
} 
 
阵列=交换（REF阵列，storeIndex，右）; 
 
返回storeIndex; 
} 
 
公众诠释[]互换（参考INT []编曲，诠释第一，诠释秒）
 {
 INT TEMP = ARR [首页]; 
 ARR [首页] = ARR [秒]; 
 ARR [秒] =温度; 
 
返回编曲; 
} 
 
公众诠释[] DoQuickSort（参考INT []数组，诠释左，诠释右）
 {
如果（右GT;左）
 {
 INT PivIndex =（左+右）/ 2; 
 INT newPivIndex =分区（数组，左，右，PivIndex）; 
 DoQuickSort（参考阵列，左，newPivIndex  -  1）; 
 DoQuickSort（REF阵列，newPivIndex + 1，右）; 
} 
 
返回数组; 
} 
  

解决方案

在除了我的评论这个问题本身，我想指出的是，切换（）和 DoQuickSort（）方法并不需要返回数组（按我在这也解释了该数组是一个参考本身的注释注）。为此，你的代码做的工作应该是这样的：

 公众诠释分区（INT []数组，INT左，右INT，INT pivotIndex）
 {
 INT pivValue =阵列[pivotIndex] 
 
互换（数组，pivotIndex，右）; 
 
 INT storeIndex =左; 
 
的for（int i =左; I<权利;我++）
 {
如果（阵列[1]  -  = pivValue）
 {
交换（数组，我，storeIndex）; 
 storeIndex = storeIndex + 1; 
} 
} 
 
互换（数组，storeIndex，右）; 
 
返回storeIndex; 
} 
 
公共无效掉期（INT []编曲，诠释第一，诠释秒）
 {
 INT TEMP = ARR [首页]; 
 ARR [首页] = ARR [秒]; 
 ARR [秒] =温度; 
} 
 
公共无效DoQuickSort（INT []数组，诠释左，诠释右）
 {
如果（右GT;左）
 {
 INT pivIndex =（左+右）/ 2; 
 INT newPivIndex =分区（数组，左，右，pivIndex）; 
 DoQuickSort（阵，左，newPivIndex  -  1）; 
 DoQuickSort（数组，newPivIndex + 1，右）; 
} 
} 
  

Attempting to learn from doing an implementation of Quicksort, I cannot find out why it's not sorting properly.

Using this sequence:

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

It returns this:

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

It seems to sort somewhat, but not all. What have I missed?

Here's my code:

 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] <= pivValue)
        {
            array = Swap(ref array, i, storeIndex);
            storeIndex = storeIndex + 1;
        }
    }

    array = Swap(ref array, storeIndex, right);

    return storeIndex;
}

public int[] Swap(ref int[] arr, int first, int second)
{
    int temp = arr[first];
    arr[first] = arr[second];
    arr[second] = temp;

    return arr;
}

public int[] DoQuickSort(ref int[] array, int left, int right)
{
    if (right > 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;
}

解决方案

In addition to my comment on the question itself, I wanted to point out that the Swap() and DoQuickSort() methods do not need to return the array (as per my note in the comment which explains that the array is a reference itself). To that end, your code to do the job should look like the following:

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);
    }
}

这篇关于快速排序不能正确排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！