—选择排序—
在未排序的序列中找到最小（大），放在排序序列的起始位置，再从剩余的未排序找最小（大）放已排序序列末尾，重复步骤。
算法描述
具体算法描述如下：
<1>.首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
<2>.再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
<3>.重复第二步，直到所有元素均排序完毕。
代码实现
void Selection_Sort(int a[], int n)
{
// 外层循环 存放有序序列，最后一个元素已经有序，故n-1
for (int i = 0; i < n - 1; ++i)
{
int index = i; // 先假定有序序列的末尾为最小值
for (int j = i + 1; j < n; j++) //内层循环 意图寻找无序序列的最小数
{
if (a[index] > a[j]) //寻找最小的数
{
index = j; //将最小数的索引保存
}
}
// 结束循环 找到最小数的索引 交换元素
int temp = a[index];
a[index] = a[i];
a[i] = temp;
}
}
算法分析
平均情况：T(n) = O(n2)
最佳情况：T(n) = O(n2)
最差情况：T(n) = O(n2)
稳定性
- 不稳定
举例:
按照找最小值，与无序区首部交换的思想则不稳定：
排序前：
2 4 4* 3
排序后：
2 3 4* 4
两个相同的元素 排序后 位置发生了改变 故无序 。
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 351134995@qq.com
