一. 算法描述
选择排序：比如在一个长度为N的无序数组中，在第一趟遍历N个数据，找出其中最小的数值与第一个元素交换，第二趟遍历剩下的N-1个数据，找出其中最小的数值与第二个元素交换......第N-1趟遍历剩下的2个数据，找出其中最小的数值与第N-1个元素交换，至此选择排序完成。
举个例子：5 7 6 4 3 8
第一趟： 3 7 6 4 5 8
第二趟： 3 4 6 7 5 8
第三趟： 3 4 5 7 6 8
第四趟： 3 4 5 6 7 8
第五趟： 3 4 5 6 7 8
二. 算法实现
#include<stdio.h> /*
* author：Knife
* time：2014.06.13 11:17
* algorithm：选择排序
*/ void main(){
int intArr[] = {,,,,,,,,,};
int n = sizeof(intArr)/sizeof(intArr[]); // 计算整型数组的长度
int minIndex,tmp;
// 选择排序
for(int i = ; i < n-; i++){
minIndex = i;
for(int j = i+; j < n; j++){
if(intArr[j]<intArr[minIndex]){
minIndex = j;
}
}
if(minIndex != i){
tmp = intArr[minIndex];
intArr[minIndex] = intArr[i];
intArr[i] = tmp;
}
} //打印输出
for(int i=; i < n; i++){
printf("%d ", intArr[i]);
}
printf("\n");
}
三. 算法分析
- 平均时间复杂度：O(n2)
- 空间复杂度：O(1) (用于交换和记录索引)
- 稳定性：不稳定 （比如序列【5， 5， 3】第一趟就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）
参考资料
[1] http://blog.****.net/cjf_iceking/article/details/7914554