Перемешать с помощью IComparer

Я был несколько удивлен в этом потоке, сколько неправильных ответов было отправлено. Только ради других, которые предлагают решение, подобное тому, отправленному OP, следующие корректные взгляды кода:

int[] nums = new int[1000];
for (int i = 0; i < nums.Length; i++)
{
    nums[i] = i;
}

Random r = new Random();
Array.Sort<int>(nums, (x, y) => r.Next(-1, 2));

foreach(var num in nums)
{
    Console.Write("{0} ", num);
}

Однако код будет иногда выдавать исключение, но не всегда. Это - то, что делает забавой отладить :) Если Вы выполните его достаточно раз или выполните процедуру вида в цикле приблизительно 50 раз, то Вы получите ошибку при утверждении:

IComparer (or the IComparable methods it relies upon) did not return zero when Array.Sort called x. CompareTo(x). x: '0' x's type: 'Int32' The IComparer: ''.

Другими словами, быстрая сортировка сравнила некоторое число x к себе и получил ненулевой результат. Очевидным решением кода была бы запись:

Array.Sort<int>(nums, (x, y) =>
    {
        if (x == y) return 0;
        else return r.NextDouble() < 0.5 ? 1 : -1;
    });

Но даже это не работает, потому что существуют случаи, где.NET сравнивает 3 числа друг с другом, который возвращает непоследовательные результаты, такие как A> B, B> C, и C> (ой!). Неважно, при использовании Гуида, GetHashCode, или какого-либо другого случайным образом сгенерированного входа, решения как, один показанный выше является все еще неправильным.

Так как это сказан, Фишер-Йетс является стандартным способом переставить массивы, таким образом, нет никакой настоящей причины для использования IComparer во-первых. Фишер-Йетс является O (n), тогда как любая реализация с помощью IComparer использует quicksort behinds сцены, который имеет временную сложность O (n, регистрируют n). Нет только никакого серьезного основания не использовать известный, эффективный, стандартный алгоритм для решения этого вида проблемы.

Однако, если Вы действительно настаиваете на том, чтобы использовать IComparer и рэнд, затем применяете свои случайные данные перед сортировкой. Это требует проекции данных на другой объект, таким образом, Вы не теряете свои случайные данные:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Pair<T, U>
    {
        public T Item1 { get; private set; }
        public U Item2 { get; private set; }
        public Pair(T item1, U item2)
        {
            this.Item1 = item1;
            this.Item2 = item2;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Pair<int, double>[] nums = new Pair<int, double>[1000];
            Random r = new Random();
            for (int i = 0; i < nums.Length; i++)
            {
                nums[i] = new Pair<int, double>(i, r.NextDouble());
            }

            Array.Sort<Pair<int, double>>(nums, (x, y) => x.Item2.CompareTo(y.Item2));

            foreach (var item in nums)
            {
                Console.Write("{0} ", item.Item1);
            }

            Console.ReadKey(true);
        }
    }
}

Или получите LINQy со своим плохим сам:

Random r = new Random();
var nums = from x in Enumerable.Range(0, 1000)
           orderby r.NextDouble()
           select x;

IComparer требование нулевого возврата в какой-то момент (для равных экземпляров T), делает математически невозможным создать универсальный IComparer, который будет подражать Перестановке Фишера-Йетса статистически. Всегда будет предвзятость. Для реальной перестановки Вы никогда не хотели бы вынуждать это возвратить какое-то конкретное значение.

Как насчет того, чтобы сортировать на основе скрытого поля, которое предписано случайное значение?

Следовать идее James Curran: позвольте IComparer поддержать "отсортированные" значения как список; если новое значение происходит, вставьте его в список в случайном положении; сравните индексом списка. Оптимизируйте путем ведения списка как сбалансированного дерева или чего-то. Каждый экземпляр такого IComparer поддержит последовательный и случайный порядок сортировки, таким образом, у Вас будет выбор разрешения Вашей Случайной сортировке последовательно быть тем же случайным упорядочиванием или другим каждый раз. Незначительная модификация даже позволит равным элементам быть "отсортированными" в различные положения упорядочивания, если Вы предпочтете читать "случайный" тот путь.

Интересное усилие. Скорее всего, неправильное употребление/злоупотребление IComparer.

Вы пытаетесь сделать случайный взвешенный вид при помощи механизма, который не был создан с этой целью.

Почему бы не реализовать Вашу собственную программу сортировки и Ваш собственный компаратор? У меня есть чувство, что даже, который был бы недостаточен.

Не делайте этого.

Все алгоритмы, предложенные к настоящему времени, вводят своего рода предвзятость в вывод (некоторые больше, чем другие).

@Princess и @Luke предлагают хранить случайное число вместе с данными. Однако, потому что существует возможность, что любые два из этих случайных чисел могли иметь то же значение, как другой, порядок сортировки между теми двумя объектами будет детерминировано смещен

Худший случай для этого был бы то, если программа сортировки "стабильна" (который является, который возражает, что считаются равными, всегда производятся в том же порядке, они были введены в). Массив. Вид, оказывается, не стабилен (он использует QuickSort внутренне), но существует все еще предвзятость, которая происходит каждый раз, когда два объекта имеют то же значение, которое зависит от того, где они находятся во входе (и конкретно где они относительно центра QuickSort).

Когда ключевое пространство для этого случайного числа увеличивается, вероятность коллизии понижается (с хорошим источником случайности), но имейте в виду, что, поскольку количество значений, которые Вы сортируете, повышается, парадокс дня рождения диктует, что вероятность по крайней мере одной пары среди них столкновение повышается очень быстро.

Для целочисленного ключа, существуют 2^32 уникальные значения для ключа и даже предполагая, что существует совершенно ровное распределение случайных значений с 75 000 строк, существует 50%-я вероятность, что будет коллизия. Википедия.

Криптографический подход хеша, который Вы предложили потенциально, имеет достаточно большое ключевое пространство (160) биты для создания шанса коллизии незначительным, но алгоритм разлагается, вся та случайность отступает к единственному интервалу прежде на самом деле сделать сравнивание, которое инвертирует преимущество того большего ключевого пространства.

Ваш лучший подход должен связаться, отличное значение "порядка сортировки" с каждым из Ваших элементов данных переставляют эти значения с помощью проверенного алгоритма и затем заказывают результаты тем значением.

Если Вы используете Массив. Вид, существует перегрузка, которая берет массив "ключей" и массив "значений". Массив ключей обычно сортируется, но каждый раз, когда значение в массиве ключей перемещено, соответствующая запись в массиве значений также перемещена.

Что-то как:

Something[] data;//populated somewhere
int[] keys = new int[data.Length];//or long if you might have lots of data
for(int i=0;i<keys.Length;++i) {
 keys[i] = i;
}

Shuffle(keys);

Array.Sort(keys, data);