如何随机打乱一个有序序列？

Question

如何随机打乱一个有序序列？假设有一数组array，其中有1..10十个元素，按从小到大排列，写一个程序将其随机打乱。要求：1.时空复杂度越低越好2.使用Pascal，c，c++或Java语言3.最好写出程序

Answer 1

你所说的其他的算法都是常见的基于比较的排序算法插入排序：基本思想每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。代码范例：for(i = 1; i < n; ++i)
{int temp = a[i];<br>for (j = i; j > 0 && temp < a[j - 1]; --j)<br> a[j] = a[j - 1];<br>}
　a[j] = temp;
}[初始关键字] [49] 38 65 97 76 13 27 49
J=2(38) [38 49] 65 97 76 13 27 49
J=3(65) [38 49 65] 97 76 13 27 49
J=4(97) [38 49 65 97] 76 13 27 49
J=5(76) [38 49 65 76 97] 13 27 49
J=6(13) [13 38 49 65 76 97] 27 49
J=7(27) [13 27 38 49 65 76 97] 49
J=8(49) [13 27 38 49 49 65 76 97]
二、选择排序
1. 基本思想：
　　每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。【示例】：
初始关键字 [49 38 65 97 76 13 27 49]
第一趟排序后 13 ［38 65 97 76 49 27 49]
第二趟排序后 13 27 ［65 97 76 49 38 49]
第三趟排序后 13 27 38 [97 76 49 65 49]
第四趟排序后 13 27 38 49 [49 97 65 76]
第五趟排序后 13 27 38 49 49 [97 97 76]
第六趟排序后 13 27 38 49 49 76 [76 97]
第七趟排序后 13 27 38 49 49 76 76 [ 97]
最后排序结果 13 27 38 49 49 76 76 97 5)归并排序
归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。(6)基数排序
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以其是稳定的排序算法。(7)希尔排序(shell)
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。(8)堆排序
我们知道堆的结构是节点i的孩子为2*i和2*i+1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1, n/2-2, ...1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。

Answer 2

　　const maxlength=10; {这里的数组中只有10个元素，更多的元素直接改这里的maxlength的值}
　　change=20; {这里只交换20次，如果想要交换的更多，可以把change的值改成想要的次数}
　　var i,j,k:longint;
　　a:array[1..maxlength] of longint;{这里定义成longint是方便你处理更大的数据，下面过程同}
　　procedure swap(var x,y:longint); {交换}
　　var s:longint;
　　begin
　　s:=x;
　　x:=y;
　　y:=s;
　　end;
　　begin
　　for i:=1 to maxlength do readln(a[i]); {读}
　　randomize; {初始化}
　　for i:=1 to change do begin
　　j:=random(maxlength-1)+1; {这样做是防止生成出来的随机数是0，导致数组下标越界，下同}
　　k:=random(maxlength-1)+1;
　　swap(a[j],a[k]);
　　end;
　　for i:=1 to maxlength do writeln(a[i]);
　　end.

Answer 3

C语言代码如下：
#include <stdio.h>
#include <conio.h>
#define N 10
int main(void)
{
int a[N] = {1,2,3,4,5,6,7,8,9,10};
int i;
int index;
int temp;
srand((unsigned)time(NULL));
for (i = N - 1; i > 0; i--)
{
index = rand() % i;
temp = a[i];
a[i] = a[index];
a[index] = temp;
}
for (i = 0; i < N; i++)
{
printf("%d ", a[i]);
}
getch();
return (0);
}

时间复杂度为O(n)。。以下为连续4次的运行结果。。您看看。。

Answer 4

Fisher-Yates shuffle

// java代码
import java.util.Random;

static Random rng = new Random();
public static void shuffle(int[] array) {
// i is the number of items remaining to be shuffled.
for (int i = array.length; i > 1; i--) {
// Pick a random element to swap with the i-th element.
int j = rng.nextInt(i); // 0 <= j <= i-1 (0-based array)
// Swap array elements.
int tmp = array[j];
array[j] = array[i-1];
array[i-1] = tmp;
}
}

http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle本回答被网友采纳