数据结构基础(1) --Swap & Bubble-Sort & Select-Sor
发布时间：2020-12-13 20:24:37 所属栏目：PHP教程 来源：网络整理
导读：Swap的简单实现 //C语言方式(by-pointer):template typename Typebool swapByPointer(Type *pointer1,Type *pointer2){ //确保两个指针不会指向同1个对象 if (pointer1 == NULL || pointer2 == NULL) { return false; } if (pointer1 != pointer2) { Type tm
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;
} （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |