简单选择排序也叫作直接选择排序

基本思想：

每一趟在后面n-i+1个中选出关键字最小的记录，作为有序序列的第i个记录

(1)设待排序的记录存放在数组r[1…n ]中，第一趟从r[1]开始，通过n-1次比较，从n个记录中选出关键字最小的记录，记为r[k]，交换r[1]和r[k].

(2)第二趟从r[2]开始，通过n-2次比较，从n-1个记录中选出关键字最小的记录，记为r[k],交换r[1]和r[k]。

(3)第i趟从r[i]开始，通过n-i次比较，从n-1+1个记录中选出关键字最小的记录，记为r[k]，交换r[i]和r[k].

(4)经过n-1趟，排序完成。

void SelectSort(SqList &K){//对顺序表L做简单选择排序    for(i=1;i

算法分析

移动次数

• 最好情况： 0

• 最坏情况：3(n-1)

比较次数：1/2（n*n-n）

时间复杂度：O(n*n)

空间复杂度:O(1)

算法特点

不稳定