完美洗牌算法（1）

题目描述;     有一个长度为2n的数组{a1,a2,a3,...,an,b1,b2,...,bn}，希望排序后变成{a1,b1,a2,b2,...an,bn}. 解法1： 位置置换算法 设定数组下标从 1开始

原始序列

A1

A2

A3

A4

B1

B2

B3

B4

数组下标

1

2

3

4

5

6

7

8

最终序列

B1

A1

B2

A2

B3

A3

B4

A4

通过对比原始序列与最终前后位置的变化 前n个元素中（1->2,2->4,2->6,4->8) 推广到一般情况，前n个元素中，第i个元素去了第2i个元素的位置 后n个元素中（5->1,6->3,7->5,8->7） 推广到一般情况，后n个元素中，第i个元素去了第2(i-n)-1= 2i-(2n+1 )=2i%(2n+1 ) 综合到任意情况，任意的第i个元素都最终换到了(2i)%(2n+1)的位置 c代码如下：

点击(此处)折叠或打开

#include<stdio.h> #include<stdlib.h> #define N 9 #define swap(t,x,y) (t = (x),x = (y),y = (t)) int b[N]; void LocationReplace(int *a,int n) {     int i = 0,n1 = 2*n,temp = 0;     for (i = 1;i <= n1 ;i++)     {         b[(2*i)%(2*n+1)] = a[i];//这里不要写成2i,2n,忘了*     }     for (i = 1;i <= n1 ;i++ )     {         a[i] = b[i];     }     for (i = 2;i<= n1 ;i += 2 )//交换a[1]和a[2],a[3]和a[4]...     {         swap(temp,a[i-1],a[i]);     } } int main() {     int a[9] = {0,1,2,3,4,5,6,7,8};     LocationReplace(a,4);     int i = 0;     for (i = 1;i <=8;i++)     {         printf("%d ",a[i]);     }     printf("\n");     return 0; } 运行结果如下： [root@localhost ~]# ./a.out 1 5 2 6 3 7 4 8 [root@localhost ~]#    此程序的时间复杂度是o(n),空间复杂度也是o(n). <script>window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"0","bdSize":"16"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];</script> 阅读(367) | 评论(0) | 转发(0) | 0

上一篇：荷兰国旗问题

下一篇：完美洗牌算法(2)

相关热门文章 test123编写安全代码——小心有符号数...使用openssl api进行加密解密...一段自己打印自己的c程序...彻底搞定C语言指针详解-完整版... 给主人留下些什么吧！~~ 评论热议