冒泡排序与选择排序
冒泡排序：从首元素开始，依次比较前后两个元素，比较到最后一个元素的时候，即可得到最大值，最大值的位置就是末尾元素，下次排序不用考虑末尾元素
选择排序：从首元素开始，从未排序序列中选择出最小值（即记录最小值坐标位置），最小值坐标初始化为首元素坐标，首元素后面的元素依次与最小值比较，比较到最后一个元素即可得到最小值，再与首元素交换，下次排序不再考虑首元素
两者性能比较
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)级别的排序算法，但选择排序仍优于冒泡排序
