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