Swap的簡單實現(xiàn)

//C語言方式(by-pointer): template <typename Type> bool swapByPointer(Type *pointer1, Type *pointer2) {//確保兩個指針不會指向同一個對象if (pointer1 == NULL || pointer2 == NULL){return false;}if (pointer1 != pointer2){Type tmp = *pointer1;*pointer1 = *pointer2;*pointer2 = tmp;}return true; }
//C++特有方式(by-reference): template <typename Type> void swapByReference(Type &value1, Type &value2) {if (value2 != value1){Type tmp = value1;value1 = value2;value2 = tmp;} }

小結(jié):

雖然我們自己實現(xiàn)了swap,但我們還是比較推薦使用C++?STL已經(jīng)實現(xiàn)好的std::swap()函數(shù),其存在于命名空間std中,使用實例如下面的<冒泡排序>.

??

冒泡排序(Bubble-Sort)

算法思想:

從左到右掃描數(shù)據(jù),找出最大的元素,將其放到數(shù)組右邊;

過程:

循環(huán)比較相鄰的兩個數(shù),如果左邊的數(shù)比右邊的大,則交換兩個數(shù);

//實現(xiàn):注意代碼中的三個注意點(x): template <typename Type> void bubbleSort(Type *begin, Type *end) {if ((begin == end) || (begin == NULL) || (end == NULL))return ;int length = end - begin;//注意點(1):保證一旦數(shù)組有序, 則會直接停止排序, 不會在繼續(xù)進(jìn)行無用的循環(huán)bool isOrder = false;//外層循環(huán)控制掃描次數(shù)(length-1)//注意點(2):N個元素其實只需N-1次掃描for (int i = 0; !isOrder && i < length-1; ++i){//首先假定這次數(shù)組已經(jīng)有序isOrder = true;//注意點(3):確保能夠從0掃描到最后一個未排序的元素for (Type *iter = begin; iter < end-i-1; ++iter){//如果前面的左邊的元素>右邊的元素if (*iter > *(iter+1)){//交換std::swap(*iter, *(iter+1));isOrder = false;}}} }template <typename Type> void bubbleSort(Type *array, int length) {return bubbleSort(array, array+length); }

選擇排序(Select-Sort)

思想:

從當(dāng)前尚未排序的序列中選擇一個最小的元素,?將之放到已排序的序列的隊列的末尾;

要點:

1.注意三個指針(inner,?outer,?miner)所代表的含義;

2.同時注意是從未排序的序列中進(jìn)行查找最小元素!

//實現(xiàn) template <typename Type> void selectSort(Type *begin, Type *end) {if ((begin == end) || (begin == NULL) || (end == NULL))return ;//只要循環(huán)到最后一個元素的前一個就行了,因為剩下的那個肯定是最大的for (Type *outer = begin; outer < end-1; ++outer){//注意:是從尚未排序的序列中查找(miner = outer, inner = outer+1)Type *miner = outer;//從miner+1開始遍歷數(shù)組, 尋找一個元素值小于*miner的for (Type *inner = outer+1; inner < end; ++inner){if (*inner < *miner)miner = inner;}if (miner != outer)std::swap(*miner, *outer);} }//為了能夠讓STL的標(biāo)準(zhǔn)容器如vector使用 template <typename Iterator> void selectSort(Iterator iter1, Iterator iter2) {return selectSort(&(*iter1), &(*iter2)); }template <typename Type> void selectSort(Type *array, int length) {return selectSort(array, array+length); }

小結(jié):

雖然我們自己實現(xiàn)了Bubble-Sort和Select-Sort,但我們在實際軟件開發(fā)中一般是不會用到的,因為的它的效率為O(N^2),效率太慢^_^,?因此我們還是推薦使用C++?STL中已經(jīng)實現(xiàn)了的std::sort(),?其內(nèi)部原理使用了快速排序,?效率為O(logN)速度非常快.

?

附-測試程序

int main() {srand(time(NULL));vector<double> dVec;int count = 10;while (count --){dVec.push_back((rand()%1000)/100.0);}selectSort(dVec.begin(), dVec.end());for (vector<double>::iterator iter = dVec.begin(); iter < dVec.end(); ++iter){cout << *iter << endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的数据结构基础(1) --Swap Bubble-Sort Select-Sort的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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