基本思想:简单选择排序就是通过n-i次关键字间的比较,从n-i+1个记录中选出关键字最小的记录,并和第i个记录交换值。
C++实现
/**********************************/ /***********选择排序***************/ /**********************************/ void SeclectSort(ElemType a[],int n) { int i,j,min; for(i = 0;i < n;i++) { min = i;//当前下标定义为最小值 for(j = i+1;j < n;j++) { if(a[min] > a[j])//若之后有小于当前最小值的关键字 min = j; } if(i != min) //若min不等于i,说明找到最小值,交换 swap(a,i,min); } }
Python实现
#---------------# #--Select sort--# #---------------# def select_sort(arr): arrlen = len(arr) #execute n-1 times for i in range(arrlen-1): min = i for j in range(i+1,arrlen): if(arr[min] > arr[j]): min = j if(i != min): swap(arr,i,min)
简单选择排序的复杂度分析:
无论最好最差的情况,其比较次数都是一样的多,第i趟排序需要进行n-i次关键字的比较,此时需要比较n(n-1)/2次。
最好情况下,交换次数为0,最差情况下,交换次数为n-1。
总的时间复杂度为o(n^2)。尽管与冒泡排序相同,但性能上略优于冒泡。