排序算法之简单选择排序
简单选择排序
接下来我们来简单地学习一下简单选择排序。
原理:
通过n-1次关键字之间的比较,从n-i+1个记录中找到关键字最小的记录,并和第i个记录交换。其实很好理解:在冒泡排序中,我们每次都做了交换,而这里我们不需要每次都进行交换,而是把最大的数(min记录的是最大值的下标)和第i个记录交换。
代码如下:
void simpleChooseSort(int a[],int aLength) { int i,j,min; for (i=0; i<aLength; i++) { min = i; for (j=i+1; j<aLength; j++) { if (a[min]<a[j]) { min=j; } } if (i!=min) { swap(a, i, min); } } }
比如说我们待排序的序列是:
{9,1,5,8,3,7,4,6,2}
也就是让数组第一个元素和后面的每个元素比较,但是比较的过程中不修改不进行交换,而是记录最大的数据的下标,然后把该最大元素与a[i]进行交换,这样便可以实现简单选择排序。
swap函数如下:
//交换位置 void swap(int a[],int i,int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; }
主函数如下:
int main(int argc, const char * argv[]) { int a[] = {12,34,9,1,5,8,3,7,4,6,2,13,42,16,23}; //length = 15 simpleChooseSort(a, 15); return 0; }
运行结果:
简单选择排序算法:42 34 23 16 13 12 9 8 7 6 5 4 3 2 1
其时间复杂的也是 O(n^2 ),虽然与冒泡排序同是O(n^2 ), 但是简单选择排序的性能还是要略优于冒泡排序的。