冒泡排序与选择排序

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

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

两者性能比较

bubbleSort.h

#ifndef BUBBLESORT_H

#define BUBBLESORT_H

#include <iostream>

#include <algorithm>

usingnamespacestd;

template<typenameT>

voidbubbleSort(Tarr[],intn){

   boolflag;

   do{

       flag=false;

       for(inti=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>

usingnamespacestd;

template<typenameT>

voidselectionSort(Tarr[],intn){

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

       intminIndex=i;

       for(intj=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>

usingnamespacestd;

namespaceSortTestHelper{

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

   int*generateRandomArray(intn,intrangeL,intrangeR){

       assert(rangeL<=rangeR);

       int*arr=newint[n];

       srand(time(0));

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

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

       returnarr;

   }

   //打印数组

   template<typenameT>

   voidprintArray(Tarr[],intn){

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

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

       cout<<endl;

       return;

   }

   //判断是否排序

   template<typenameT>

   boolisSorted(Tarr[],intn){

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

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

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

               returnfalse;

       returntrue;

   }

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

   template<typenameT>

   voidtestSort(stringsortName,void(*sort)(T[],int),Tarr[],intn){

       clock_tstartTime=clock();

       sort(arr,n);

       clock_tendTime=clock();

       //断言：表达式为假，程序会终止

       //assert(表达式);

       assert(isSorted(arr,n));

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

       return;

   }

   //数组复制

   int*copyIntArray(inta[],intn){

       int*arr=newint[n];

       copy(a,a+n,arr);

       returnarr;

   }

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

   int*generateNearlyOrderedArray(intn,intswapTimes){

       int*arr=newint[n];

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

           arr[i]=i;

       srand(time(0));

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

           intposx=rand()%n;

           intposy=rand()%n;

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

       }

       returnarr;

   }

}

#endif

#include<iostream>

#include<algorithm>

#include "bubbleSort.h"

#include "selectionSort.h"

#include "SortTestHelper.h"

usingnamespacestd;

intmain(){

   intn=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;

   return0;

}

打印结果：

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)级别的排序算法，但选择排序仍优于冒泡排序