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

## 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;
}
}

## 冒泡排序(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.注意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);
}

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;
}

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，您必须在下载后24小时内删除！
3. 不得使用于非法商业用途，不得违反国家法律。否则后果自负！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 本站源码并不保证全部能正常使用，仅供有技术基础的人学习研究，请谨慎下载
8. 如遇到加密压缩包，请使用WINRAR解压,如遇到无法解压的请联系管理员！