选择排序（C）

选择排序

  顾名思义，先在数据集合中选出最大或最小元素的位置，依次排列位置顺序，之后再从剩余元素中找出最大或最小元素的位置，排于其次，直到仅剩一个元素时，完成排序。

算法描述

假设：对于集合N【len】进行选择排序，i 为排序次数，0 <= i < len - 1 对于 len 个元素进行 len - 1 次排序即可
第 1 次排序： 次数 i = 0 开始
  先从 len - 1 个元素中找出最小元素的位置 min（顺序），即：j = 0; j < len; j++；
  然后N【min】与 N【0】元素互换位置，此时元素N【0】就是集合N中最小的元素；
  继续下一轮排序 i++；
第 i 次排序：次数 i < len - 1
  当进行第 i 次排序时， 需要从剩下的 第 i 到 第（len -1）个元素中找出最小元素的位置 min，
  因为前面 i -1 个元素已经按顺序排列，即：j = i; j < len; j++；
  然后N【min】与N【i】元素互换位置，此时元素N【i】就是剩余元素中最小的元素；
  到此前面 0 到 i 个元素按顺序排列，i++ 继续执行下一轮排序，直到 i = len - 2 时完成排序；

示例代码

下面用 C语言实现一下选择排序

void select_Sort(int *N, int len)
{
	int i, j, min, temp;
	for(i = 0; i < len - 1; i++) {
		min = i;
		for(j = i + 1; j < len; j++) {
			if(N[j] < N[min]) {
				min = j;	// min一直存放较小元素的位置
			}
		}
		if(i != min) {	// 如果当前N[i]就是最小的元素，无需交换位置
			temp = N[i];
			N[i] = N[min];
			N[min] = temp;
		}
	}
}

执行结果

下图将整个选择排序过程显示出来

算法复杂度

  空间复杂度为O（1），只需要一个临时变量辅助空间；时间复杂度为O（n^2），比较次数与关键字的初始状态无关，总的比较次数N= (n -1) + (n -2) + … + 2 + 1 = n*( n -1) / 2。交换次数O( n），最好情况是，已经有序，交换0次；最坏情况交换n-1次，逆序交换n/2次。交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，当 n 值较小时，选择排序比冒泡排序快。

  选择排序是也一种不稳定排序，比如序列【3， 4， 3, 1，5】，如下图所示：

排序前后，两个相同数值 3 的前后位置发生对调，验证其不稳定性。