排序算法之选择排序
版权所有，转载请注明：本文出自学与思编程网
选择排序应该是所有排序中最直接最简单的排序算法了，其基本思想是：首先在所有未排序元素序列中找到最小的元素并把这个元素与整个序列中的第一个元素交换，然后找出剩下的未排序序列中的最小元素与整个序列中的第二个元素交换，反复这一过程直到最后排序完成。我们还是以一个简单的整数升序排序为例看看其排序过程：
假定有一组待排序整数：3，5，2，1 现在我们要把这4个数按升序排列。
首先找到这四个元素中最小的1与第一个元素3交换，结果是：1，5，2，3
然后从第二个元素开始找到最小元素2与第二个元素5交换，结果是：1，2，5，3
再从第三个元素开始找到最小元素3与第三个元素5交换，结果是1，2，3，5
至此排序完成。
下面是选择排序的c语言代码
void selection_sort(int a[], int n)
{
int i, j;
int m;
int tmp;
for (i = 0; i < n – 1; i++) {
m = i;
for (j = i + 1; j < n; j++) {
if (a[j] < a[m]) {
m = j;
}
}
tmp = a[i];
a[i] = a[m];
a[m] = tmp;
}
}
下面简单的分析一下选择排序的时间复杂度。
看上面的代码，变量i循环了 n – 1 次，对每个i，j循环的次数为 n – (i + 1)次，即j的循环次数为：n – 1, n – 2, n – 3, …, 3, 2, 1. 这样j总共循环了1 + 2 + 3 + … + (n – 3) + (n – 2) + (n – 1) = (n – 1) * n / 2 = (n * n – n) / 2 次，这就是选择排序的比较次数。也样可知，选择排序的比较操作最坏，最好，平均时间复杂度均为n2。
版权所有，转载请注明：本文出自学与思编程网
