seo网站推广怎么做,域名注册西部数码,电商seo搜索引擎优化,沪江博客wordpress模板实现in-place的数据交换 声明#xff1a;引用请注明出处http://blog.csdn.net/lg1259156776/ 经典的排序问题 问题描述 一个数组中包含两个已经排好序的子数组#xff0c;设计一个in-place#xff08;原位操作#xff09;算法来对这个数组排序。测试数据为 a[] 1 4 5 7 8 … 实现in-place的数据交换 声明引用请注明出处http://blog.csdn.net/lg1259156776/ 经典的排序问题 问题描述 一个数组中包含两个已经排好序的子数组设计一个in-place原位操作算法来对这个数组排序。测试数据为 a[] 1 4 5 7 8 9 2 3 6 10 11 。 问题分析 排序是一个非常经典的算法设计问题这个不是难点难点在于设定的in-place操作意思是所有的操作都是”就地“操作不允许进行移动。在我的博文《排序算法一直接插入排序》中讲到了对于排序算法时间复杂度在于项目间的比较和移动次数这里的in-place操作指的就是设定移动次数为0。分析排序算法中为何需要项目间的移动主要是为了节省内存消耗空间复杂度在原有的数组内存空间上进行排序这样就需要为已经排好序的数据倒腾内存通常的解决办法是将要倒腾的内存位置上的未排序的数据存在一个临时变量temp进行保存然后其它的数据依次移动。这样的算法额外的空间消耗只有O(1)。题目中的要求是这个临时变量也不能用。实际上是要解决in-place的数据交换操作。 解决方案in-place数据交换 通过异或操作实现原位数据交换。 #include iostreamusing namespace std;void swap(int x, int y)
{x x ^ y;y x ^ y;x x ^ y;
}void insertion(int a[], int sz)
{for(int i1; i sz; i) {int j i;while(j 0) {if(a[j-1] a[j]) swap(a[j-1],a[j]);j--;}}for(int i 1; i sz; i) cout a[i] ;
}int main()
{int a[] { 1, 4, 5, 7, 8, 9, 2, 3, 6, 10, 11 };int size sizeof(a)/sizeof(int);for (int i 0; i size; i) cout a[i] ;cout endl;insertion(a, size);cout endl;return 0;
} 输出为 1 4 5 7 8 9 2 3 6 10 11
2 3 4 5 6 7 8 9 10 11 分析原位数据交换 设定X1001Y0111进行原位数据交换操作的验证 XX xor Y1110YX xor Y1001XX xor Y0111从中可以看出X和Y在不借助任何临时变量的存储前提下in-place的完成了交换。 2015-9-24 艺少 转载于:https://www.cnblogs.com/huty/p/8519124.html
