选择排序
栏目：综合技术时间：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)。
------分隔线----------------------------
------分隔线----------------------------