Google Image
在排序算法中，最简单的莫过于选择排序了。
本文将介绍以下内容
排序思路
算法实现（JAVA）
测试阶段
算法分析
排序思路：
在选择排序算法中分别有一个外循环和一个内循环，假设需要排序的序列共有n个元素，所以外循环的次数为n次，在n次交换（外循环）中，每次设置序列中的第一个元素为最小值（min)，然后进行内循环，每次内循环都将序列中与min比较，若有元素小于min，则进行交换（若没有，min自己与自己交换）。所以内循环的次数暂时不确定。
简而言之，就是在未排序的序列中，每次选取序列首位元素，依次与序列中其他元素比较，进而交换元素，达到排序的效果。
算法实现
1.外循环
public static void selectionSort(int[] a){
int n = a.length;
for (int i = 0; i < n; i++) { //外循环共n次
int min = i;
int temp = a[i]; //
a[i] = a[min]; // 交换元素
a[min] = temp; //
}
}
共有n次交换
2.内循环（比较大小并交换元素索引）
for (int j = i + 1; j < n; j++) {
if(a[j] < a[min]){
min = j; //如果由元素小于min,则交换元素索引
}
}
j = i + 1, i +2 , i + 3 ... n.
共有n - i - 1次比较，比较的次数将会在下文提及。
3.交换元素
int temp = a[i];
a[i] = a[min];
a[min] = temp;
所以，选择排序的代码块
就是如此了：
public static void selectionSort(int[] a){
int n = a.length;
for (int i = 0; i < n; i++) {
int min = i;
for (int j = i + 1; j < n; j++) {
if(a[j] < a[min]){
min = j;
}
}
int temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
测试阶段
我们来写一个测试数据：
public static void main(String[] args){
int[] a = new int[10];
for (int i = 0; i < a.length; i++) {
a[i] = (int)(Math.random()*100); //随机输入测试数据
System.out.print(a[i] + " ");
}
System.out.println();
selectionSort(a);
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
随机选取几组排序结果：
test 1
test 2
test 3
算法分析：
1. 特点
运行时间与输入数据无关，运行时间与数组大小成线性相关，无论
初始数据的有序性如何，都不会改变元素交换的次数。数据的移动最少，这是其他排序所不能比的，每次外循环使数据移
动一次，所以选择排序的数据移动次数为 n 次。
2. 时间复杂度
内循环：n 次交换
外循环：比较的次数随着i的增长而减少，每次内循环有n -1 - i 次比
较，总共比较次数：
(n - 1) + (n - 2) + ... + 2 + 1 = n(n - 1) / 2基本操作总数： n + n(n - 1) /2 = n(n + 1) / 2 ~ n2/2
所以，时间复杂度为O(n2)，平方级别
3. 空间复杂度
- 在交换素组元素时，需要建立一个临时变量来帮助交换元素，所以空间复杂度为O(1)
4. 稳定性
- 由于选择排序在排序前后会打乱相同键值元素的相对顺序，所以选择排序是不稳定的
关于选择排序的说明就到这里了，下一篇将会是 冒泡排序 。
给颗红心，举手之劳， 谢谢！
