在预定义数据上生成近排序列表的算法

本文关键字：排序 列表 算法 预定义 数据 | 更新日期: 2023-09-27 18:05:20

注意:这是一个两部分问题的第一部分。

这里的第二部分

我想更多地了解排序算法，还有什么比编码更好的方法呢?所以我想我需要一些数据来处理。

我创建一些"标准"数据的方法如下:创建一组项目，不确定要多大，但我想玩得开心，让我的电脑发出一点呻吟:D

一旦我有了这个列表，我将把它推送到一个文本文件中，然后读取它来运行我的算法。我应该有总共4个文本文件填充相同的数据，但只是排序不同运行我的算法(见下文)。

纠正我，如果我错了，但我相信我需要4种不同类型的场景来配置我的算法。

  • 随机排序的数据(为此我将使用knuth shuffle)
  • 反向数据(足够容易)
  • 几乎排序(不确定如何实现这一点)
  • 少数独特的(再次不确定如何处理这个)

这个问题用于生成一个几乎排序的列表。

哪种方法最适合在预定义数据上生成接近排序的列表?

在预定义数据上生成近排序列表的算法

对已排序的列表进行"洗牌"，使其"几乎已排序":

  1. 创建一个可以应用于数组部分的函数列表，如:

    Negate(array, startIndex, endIndex);
    Reverse(array, startIndex, endIndex);
    Swap(array, startIndex, endIndex);

  2. 对于i从0到数组长度的某个函数(例如Log(array.Length):

    )
    1. 随机选择2个整数*
    2. 从你想到的函数中随机选择一个
    3. 将该函数应用于数组
      4. 的索引

*注意:整数不能限制为数组大小。相反，选择随机整数并将数组"换行"——这样，靠近末尾的元素将有与中间元素相同的被修改的机会。

回答我自己的问题。它所做的就是取一个排序过的列表，然后对其中的一小部分进行洗牌。

    public static T[] ShuffleBagSort<T>(T[] array, int shuffleSize)
    {
        Random r = _random;
        for (int i = 0; i < array.Length; i += shuffleSize)
        {
            //Prevents us from getting index out of bounds, while still getting a shuffle of the 
            //last set of un shuffled array, but breaks for loop if the number of unshuffled array is 1
            if (i + shuffleSize > array.Length)
            {
                shuffleSize = array.Length - i;
                if (shuffleSize <= 1) // should never be less than 1, don't think that's possible lol
                    continue;
            }
            if (i % shuffleSize == 0)
            {
                for (int j = i; j < i + shuffleSize; j++)
                {
                    // Pick random element to swap from our small section of the array.
                    int k = r.Next(i, i + shuffleSize);
                    // Swap.
                    T tmp = array[k];
                    array[k] = array[j];
                    array[j] = tmp;
                }
            }
        }
        return array;
    }
  1. 排序数组
  2. 开始用冒泡排序按降序排序
  3. 在几次迭代后停止(取决于您希望数组的"无序"程度)
  4. 增加一些随机性(每次当bubblesort想要交换两个元素扔硬币并执行该操作或不依赖于结果时，或使用不同于50/50的概率)

这将给你一个数组，它将在其整个范围内大致相等地修改，保留大部分顺序(开始将保存最小的元素，结束将保存最大的元素)。这是因为使用随机测试的bubblesort执行的更改将是相当局部的。它不会一次混合整个数组，这样它就不会像原来的数组。

如果你愿意，你也可以完全随机地洗牌数组的整个部分(但保持部分不要太大，因为，你会完全失去排序)。

或者您也可以随机交换数组的整个排序部分。这将是一个有趣的测试用例，例如:

[1,2,3,4,5,6,7,8] -> [1,2,6,7,8,3,4,5]

几乎排序的列表是Timsort (python)在现实世界中如此高效的原因，因为数据通常"几乎排序"。有一篇文章解释了数据熵背后的数学原理。

相关文章：