排序算法之选择排序

选择排序也是一种简单直观的排序算法。它的工作原理很容易理解：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

// 分类 -------------- 内部比较排序

// 数据结构 ---------- 数组

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

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

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

// 所需辅助空间 ------ O(1)

// 稳定性 ------------ 不稳定

选择排序是不稳定的排序算法，不稳定发生在最小元素与A[i]交换的时刻。比如序列：{5, 8,5,2, 9 }，一次选择的最小元素是2，然后把2和第一个5进行交换，从而改变了两个元素5的相对次序。

#include

usingnamespacestd;

voidexchange(intA[],inti,intj)//交换A[i]和A[j]

{

inttemp = A[i];

A[i] = A[j];

A[j] = temp;

}

intmain()

{

intA[] = {8,5,2,6,9,3,1,4,0,7};//从小到大选择排序

intn =sizeof(A) /sizeof(int);

inti, j, min;

for(i =0; i <= n -2; i++)//已排序序列的末尾

{

min = i;

for(j = i +1; j <= n -1; j++)//未排序序列

{

if(A[j] < A[min])//依次找出未排序序列中的最小值,存放到已排序序列的末尾

{

min = j;

}

}

if(min != i)

{

exchange(A, min, i);//该操作很有可能把稳定性打乱,所以选择排序是不稳定的排序算法

}

}

printf("选择排序结果：");

for(i =0; i < n; i++)

{

printf("%d ",A[i]);

}

printf("\n");

return0;

}