如何将int快速插入排序数组?

我将使用长度为35的int数组(因为您说的范围是1-34)来记录数字的状态。

int[] status = Enumerable.Repeat(0, 35).ToArray(); 
//an array contains 35 zeros
//which means currently there is no elements in the array
status[10] = 1;  // now the array have only one number: 10
status[11] ++;   // a new number 11 is added to the list

所以如果你想在列表中添加一个数字i:

status[i]++;  // O(1) to add a number

要从列表中删除i:

status[i]--;   // O(1) to remove a number

想知道名单上所有的数字吗?

    for (int i = 0; i < status.Length; i++)
    {
        if (status[i] > 0)
        {
            for (int j = 0; j < status[i]; j++)
                Console.WriteLine(i);
        }
    }
    //or more easier using LINQ
    var result = status.SelectMany((i, index) => Enumerable.Repeat(index, i));

下面的示例可以帮助您更好地理解我的代码:

the real number array: 1 12 12 15 9 34 // i don't care if it's sorted
the status array: status[1]=1,status[12]=2,status[15]=1,status[9]=1,status[34]=1
                  all others are 0

在14个值的情况下,这是一个非常小的数组,我不认为切换到更智能的数据结构(如列表)将为您赢得多少好处,特别是如果您快速进行良好的随机访问。在这种规模下,即使是二进制搜索也可能比线性搜索慢。您确定,例如,在副本上插入不满足您的性能要求吗?

这个手术要经常进行,所以需要尽可能快。

你注意到的“经常”发生的事情 不 程序中的瓶颈-通常令人惊讶的是实际的瓶颈是什么。在执行任何优化之前,您应该编写一些简单的代码并测量程序的实际性能。

我在想很多不同的方法,包括二进制搜索和简单的拷贝插入,但发现很难决定。

假设这是瓶颈,不同方法的big-O性能在这里将不相关,因为数组的大小很小。只需尝试几种不同的方法,测量结果,看看哪种方法表现最好,然后选择这种方法就更容易了。如果您已经遵循了第一段中的建议,那么您已经有了一个profiler设置,也可以用于此步骤。

在中间插入一个 LinkedList<int> 这将是最快的选择-任何其他涉及复制数据。对于14个元素,不要过分强调二进制搜索等-只要向前走到您想要的项目:

using System;
using System.Collections.Generic;
static class Program
{
    static void Main()
    {

        LinkedList<int> data = new LinkedList<int>();
        Random rand = new Random(12345);
        for (int i = 0; i < 20; i++)
        {
            data.InsertSortedValue(rand.Next(300));
        }
        foreach (int i in data) Console.WriteLine(i);
    }
}
static class LinkedListExtensions {
    public static void InsertSortedValue(this LinkedList<int> list, int value)
    {
        LinkedListNode<int> node = list.First, next;
        if (node == null || node.Value > value)
        {
            list.AddFirst(value);
        }
        else
        { 
            while ((next = node.Next) != null && next.Value < value)
                node = next;
            list.AddAfter(node, value);
        }
    }
}

使用蛮力方法是最好的选择,因为14不是一个数字:)。然而,这并不是一个可扩展的决定,因为14日有一天会变成14000日,这将导致问题

你的数组最常用的操作是什么? 插入?阅读?

• 堆数据结构将为它们提供O(日志(14))。SortedDictionary可能会影响您的性能。
• 使用一个简单的数组可以得到O(1)用于读取,O(14)用于插入。

顺便问一下,你试过System.Collections.Generic.SortedDictionary ot System.Collections.Generic.SortedList吗?

如果你在.Net 4上,你应该看看 SortedSet<T> . 否则看看 SortedDictionary<TKey, TValue> 你在哪里做的 TValue 作为 object 然后把 null 因为你只是对钥匙感兴趣。

如果数组中没有重复的值,并且可能的值不会改变,那么使用一个固定大小的数组,其中的值等于索引是一个不错的选择

插入和读取都是O(1)

你有一个从1到34的可能值范围,这是相当窄的。所以最快的方法可能是使用一个有34个插槽的阵列。要插入数字n,只需执行数组[n-1]++并将其删除,请执行数组[n.1]--(如果n>0)。

若要检查集合中是否存在值,请执行数组[n-1 ] & gt;0。

编辑 :该死……丹尼跑得更快。:)

写一个方法获取一个整数数组,并使用冒泡排序将它们排序到位。不允许该方法创建任何其他数组。冒泡排序是一种简单的排序算法,它通过循环遍历要排序的数组,比较每对相邻元素,如果它们的顺序不对,则进行交换。