算法生成近排序名单上predefined数据 [英] Algorithm for generating a nearly sorted list on predefined data

问题描述

注：这是一个2部分的问题第1部分

Note: This is part 1 of a 2 part question.

这里第2部分

我想更多的排序算法什么更好的方式做比再code！所以，我想我需要一些数据的工作。

I'm wanting to more about sorting algorithms and what better way to do than then to code! So I figure I need some data to work with.

我的方法来创建一些标准的数据如下：创建项目的定数，不知道如何大做，但我想有乐趣，让我的电脑捞到一点点：D

My approach to creating some "standard" data will be as follows: create a set number of items, not sure how large to make it but I want to have fun and make my computer groan a little bit :D

在我有一个名单，我将它推到一个文本文件中，只是读出，要对运行我的算法。我应该有一个总的填充相同的数据4个文本文件，但只是排序不同运行我的算法对（见下文）。

Once I have that list, I'll push it into a text file and just read off that to run my algorithms against. I should have a total of 4 text files filled with the same data but just sorted differently to run my algorithms against (see below).

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

Correct me if I'm wrong but I believe I need 4 different types of scenarios to profile my algorithms.

• 在随机排序的数据（这个我会用克努特洗牌）
• 在反向数据（很容易）
• 在近排序（不知道如何实现这一点）
• 在一些独特的（再一次不知道如何处理这一点）

这个问题是产生近排序列表。

This question is for generating a nearly sorted list.

哪种方法是最好的生成predefined数据的近排序列表？

Which approach is best to generate a nearly sorted list on predefined data?

推荐答案

在这里回答我的问题。所有这一切都不会走的是一条排序列表和洗牌它的小部分。

Answering my own question here. All this does is taking a sorted list and shuffling up small sections of it.

    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;
    }

这篇关于算法生成近排序名单上predefined数据的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！