Выдать массив в случайном порядке

[Trotil]

Постановка задачи:
есть числовой массив: {1, 2, 3, ..., N}, причем N - достаточно большое
Нужно его перемешать в произвольном порядке.
То есть в итоге я должен получить: {31, 17, 94, 1, 389, ...}, естественно каждый раз в разном порядке.

Как можно оптимальным способом по времени решить такую задачу?

Мой вариант:

// N - первоначальная длина массива
// n - текущая длина массива
// a - старый массив
// b - новый массив

n=N;
while (n>=0)
{
 i=random(n);
 b[N-n]=a[i];
 deleted (a. i); // удаляет из массива a элемент a[i]
 n--;
}

 

[Шогал]

Ну, каждое удаление будет выполняться за линейную сложность. Лучше вместо удаления a присваивать ему значение a[n-1].