数据结构与算法
Sorting Algorithms:Selection Sort
1 基本思路
- 遍历数组，把最小（大）的元素放在数组首部，
- 把剩下的元素看做一个数组，再次遍历，
- 获得最小（大）的元素放在数组首部
- 意在每次遍历新数组选择出最小（大）元素
2 图示
164ac5c57b349a90.gif
3 算法复杂度分析
| 平均 | 最坏 | 最好 | 稳定性 | 空间复杂度 |
|---|---|---|---|---|
| O(n^2) | O(n^2) | O(n^2) | 不稳定 | O(1) |
p.s. 最好情况：即不用元素交换，但仍要进行比较。比较次数n(n-1)/2次
4 代码实现
/**
*
* Selection Sort
* 遍历数组，把最小（大）的元素放在数组首部，
* 把剩下的元素看做一个数组，再次遍历，
* 获得最小（大）的元素放在数组首部
* 意在每次遍历新数组选择出最小（大）元素
* 算法复杂度分析
* 比较次数 n(n-1)/2 次
* 时间复杂度（平均） O(n^2) 外循环n次，内循环m次 m*n
* 时间复杂度（最坏） O(n^2) 外循环n次，内循环m次 m*n
* 时间复杂度（最好） O(n^2) 即不用元素交换，但仍要进行比较
* 空间复杂度 O(1)
* 稳定性 不稳定
*/
public class SelectionSort {
public static void main(String[] args) {
int[] a = new int[10];
//random array
for (int i = 0; i < a.length; i++) {
Random rd = new Random();
a[i] = rd.nextInt(10);
}
System.out.println("Random Array :");
System.out.println(Arrays.toString(a));
System.out.println();
System.out.println("Selection Sort :");
int temp = 0;
//外循环规定遍历次数，最后只剩一个元素则不需再遍历
// 所以外循环遍历 n-1次数组
for (int i = 0; i < a.length - 1; i++) {
//当前遍历数组最小元素的角标，初始时令其=i
int minIndex = i;
//将剩余未排序元素当成新的数组，与该数组首位元素比较
// 比较后记录最小元素的角标
for (int j = i + 1; j < a.length; j++) {
//比较
if (a[minIndex] > a[j]) {
minIndex = j;
}
}
//根据最小元素的角标，将其放到当前数组的首位
if (minIndex != i) {
temp = a[minIndex];
a[minIndex] = a[i];
a[i] = temp;
}
}
System.out.println(Arrays.toString(a));
}
}
