简单选择排序（直接选择排序）

【分类】

 选择类排序

【基本思想】

 每一趟从待排序的数据元素中选出最小（最大）的元素，顺序放在待排序的数列最前，直到全部待排序的数据元素全部排完。

【特点】

 数据结构：数组

 稳定性：不稳定

【过程】

 初始关键字：『 8，5，2，6，9，3，1，4，0，7 』

 第一趟排序后：0，『5，2，6，9，3，1，4，8，7』

 第二趟排序后：0，1，『2，6，9，3，5，4，8，7』

 第三趟排序后：0，1，2，『6，9，3，5，4，8，7』

 第四趟排序后：0，1，2，3，『9，6，5，4，8，7』

 第五趟排序后：0，1，2，3，4，『6，5，9，8，7』

 第六趟排序后：0，1，2，3，4，5，『6，9，8，7』

 第七趟排序后：0，1，2，3，4，5，6，『9，8，7』

 第八趟排序后：0，1，2，3，4，5，6，7，『8，9』

 第九趟排序后：0，1，2，3，4，5，6，7，8，『9』

 结果：          『 0，1，2，3，4，5，6，7，8，9 』

 

 

          

   排序过程           宏观过程

 

【复杂度与辅助空间】

 最差时间复杂度：O(n^2)

 最优时间复杂度：O(n^2)

 平均时间复杂度：O(n^2)

 所需辅助空间：O(1)

【实现方法】

 双重循环，外层i控制当前序列最小（最大）值存放的数组元素位置，内层循环j控制从i+1到n序列中选择最小的元素所在位置k。

【源程序】

void select_sort()
{
	int i,j,min;
    for (i = 0; i < n - 1; i++)//i为已排序序列的末尾
	{
        min = i;
        for (j = i + 1; j < n; j++)//未排序序列
            if (a[j] < a[min])//找出未排序序列中的最小值
		    min = j;
        if (min != i)
            swap(a[i],a[min]);//放到已排序序列的末尾，该操作很有可能把稳定性打乱，所以选择排序是不稳定的排序算法
    }
}