Алгоритм сортировки: сортировка выбором

Java алгоритм

Sorting Algorithms:Selection Sort

предисловие

Этот блог используется для обзора и консолидации этой слабой курицы и закладки прочного фундамента.

Основная мысль

Пройдите массив и поместите наименьший (самый большой) элемент в начало массива,
Обработайте оставшиеся элементы как массив и снова выполните обход,
Получить наименьший (самый большой) элемент в начале массива
Предназначен для выбора наименьшего (наибольшего) элемента каждый раз при обходе нового массива.

Анимированный пример

Selection Sort
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/