0%

选择排序

发表于 更新于 分类于

选择排序是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。

基本思想

  1. 首先在未排序序列中找到最小元素，存放到排序序列的起始位置
  2. 再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾
  3. 重复步骤2，直到排序完成

动态图如下(来源：https://www.cnblogs.com/onepixel/articles/7674659.html)：

sort.jpg

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author gelong
 * @date 2020/6/4 23:18
 */
public class SelectionSort {

    private SelectionSort() {}


    public static <T> void sort(T[] data, Comparator<T> comparator) {
        for (int i = 0; i < data.length; i++) {
            int index = i;
            for (int j = i + 1; j < data.length; j++) {
                if (comparator.compare(data[index], data[j]) > 0) {
                    index = j;
                }
            }
            swap(data, i, index);
        }
    }

    private static <T> void swap(T[] data, int i, int j) {
        T temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    public static void main(String[] args) {
        Integer[] data = {3, 1, 2, 5, 4};
        sort(data, Integer::compareTo);
        System.out.println(Arrays.toString(data));
    }
}