程序员人生 网站导航

选择排序

栏目:综合技术时间:2015-05-07 10:01:26

选择排序

选择排序和冒泡排序1样,很简单,而且也比冒泡排序更好理解。

原理:
从0位置开始,顺次遍历数组0-(n⑴)元素,选择最小(或最大)的,与第1个元素交换。
从1位置开始,顺次遍历数组1-(n⑴)元素,选择最小(或最大)的,与第2个元素交换。

直到n⑴位置

代码:

// 选择排序 void selectSort(int arr[], int len) { int temp; for (int i = 0; i < len; i++) { int minIndex = i; for (int j = i; j < len; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } if (minIndex != i) { temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } } }

图解:
这里写图片描述
这里写图片描述

从arr[0]~arr[9], 选择最小的1个arr[9]=1, 与arr[0]交换
从arr[1]~arr[9], 选择最小的1个arr[8]=2, 与arr[1]交换

很简单吧!

分析:
我们可以看到,1共比较了 1+2+…+n⑴ 次, 但是比排序更好的是,选择选择最小的数后只需要交换1次。时间复杂度: O(n2)

------分隔线----------------------------
------分隔线----------------------------

最新技术推荐