最简单的排序--选择排序，你知多少？
各种排序是常见的面试题， 我希望能够帮助大家轻松的秒杀那些小菜鸟这个排序我原本不打算介绍的， 因为时间有限， 只能挑个简单的介绍了。
有个普遍的错误的观点，认为选择排序的 时间复杂度 总是为 0(n^2), 我告诉你， 还就不是的
#include <stdio.h>
#include <stdlib.h>
#define MAX_NUM 15
#define less(A, B) ((A) < (B))
#define exch(A, B) {char t = A; A = B; B = t;}
void selectionSort(char a[], int left, int right);
int main(void)
{
char a[MAX_NUM+1] = "ASORTINGEXAMPLE";
int i;
selectionSort(a, 0, MAX_NUM-1);
for (i = 0; i < MAX_NUM; i++)
{
printf("%c ", a[i]);
}
getchar();
return 0;
}
void selectionSort(char a[], int left, int right)
{
int i, j, min;
for (i = left; i < right; i++)
{
min = i;
for (j = i+1; j <= right; j++)
{
if (less(a[j], a[min]))
{
min = j;
}
}
exch(a[i], a[min]);
}
}
由排序过程可得， 选择排序 交换次数 与 n 成比例, 比较次数与 n^2成比例，
所以， 选择排序的 时间复杂度由 比较次数决定。
选择排序之所以慢，是因为他的运行时间与文件的已排序量基本没有关系，文件是 已有序的 或是 随机的，使用选择排序
排序， 所花时间基本一样。
需要注意的是，比较或是交换的关键字不一定是 单一数值，可能是字符串， 可能结构体...
对于大项、小键的文件， 选择排序恰恰是最好的选择，其运行时间 为线性的，没想到吧 ！
[ 本帖最后由 BlueGuy 于 2011-1-9 21:29 编辑 ]
