冒泡排序与选择排序的比较-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

冒泡排序与选择排序的比较

简介: 冒泡排序与选择排序的比较

冒泡排序与选择排序

冒泡排序:从首元素开始,依次比较前后两个元素,比较到最后一个元素的时候,即可得到最大值,最大值的位置就是末尾元素,下次排序不用考虑末尾元素

选择排序:从首元素开始,从未排序序列中选择出最小值(即记录最小值坐标位置),最小值坐标初始化为首元素坐标,首元素后面的元素依次与最小值比较,比较到最后一个元素即可得到最小值,再与首元素交换,下次排序不再考虑首元素

两者性能比较

bubbleSort.h

#ifndef BUBBLESORT_H

#define BUBBLESORT_H

#include <iostream>

#include <algorithm>

using namespace std;

template <typename T>

void bubbleSort(T arr[],int n){

    bool flag;

    do{

        flag=false;

        for(int i=1;i<n;i++){

            if(arr[i]<arr[i-1]){

                swap(arr[i],arr[i-1]);

                flag=true;

            }

        }

        n--;

    }while(flag);

}

#endif

selectionSort.h

#ifndef SELECTIONSORT_H

#define SELECTIONSORT_H

#include <iostream>

#include <algorithm>

using namespace std;

template<typename T>

void selectionSort(T arr[],int n){

    for(int i=0;i<n;i++){

        int minIndex=i;

        for(int j=i+1;j<n;j++){

            if(arr[j]<arr[minIndex])

                minIndex=j;

        }

        swap(arr[i],arr[minIndex]);

    }

}

#endif

SortTestHelper.h

#ifndef SORTTESTHELPER

#define SORTTESTHELPER

#include <iostream>

#include<cassert>

#include<ctime>

using namespace std;

namespace SortTestHelper{

    //生成有n个元素的随机数组,每个元素的随机范围是[rangeL,rangeR]

    int* generateRandomArray(int n,int rangeL,int rangeR){

        assert(rangeL<=rangeR);

        int* arr=new int[n];

        srand(time(0));

        for(int i=0;i<n;i++)

            arr[i]=rand()%(rangeR-rangeL+1)+rangeL;

        return arr;

    }

    //打印数组

    template<typename T>

    void printArray(T arr[],int n){

        for(int i=0;i<n;i++)

            cout << arr[i] << " ";

        cout << endl;

        return;

    }

    //判断是否排序

    template <typename T>

    bool isSorted(T arr[],int n){

        for(int i=1;i<n;i++)

            //如果前一个元素比后一个元素还要大,说明没有排序成功

            if(arr[i-1]>arr[i])

                return false;

        return true;

    }

    //测试排序算法时间性能,参数为排序算法名称,排序算法函数指针,随机数组,数组个数

    template <typename T>

    void testSort(string sortName,void(*sort)(T[],int),T arr[],int n){ 

        clock_t startTime=clock();

        sort(arr,n);

        clock_t endTime=clock();

        //断言:表达式为假,程序会终止

        //assert(表达式);

        assert(isSorted(arr,n)); 

        cout << sortName << " : " << double(endTime-startTime)/CLOCKS_PER_SEC <<  " s" << endl;

        return;

    }

    //数组复制

    int* copyIntArray(int a[],int n){

        int* arr=new int[n];

        copy(a,a+n,arr);

        return arr;

    }

    // 生成一个近乎有序的数组

    int* generateNearlyOrderedArray(int n,int swapTimes){

        int* arr=new int[n];

        for(int i=0;i<n;i++)

            arr[i]=i;

        srand(time(0));

        for(int i=0;i<swapTimes;i++){

            int posx=rand()%n;

            int posy=rand()%n;

            swap(arr[posx],arr[posy]);

        }

        return arr;

    } 

}

#endif

#include<iostream>

#include<algorithm>

#include "bubbleSort.h"

#include "selectionSort.h"

#include "SortTestHelper.h"

using namespace std;

int main(){

    int n=1000;

    cout << "n = " << n << endl;

    //生成乱序数组

    int* arr=SortTestHelper::generateRandomArray(n,0,n);

    int* arr2=SortTestHelper::copyIntArray(arr,n);

    //测试耗时

    SortTestHelper::testSort("bubbleSort",bubbleSort,arr,n);

    SortTestHelper::testSort("selectionSort",selectionSort,arr2,n); 

    //释放空间

    delete[] arr;

    delete[] arr2;

    return 0;

}

打印结果:

n = 10000

bubbleSort : 1.843 s

selectionSort : 0.176 s

n = 100000

bubbleSort : 167.288 s

selectionSort : 14.919 s

数据量扩大10倍,排序所耗时间扩大100倍,可见两者时间复杂度都是O(n^2)

总结

两者比较方式相同,交换方式不同

冒泡排序可能每一次比较都会交换,最多比较n次,交换n次

选择排序,比较n次在未排序序列中选择出最值,才会进行交换,即比较n次,交换1次

可见虽然两者都是O(n^2)级别的排序算法,但选择排序仍优于冒泡排序

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章
最新文章
相关文章