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

Swap的简单实现

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

小结:

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

冒泡排序(Bubble-Sort)

算法思想:

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

过程:

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

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

思想:

从当前尚未排序的序列中选择一个最小的元素, 将之放到已排序的序列的队列的末尾;

要点:

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

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

//实现  
template <typename Type>  
void selectSort(Type *begin, Type *end)  
{  
    if ((begin == end) || (begin == NULL) || (end == NULL))  
        return ;  
    //只要循环到最后一个元素的前一个就行了,因为剩下的那个肯定是最大的  
    for (Type *outer = begin; outer < end-1; ++outer)  
    {  
        //注意:是从尚未排序的序列中查找(miner = outer, inner = outer+1)  
        Type *miner = outer;  
        //从miner+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,但我们在实际软件开发中一般是不会用到的,因为的它的效率为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;  
}  

原文发布于微信公众号 - Java帮帮(javahelp)

原文发表时间:2017-02-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Vamei实验室

Python基础02 基本数据类型

作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢! 简单的数据类型以及赋值 变量不需要声明 P...

19850
来自专栏峰会SaaS大佬云集

C#学习---基础入门(五)

    语法  string Insert(int startIndex ,string value)

13940
来自专栏思考的代码世界

Python基础学习02天

17540
来自专栏CDA数据分析师

Python正则表达式指南

本文介绍了Python对于正则表达式的支持,包括正则表达式基础以及Python正则表达式标准库的完整介绍及使用示例。本文的内容不包括如何编写高效的正则表达式、如...

21050
来自专栏Python

while补充,字符串和数字的内置方法

一、while循环的补充 while True: name=input('please input your name: ') password...

27170
来自专栏AI研习社

最常见的 35 个 Python 面试题及答案(2018 版)

作为一个 Python 新手,你必须熟悉基础知识。在本文中我们将讨论一些 Python 面试的基础问题和高级问题以及答案,以帮助你完成面试。包括 Python ...

87330
来自专栏专注 Java 基础分享

java基础之继承(二)

上篇我们介绍了java中的构造方法,了解了关键字this和super在继承中所起到的作用,this可以显式调用重载的构造方法,super可以显式的调用父类中的任...

21180
来自专栏程序员八阿哥

菜鸟学Python(2):Python可迭代对象中的添加和删除(add,append,pop,remove,insert)

学习python的list,tuple,dict,set的时候被插入和删除的用法弄得有点晕,所以进行归纳,以便记忆

10110
来自专栏nummy

Python中getattr、__get__、__getattr__和__getattribute__的区别

getattr (object, name[, default])是Python的内置函数之一,它的作用是获取对象的属性。

11110
来自专栏python百例

07-列表基础

8610

扫码关注云+社区

领取腾讯云代金券