最新公告
  • 欢迎您光临波比源码,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 数据结构基础(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;
    }
    }

    小结:

    虽然我们自己实现了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;
    }

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

    波比源码 » 数据结构基础(1) –Swap & Bubble-Sort & Select-Sort

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    波比源码
    一个高级程序员模板开发平台
    升级波友尊享更多特权立即升级