选择排序

1.选择排序概念

将数组分为两个子集，排序的和未排序的，每一轮从未排序的子集中选取最小的元素，放入排序子集；
重复此操作，直至排序完成。
举个例子：

int[] a = {5, 3, 7, 2, 1, 9, 8, 4};

从头遍历所有元素，找到最小元素1，将1与原数组第一个元素交换位置，此时a数组为a = {1, 3, 7, 2, 5, 9, 8, 4}；
因为第一个元素已经为最小，故从第二个元素开始比较，找到最小元素2，将2与原数组第二个元素也就是3交换位置；
以此类推......

2.编程思路

1. 定义 i 为每轮选择最小元素要交换的目标索引
2. 遍历数组a
3. 定义 s 为最小元素的索引
4. 如果a[s] > a[j]，则将 j 的值赋给 s 
5. 后面的循环就以 s+1 为起点，不再重复遍历所有数据

3.代码实现

package array;

import java.util.Arrays;

import static array.BubbleSort.swap;

/**
 * @author: 邹祥发
 * @date: 2021/10/14 12:51
 * 选择排序
 */
public class SelectionSort {
    public static void main(String[] args) {
        int[] a = {5, 3, 7, 2, 1, 9, 8, 4};
        selection(a);
    }

    private static void selection(int[] a) {
        //i 表示每轮选择最小元素要交换的目标索引
        for (int i = 0; i < a.length - 1; i++) {
            // s 代表最小元素的索引
            int s = i;
            for (int j = s + 1; j < a.length; j++) {
                if (a[s] > a[j]) {
                    s = j;
                }
            }
            if (s != i) {
                swap(a, s, i);
            }
            System.out.println(Arrays.toString(a));
        }
    }
}

运行结果：
[1, 3, 7, 2, 5, 9, 8, 4]
[1, 2, 7, 3, 5, 9, 8, 4]
[1, 2, 3, 7, 5, 9, 8, 4]
[1, 2, 3, 4, 5, 9, 8, 7]
[1, 2, 3, 4, 5, 9, 8, 7]
[1, 2, 3, 4, 5, 7, 8, 9]
[1, 2, 3, 4, 5, 7, 8, 9]

4.优化

优化方式：为减少交换次数，每一轮可以先找最小的索引，在每轮最后再交换元素。
上述代码已经进行优化。

5.选择排序与冒泡排序比较

1.二者时间复杂度都是O(n²)。
2.选择排序一般要快于冒泡，因为其交换次数少。
3.如果集合有序度高，则冒泡优于选择。
4.冒泡属于稳定排序算法，而选择属于不稳定排序

6.稳定性排序与不稳定性排序区别？

先来看一段代码：

package array;

import java.util.*;

/**
 * @author: 邹祥发
 * @date: 2021/10/14 13:23
 */
public class StableVsUnstable {
    public static void main(String[] args) {
        System.out.println("=================不稳定================");
        Card[] cards = getStaticCards();
        System.out.println(Arrays.toString(cards));
        selection(cards, Comparator.comparingInt((Card a) -> a.sharpOrder).reversed());
        System.out.println(Arrays.toString(cards));
        selection(cards, Comparator.comparingInt((Card a) -> a.numberOrder).reversed());
        System.out.println(Arrays.toString(cards));

        System.out.println("=================稳定=================");
        cards = getStaticCards();
        System.out.println(Arrays.toString(cards));
        bubble(cards, Comparator.comparingInt((Card a) -> a.sharpOrder).reversed());
        System.out.println(Arrays.toString(cards));
        bubble(cards, Comparator.comparingInt((Card a) -> a.numberOrder).reversed());
        System.out.println(Arrays.toString(cards));
    }

    public static void bubble(Card[] a, Comparator<Card> comparator) {
        int n = a.length - 1;
        while (true) {
            int last = 0; // 表示最后一次交换索引位置
            for (int i = 0; i < n; i++) {
                if (comparator.compare(a[i], a[i + 1]) > 0) {
                    swap(a, i, i + 1);
                    last = i;
                }
            }
            n = last;
            if (n == 0) {
                break;
            }
        }
    }

    private static void selection(Card[] a, Comparator<Card> comparator) {
        for (int i = 0; i < a.length - 1; i++) {
            // i 代表每轮选择最小元素要交换到的目标索引
            int s = i; // 代表最小元素的索引
            for (int j = s + 1; j < a.length; j++) {
                if (comparator.compare(a[s], a[j]) > 0) {
                    s = j;
                }
            }
            if (s != i) {
                swap(a, s, i);
            }
        }
    }

    public static void swap(Card[] a, int i, int j) {
        Card t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    enum Sharp {
        diamond, club, heart, spade, black, red
    }

    static Card[] getStaticCards() {
        List<Card> list = new ArrayList<>();
        Card[] copy = Arrays.copyOfRange(Card.cards, 2, 13 * 4 + 2);
        list.add(copy[7]);
        list.add(copy[12]);
        list.add(copy[12 + 13]);
        list.add(copy[10]);
        list.add(copy[9]);
        list.add(copy[9 + 13]);
        return list.toArray(new Card[0]);
    }

    static Map<String, Integer> map = Map.ofEntries(
            Map.entry("RJ", 16),
            Map.entry("BJ", 15),
            Map.entry("A", 14),
            Map.entry("K", 13),
            Map.entry("Q", 12),
            Map.entry("J", 11),
            Map.entry("10", 10),
            Map.entry("9", 9),
            Map.entry("8", 8),
            Map.entry("7", 7),
            Map.entry("6", 6),
            Map.entry("5", 5),
            Map.entry("4", 4),
            Map.entry("3", 3),
            Map.entry("2", 2)
    );

    static class Card {
        private Sharp sharp;
        private final String number;
        private final int numberOrder;
        private final int sharpOrder;

        public Card(Sharp sharp, String number) {
            this.sharp = sharp;
            this.number = number;
            this.numberOrder = map.get(number);
            this.sharpOrder = sharp.ordinal();
        }

        private static final Card[] cards;

        static {
            cards = new Card[54];
            Sharp[] sharps = {Sharp.spade, Sharp.heart, Sharp.club, Sharp.diamond};
            String[] numbers = {"A", "K", "Q", "J", "10", "9", "8", "7", "6", "5", "4", "3", "2"};
            int idx = 2;
            for (Sharp sharp : sharps) {
                for (String number : numbers) {
                    cards[idx++] = new Card(sharp, number);
                }
            }
            cards[0] = new Card(Sharp.red, "RJ");
            cards[1] = new Card(Sharp.black, "BJ");
        }

        @Override
        public String toString() {
            switch (sharp) {
                case heart:
                    return "[\033[31m" + "♥" + number + "\033[0m]";
                case diamond:
                    return "[\033[31m" + "♦" + number + "\033[0m]";
                case spade:
                    return "[\033[30m" + "♠" + number + "\033[0m]";
                case club:
                    return "[\033[30m" + "♣" + number + "\033[0m]";
                case red:
                    return "[\033[31m" + "\uD83C\uDFAD" + "\033[0m]";
                case black:
                    return "[\033[30m" + "\uD83C\uDFAD" + "\033[0m]";
                default:
                    throw new IllegalArgumentException();
            }
        }
    }
}

输出结果：

首先看 "不稳定" 的第一行到第二行是按照花色排序的，而第二行到第三行则是按照降序排列。
为什么说它是不稳定的呢？
细心的朋友可以发现：第一行到第三行黑桃二和红桃二的位置变化。
结论：冒泡排序为稳定排序，就算是经历了先花色再降序的排序规则，黑桃二依旧在红桃二前面；
与之相反，选择排序为不稳定排序，经历了花色排序后再进行降序，无法保证其原来的规则。

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名，转载请标明出处。
最后编辑时间为: 2021/10/21 16:18:12