选择排序
基本原理: 将待排序的元素分为已排序(初始为空)和未排序两组，依次将未排序的元素中值最小的元素放入已排序的组中。
两种常见的选择排序： 简单选择排序、堆排序。
简单选择排序
在一组元素R[i]到R[n]中选择具有最小关键码的元素，若它不是这组元素中的第一个元素，则将它与这组元素中的第一个元素对调。除去具有最小关键字的元素，在剩下的元素中重复第(1)、(2)步，直到剩余元素只有一个为止。
(简单)选择排序.gif
简单选择排序示例:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 状态 |
|---|---|---|---|---|---|---|---|---|
| 49 | 38 | 65 | 97 | 76 | 13 | 27 | 49' | 初始状态 |
| 13 | 38 | 65 | 97 | 76 | 49 | 27 | 49' | 第一趟 |
| 13 | 27 | 65 | 97 | 76 | 49 | 38 | 49' | 第二趟 |
| 13 | 27 | 38 | 97 | 76 | 49 | 65 | 49' | 第三趟 |
| 13 | 27 | 38 | 49 | 76 | 97 | 65 | 49' | 第四趟 |
| 13 | 27 | 38 | 49 | 49' | 97 | 65 | 76 | 第五趟 |
| 13 | 27 | 38 | 49 | 49' | 65 | 97 | 76 | 第六趟 |
| 13 | 27 | 38 | 49 | 49' | 65 | 76 | 97 | 第七趟 |
代码：
void Select_Sort(int s[]) {
for (int i = 0; i < s.length; i++) {
int mix_index = i;
for (int j = i; j < s.length; j++) {
if (s[j] < s[mix_index])
mix_index = j;
}
if(i == mix_index)
continue;
int temp = s[mix_index];
s[mix_index] = s[i];
s[i] = temp;
}
}
public static void main(String[] args) {
int[] s = {49,38,65,97,76,13,27,49};
new SelectSort().Select_Sort(s);
for (int i = 0; i < s.length; i++) {
System.out.printf("%d ",s[i]);
}
}
输出：
13 27 38 49 49 65 76 97
简单选择排序的效率分析
| 排序算法 | 平均时间性能 | 最好时间性能 | 最坏时间性能 | 辅助空间 | 稳定性 |
|---|---|---|---|---|---|
| 简单选择排序 |  |
|
|
 |
不稳定 |
-
无论初始状态如何，在第i 趟排序中选择最小关键码的元素，需做n-i次比较，因此总的比较次数为：
(时间复杂度) 最好情况：序列为正序时，移动次数为0；最坏情况：序列为反序时，每趟排序均要执行交换操作，总的移动次数取最大值3(n-1)。
由于在直接选择排序中存在着不相邻元素之间的互换，因此，直接选择排序是一种不稳定的排序方法。例如,给定排序码为3，7，3＇，2，1，排序后的结果为1，2，3＇，3，7。
