程序员人生 网站导航

数据结构基础(1) --Swap & Bubble-Sort & Select-Sort

栏目:php教程时间:2015-01-05 08:12:39

Swap的简单实现

//C语言方式(by-pointer): template <typename Type> bool swapByPointer(Type *pointer1, Type *pointer2) { //确保两个指针不会指向同1个对象 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; } }

小结:

虽然我们自己实现了swap,但我们还是比较推荐使用C++ STL已实现好的std::swap()函数,其存在于命名空间std中,使用实例以下面的<冒泡排序>.

  

冒泡排序(Bubble-Sort)

算法思想:

从左到右扫描数据,找出最大的元素,将其放到数组右侧;

进程:

循环比较相邻的两个数,如果左侧的数比右侧的大,则交换两个数;

//实现:注意代码中的3个注意点(x): template <typename Type> void bubbleSort(Type *begin, Type *end) { if ((begin == end) || (begin == NULL) || (end == NULL)) return ; int length = end - begin; //注意点(1):保证1旦数组有序, 则会直接停止排序, 不会在继续进行无用的循环 bool isOrder = false; //外层循环控制扫描次数(length⑴) //注意点(2):N个元素其实只需N⑴次扫描 for (int i = 0; !isOrder && i < length⑴; ++i) { //首先假定这次数组已有序 isOrder = true; //注意点(3):确保能够从0扫描到最后1个未排序的元素 for (Type *iter = begin; iter < end-i⑴; ++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)

思想:

从当前还没有排序的序列当选择1个最小的元素, 将之放到已排序的序列的队列的末尾;

要点:

1.注意3个指针(inner, outer, miner)所代表的含义;

2.同时注意是从未排序的序列中进行查找最小元素!

//实现 template <typename Type> void selectSort(Type *begin, Type *end) { if ((begin == end) || (begin == NULL) || (end == NULL)) return ; //只要循环到最后1个元素的前1个就好了,由于剩下的那个肯定是最大的 for (Type *outer = begin; outer < end⑴; ++outer) { //注意:是从还没有排序的序列中查找(miner = outer, inner = outer+1) Type *miner = outer; //从miner+1开始遍历数组, 寻觅1个元素值小于*miner的 for (Type *inner = outer+1; inner < end; ++inner) { if (*inner < *miner) miner = inner; } if (miner != outer) std::swap(*miner, *outer); } } //为了能够让STL的标准容器如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); }

小结:

虽然我们自己实现了Bubble-Sort和Select-Sort,但我们在实际软件开发中1般是不会用到的,由于的它的效力为O(N^2),效力太慢^_^, 因此我们还是推荐使用C++ STL中已实现了的std::sort(), 其内部原理使用了快速排序, 效力为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; }

------分隔线----------------------------
------分隔线----------------------------

最新技术推荐