时间戳

首页 > 解决方案 > 使用 C# 将我的迭代选择排序更改为递归排序

c# - 使用 C# 将我的迭代选择排序更改为递归排序

问题描述

我尝试将我的排序更改为方法调用自身的递归函数。至少这是我对递归到 foregofor循环的理解，并且该方法调用自身来重复必要的迭代。

下面是我的迭代版本：

for (int i = 0; i < Integers.Count; i++) //loops through all the numbers
{
    min = i; //setting the current index number to be the minimum

    for (int index = i + 1; index < Integers.Count; index++) //finds and checks pos of min value 
    {                                                        //and switches it with last element using the swap method
        if ((int) Integers[index] > (int) Integers[min]) {
            min = index;
        }
        comparisons++;
    }
    if (i != min) //if statement for if swop is done
    {
        Swap(i, min, Integers, ref swops); //swap method called
    }
    //Swap method called
}

我试过让它递归。我在网上读到，for在递归函数中仍然有循环是可以的，我猜这不是真的。我只是无法开发一种工作方式。我是否需要将方法拆分为 2，其中一种方法遍历列表，另一种方法进行排序？

下面是我的选择排序递归方法尝试：

static void DoSelectionSortRecursive(ArrayList Integers, int i, int swops, int comparisons) {

    int min;
    min = i;
    for (int index = i + 1; index < Integers.Count; index++) //read online that the use of arraylists are deprecated, and i shoudlve rather used List<int> in order to remedy the code. is it necassary 
    {

        if ((int) Integers[index] > (int) Integers[min]) {
            min = index;
        }
        comparisons++;
    }
    if (i != min) {
        Swap(i, min, Integers, ref swops);
    }
    DoSelectionSortRecursive(Integers, (i + 1), comparisons, swops); //DoSelectionSortRecursive method called 
}

这是我改进的尝试，包括性能指标和一切。未排序列表中的原始整数列表。84,24,13,10,37。
我得到 84,24,13,37,10。显然不是按降序排列的。下面是改进后的代码

static void DoSelectionSortRecursive(ArrayList Integers)
    {

        Stopwatch timer = new Stopwatch();
        timer.Start();
        int shifts = 0;
        int swops = 0;
        int comparisons = 0;

        Sort(Integers, 1,ref swops,ref comparisons);   

        timer.Stop();
        Console.WriteLine("Selection Sort Recursive: ");
        Console.WriteLine(timer.ElapsedMilliseconds);
        Console.WriteLine(swops);
        Console.WriteLine(comparisons);
        Console.WriteLine(shifts);      //not needed in this sort
        Console.WriteLine("-------------------------------------");
        foreach (int i in Integers)
        {
            Console.WriteLine(i);
        }

    }

    static void Sort(ArrayList Integers, int i, ref int swops, ref int comparisons)
    {
        int min = i;
        int index = i + 1;
        if (index < Integers.Count)        //read online that the use of arraylists are deprecated, and i shoudlve rather used List<int> in order to remedy the code. is it necassary 
        {

            if ((int)Integers[index] > (int)Integers[min])
            {
                min = index;
            }
            comparisons++;
            index++;
        }
        if (i != min)
        {
            Swap(i, min, Integers, ref swops);
        }
        if (i < Integers.Count - 1)
        {
            Sort(Integers, (i + 1), ref comparisons, ref swops);     //DoSelectionSortRecursive method called 
        }

    }

 static void Swap(int x, int y, ArrayList Integers, ref int swap)      //swap method, swaps the position of 2 elements
    {
        swap++;
        int temporary = (int)Integers[x];                   //essentially will swap the min with the current position
        Integers[x] = Integers[y];
        Integers[y] = temporary;
    }

标签： c#sortingrecursion

解决方案

没有关于递归的“规则”说你不能在递归方法体中使用循环。递归的唯一规则是函数必须调用自身，您的第二个代码片段会这样做，因此DoSelectionSortRecursive是合法的递归。

例如，归并排序使用递归来拆分数组，使用循环来合并已排序的子数组。除了递归函数之外，将其称为任何东西都是错误的，递归地实现合并阶段（合并排序的实现细节）有点愚蠢——它会更慢更难推理，所以循环是自然的选择。

另一方面，归并排序的拆分部分对于递归编写是有意义的，因为它通过对数因子将问题空间切碎并且具有多个分支。重复减半意味着它不需要对一个典型的数组进行多次或十几个递归调用。这些调用不会产生太多开销，并且非常适合调用堆栈。

另一方面，对于没有尾调用优化（如 C# ）的语言中的线性递归算法，调用堆栈很容易崩溃，其中线性结构中的每个索引都需要整个堆栈帧。

禁止循环的规则是由试图通过强迫您在解决方案中使用特定方法来教授递归的教育工作者制定的。就课程而言，是否需要将一个或两个循环转换为递归以使其“计数”取决于您的教师。（抱歉，如果我对您的教育安排的假设不正确）

也就是说，递归编写嵌套循环排序的要求基本上是出于教学目的而误用递归。在“现实世界”中，您只需迭代地编写它并完成它，就像谷歌在 V8 JavaScript 引擎中所做的那样，它在小数组上使用插入排序。我怀疑还有很多其他案例，但这是我最熟悉的案例。

在性能敏感的生产代码中使用简单的嵌套循环排序的关键在于它们不是递归的。这些排序的优点是它们避免了分配堆栈帧和产生函数调用开销来对十几个数字的小数组进行排序，其中二次时间复杂度不是一个重要因素。当数组大部分被排序时，插入排序尤其不需要做太多工作，并且主要是对数组的线性遍历（有时在某些需要可预测性能的实时应用程序中是一个缺点，在这种情况下，选择排序可能是更可取——参见维基百科）。

关于ArrayLists，文档说：“我们不建议您使用ArrayList该类进行新开发。相反，我们建议您使用泛型List<T>类。” 所以你基本上可以忘记，ArrayList除非你正在做遗留代码（注意：Java确实使用ArrayList更类似于 C# 的 s List。std::list它不是 C++ 中的数组，所以保持所有这些都直截了当可能会令人困惑）。

值得称赞的是，您首先迭代地编写了排序，然后仅在外循环上转换为递归。最好从你所知道的开始，让一些东西发挥作用，然后逐渐对其进行改造以满足新的要求。

缩小一点，我们可以隔离这个内部循环在我们将其作为函数拉出时所起的作用，然后独立于我们希望使用它的选择排序来编写和测试它。在子程序自己工作之后，然后选择sort 可以将其用作黑盒，整体设计是可验证的和模块化的。

更具体地说，这个内部循环的作用是找到从索引开始的最小值：int IndexOfMin(List<int> lst, int i = 0)。合同规定，如果违反前提条件，它将引发ArgumentOutOfRangeException错误。0 <= i < lst.Count

为简单起见，我跳过了指标变量，但添加了一个随机测试工具，可以对内置排序进行相当合理的验证。

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

class Sorter
{
    private static void Swap(List<int> lst, int i, int j)
    {
        int temp = lst[i];
        lst[i] = lst[j];
        lst[j] = temp;
    }

    private static int IndexOfMin(List<int> lst, int i = 0)
    {
        if (i < 0 || i >= lst.Count)
        {
            throw new ArgumentOutOfRangeException();
        }
        else if (i == lst.Count - 1)
        {
            return i;
        }

        int bestIndex = IndexOfMin(lst, i + 1);
        return lst[bestIndex] < lst[i] ? bestIndex : i;
    }
    
    public static void SelectionSort(List<int> lst, int i = 0)
    {
        if (i < lst.Count)
        {
            Swap(lst, i, IndexOfMin(lst, i));
            SelectionSort(lst, i + 1);
        }
    }

    public static void Main(string[] args) 
    {
        var rand = new Random();
        int tests = 1000;
        int lstSize = 100;
        int randMax = 1000;

        for (int i = 0; i < tests; i++)
        {
            var lst = new List<int>();

            for (int j = 0; j < lstSize; j++)
            {
                lst.Add(rand.Next(randMax));
            }

            var actual = new List<int>(lst);
            SelectionSort(actual);
            lst.Sort();

            if (!lst.SequenceEqual(actual))
            {
                Console.WriteLine("FAIL:");
                Console.WriteLine($"Expected => {String.Join(",", lst)}");
                Console.WriteLine($"Actual   => {String.Join(",", actual)}\n");
            }
        }
    }
}

这是一个使用泛型的更通用的解决方案，CompareTo因此您可以对实现IComparable接口的任何对象列表进行排序。此功能更类似于内置排序。

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

class Sorter
{
    public static void Swap<T>(List<T> lst, int i, int j)
    {
        T temp = lst[i];
        lst[i] = lst[j];
        lst[j] = temp;
    }

    public static int IndexOfMin<T>(List<T> lst, int i = 0)
        where T : IComparable<T>
    {
        if (i < 0 || i >= lst.Count)
        {
            throw new ArgumentOutOfRangeException();
        }
        else if (i == lst.Count - 1)
        {
            return i;
        }

        int bestIndex = IndexOfMin(lst, i + 1);
        return lst[bestIndex].CompareTo(lst[i]) < 0 ? bestIndex : i;
    }
    
    public static void SelectionSort<T>(List<T> lst, int i = 0)
        where T : IComparable<T>
    {
        if (i < lst.Count)
        {
            Swap(lst, i, IndexOfMin(lst, i));
            SelectionSort(lst, i + 1);
        }
    }

    public static void Main(string[] args) 
    {
        // same as above
    }
}

由于您询问如何将两个递归函数合并为一个，因此可以通过跟踪参数列表中的i和j索引并添加一个分支来确定是处理帧上的内部循环还是外部循环。例如：

public static void SelectionSort<T>(
    List<T> lst, 
    int i = 0, 
    int j = 0, 
    int minJ = 0
) where T : IComparable<T>
{
    if (i >= lst.Count)
    {
        return;
    }
    else if (j < lst.Count)
    {
        minJ = lst[minJ].CompareTo(lst[j]) < 0 ? minJ : j;
        SelectionSort(lst, i, j + 1, minJ);
    }
    else
    {
        Swap(lst, i, minJ);
        SelectionSort(lst, i + 1, i + 1, i + 1);
    }
}

这篇文章中显示的所有代码都不适合生产——重点是说明什么不该做。

推荐阅读