Sorting Algorithms:Selection Sort
предисловие
Этот блог используется для обзора и консолидации этой слабой курицы и закладки прочного фундамента.
Основная мысль
Пройдите массив и поместите наименьший (самый большой) элемент в начало массива,
Обработайте оставшиеся элементы как массив и снова выполните обход,
Получить наименьший (самый большой) элемент в начале массива
Предназначен для выбора наименьшего (наибольшего) элемента каждый раз при обходе нового массива.
Анимированный пример
Анализ сложности алгоритма
средний | худший | самый | стабильность | космическая сложность |
---|---|---|---|---|
O(n^2) | O(n^2) | O(n^2) | нестабильный | O(1) |
p.s. В лучшем случае: т. е. без замены элементов, но все же сравнения. Количество сравнений n(n-1)/2 раза
Код
import java.util.Arrays;
import java.util.Random;
/**
* Selection Sort
* 遍历数组,把最小(大)的元素放在数组首部,
* 把剩下的元素看做一个数组,再次遍历,
* 获得最小(大)的元素放在数组首部
* 意在每次遍历新数组选择出最小(大)元素
* <p>
* 算法复杂度分析
* 比较次数 n(n-1)/2 次
* 时间复杂度(平均) O(n^2) 外循环n次,内循环m次 m*n
* 时间复杂度(最坏) O(n^2) 外循环n次,内循环m次 m*n
* 时间复杂度(最好) O(n^2) 即不用元素交换,但仍要进行比较
* 空间复杂度 O(1)
* 稳定性 不稳定
*
* @author Wayne Zhang
* @date 2018/07/14
*/
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));
}
}
Ссылаться на
Гик для гиков: https://www.geeksforgeeks.org/selection-sort/
10 лучших классических алгоритмов сортировки: https://www.cnblogs.com/onepixel/articles/7674659.html
«Структура данных Dahua»: https://book.douban.com/subject/6424904/