實現(xiàn)in-place的數(shù)據(jù)交換

---

聲明：引用請注明出處http://blog.csdn.net/lg1259156776/

---

經(jīng)典的排序問題

問題描述

一個數(shù)組中包含兩個已經(jīng)排好序的子數(shù)組，設(shè)計一個in-place（原位操作）算法來對這個數(shù)組排序。測試數(shù)據(jù)為 a[] = 1 4 5 7 8 9 　2 3 6 10 11 。

問題分析

排序是一個非常經(jīng)典的算法設(shè)計問題，這個不是難點，難點在于設(shè)定的in-place操作，意思是所有的操作都是”就地“操作，不允許進行移動。在我的博文《排序算法一：直接插入排序》中講到了對于排序算法，時間復(fù)雜度在于項目間的比較和移動次數(shù)，這里的in-place操作指的就是設(shè)定移動次數(shù)為0。分析排序算法中為何需要項目間的移動，主要是為了節(jié)省內(nèi)存消耗（空間復(fù)雜度），在原有的數(shù)組內(nèi)存空間上進行排序，這樣就需要為已經(jīng)排好序的數(shù)據(jù)倒騰內(nèi)存，通常的解決辦法是將要倒騰的內(nèi)存位置上的未排序的數(shù)據(jù)存在一個臨時變量（temp）進行保存，然后其它的數(shù)據(jù)依次移動。這樣的算法額外的空間消耗只有O(1)。題目中的要求是這個臨時變量也不能用。實際上是要解決in-place的數(shù)據(jù)交換操作。

解決方案：in-place數(shù)據(jù)交換

通過異或操作實現(xiàn)原位數(shù)據(jù)交換。

#include <iostream>using 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 i=1; 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

分析原位數(shù)據(jù)交換

設(shè)定X=1001，Y=0111進行原位數(shù)據(jù)交換操作的驗證：

X=X?xor?Y=1110Y=X?xor?Y=1001X=X?xor?Y=0111從中可以看出X和Y在不借助任何臨時變量的存儲前提下，in-place的完成了交換。

---

2015-9-24 藝少

轉(zhuǎn)載于:https://www.cnblogs.com/huty/p/8519124.html

總結(jié)

以上是生活随笔為你收集整理的in-place数据交换的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。