按排序顺序将元素插入数组

Question

我想做的是当我从用户那里获取输入时，将该输入按排序顺序插入到数组中，例如。用户输入 22,3,9,10,33
输出将是：3,9,10,22,33。

除了最后添加的元素索引错误之外，我下面的代码可以正常工作。这是对学校的测试（这就是为什么数组有 50 个元素大，并且整个 class 带有 getter 和 setter 并且缺少错误检查）我想看看我哪里出错了，我我试过插入排序和选择排序都产生了这个结果。按照我的理解，应该是45个连续的零，然后是我的元素升序排列。

例如）这是我得到的输出（无论我在调用打印方法后使用选择排序还是插入排序

排序数组：0 0 0 0 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 9 10 22

 public class test
{
    private int [] arr;
    private int maxSize;
    private int numItems;
    public test(int maxSize)
    {
        this.maxSize = maxSize;
        numItems = 0;
        arr = new int[maxSize];
    }

    public bool addItem(int key)
    {
        if (numItems < maxSize)
        {
            selectionSort(key);
            arr[numItems] = key;
            numItems++;
            return true;
        }
        return false;
    }

    public bool insertionSort(int key)
    {
        int n = arr.Length - 1;
        for (int i = 1; i < n; i++)
        {
            key = arr[i];
            int j = i - 1;
            while(j>=0 && arr[j] > key)
            {
                arr[j+1] = arr[j];
                j --;
            }
            arr[j + 1] = key;
        }
        return true;
    }

    public bool selectionSort(int key)
    {
        int  n = arr.Length - 1;
        for (int i = 0; i < n; i++)
        {
            key = i;
            for(int j = i + 1; j < n; j++)
            {
                if (arr[j] < arr[key])
                {
                    key = j;
                }
            }
            int temp = arr[key];
            arr[key] = arr[i];
            arr[i] = temp;

        }
        return true;
    }    

         static void Main(string[] args)
    {

        test x = new test(50);

        int count = 0;
        int element;
        while (count < 5)
        {
            Console.WriteLine("Enter an element to add into the array");
            element = Convert.ToInt32(Console.ReadLine());
            x.addItem(element);
            count++;
        }}

Answer 1

我想你正在寻找插入排序，这里是一个例子。

   static void Main(string[] args)
    {
        int[] numbers = new int[10] {22,1,34,20,12,10,5,33,11,5};
        Console.WriteLine("\nOriginal Array Elements :");
        Show(numbers);
        Console.WriteLine("\nSorted Array Elements :");
        Show(InsertionSort(numbers));
        Console.ReadKey();
        }

    static int[] InsertionSort(int[] inputArray)
    {
        for (int i = 0; i < inputArray.Length - 1; i++)
        {
            for (int j = i + 1; j > 0; j--)
            {
                if (inputArray[j - 1] > inputArray[j])
                {
                    int temp = inputArray[j - 1];
                    inputArray[j - 1] = inputArray[j];
                    inputArray[j] = temp;
                }
              }
        }
        return inputArray;         
    }
    public static void Show(int[] array)
    {
        foreach (int i in array)
        {
            Console.Write(i.ToString() + "  ");
        }
     }

Answer 2

我发现您的代码有两个问题，而且这些问题都很小。

更新 addItem 函数以将 selectionSort 移动到赋值操作下方。

    public bool addItem(int key)
    {
        if (numItems < maxSize)
        {
            arr[numItems] = key;
            selectionSort(key);  // below the arr[numItems] assignment.
            numItems++;
            return true;
        }
        return false;
    }

并在 selectionSort 方法中，更改两件事。

一个。 for 循环 for j 应该一直到 n 和

b。在 k=j;

        public bool selectionSort(int key)
    {
        int n = arr.Length - 1;
        for (int i = 0; i < n; i++)
        {
            key = i;
            for (int j = i + 1; j <= n; j++) // <= n instead of < n
            {
                if (arr[j] < arr[key])
                {
                    key = j;
                    break;             // break here once you have k = j.
                }
            }
            int temp = arr[key];
            arr[key] = arr[i];
            arr[i] = temp;

        }
        return true;
    }

这应该可以解决您的问题。

按排序顺序将元素插入数组

Insert elements into an array in sorted order

c#

arrays

sorting

mergesort

insertion-sort