1

目前我有一个整数列表。此列表包含指向另一个更大列表中的“活动”对象的索引值。如果较小的“活动”值列表变得太大，它会触发一个循环，该循环遍历小列表并删除已变为非活动的值。目前，它通过简单地忽略非活动值并将它们添加到第二个列表来删除它们（当第二个列表再次变满时，重复相同的过程，将它们放回第一个列表等等）。

发生此触发器后，然后使用快速排序实现对列表进行排序。这一切都很好，花花公子。

- - - -问题 - - - - -

但是，我看到了速度的潜在增益。我想象在进行排序时结合删除非活动值。不幸的是，我找不到以这种方式实现快速排序的方法。仅仅因为快速排序与枢轴一起使用，这意味着如果从列表中删除值，枢轴最终将尝试访问列表中不存在的插槽等。（除非我只是想错了） .

那么，关于如何将这两种操作结合​​起来的任何想法？我似乎找不到任何可以处理这个问题的快速排序算法，或者我只是没有看到如何将它实现为快速排序......任何提示都表示赞赏！

更好地了解当前情况的代码：（当前条件：值的范围可以从 0 到 200 万，没有两个值是相同的，并且通常它们大多是排序的，因为它们经常排序）

if (deactive > 50000)//if the number of inactive coordinates is greater than 50k
{
    for (int i = 0; i < activeCoords1.Count; i++)
    {
         if (largeArray[activeCoords[i]].active == true)//if coordinate is active, readd to list
         {
             activeCoords2.Add(activeCoords1[i]);
         }
    }
    //clears the old list for future use
    activeCoords1.Clear();
    deactive = 0;
    //sorts the new list
    Quicksort(activeCoords2, 0, activeCoords2.Count() - 1);
 }    

    static void Quicksort(List<int> elements, int left, int right)
    {
        int i = left, j = right;
        int pivot = elements[(left + right) / 2];

        while (i <= j)
        {
            // p < pivot
            while (elements[i].CompareTo(pivot) < 0)
            {
                i++;
            }

            while (elements[j].CompareTo(pivot) > 0)
            {
                j--;
            }

            if (i <= j)
            {
                // Swap
                int tmp = elements[i];
                elements[i] = elements[j];
                elements[j] = tmp;

                i++;
                j--;
            }
        }

        // Recursive calls
        if (left < j)
        {
            Quicksort(elements, elements, left, j);
        }

        if (i < right)
        {
            Quicksort(elements, elements, i, right);
        }
    }
4

2 回答 2

1

听起来您可能会从使用红黑树（或其他平衡二叉树）中受益，您的搜索、插入和删除时间将是 O(log n)。这棵树将始终被排序，因此不会有任何人因大命中而重新排序。

您在访问类型（搜索、插入、删除）方面的划分是什么？您的访问限制是什么？

于 2013-05-04T07:26:08.560 回答
1

我会使用 aList<T>或 aSortedDictionary<TKey, TValue>作为您的数据结构。

由于您进行排序的原因（“基于感觉的微优化”）不是一个好的原因，我会避免这样做。一个很好的理由是“它对性能有可衡量的影响”。

在那种情况下（或者你只是想这样做），我推荐一个 SortedDictionary。所有的分类工作都已经为你完成了，没有理由重新发明轮子。

如果一个合适的数据结构就足够了，就不需要同时处理两个列表。红黑树似乎是合适的，并且显然根据此在 SortedDictionary 中使用

于 2013-05-04T16:31:55.403 回答