02. 最简单的排序算法——选择排序
“ 每次都只拿最小的出来。”
01
—
洗牌与发牌
周末打牌斗地主，刚刚使用了《线性查找》将广告牌进行定位，对广告牌拿出来了，现在需要进行洗牌与发牌（假设你不是地主，一共要发给你17张牌）。
下面创建一个纸牌工具类，其中包含了一个54张牌的整型数组，一个洗牌的方法（ruffle）和一个发牌的方法（dealCards）。
// 纸牌类class CardUtil{//为了方便用数字表示，规定14表示小王，15表示大王static int[] cards = {1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,6,6,6,6,7,7,7,7,8,8,8,8,9,9,9,9,10,10,10,10,11,11,11,11,12,12,12,12,13,13,13,13,14,15};// 洗牌public static int[] ruffle(){//生成随机数的类 其中 nextInt(n) 方法可以生成 [0,n)区间的数字Random rnd = new Random();//思路：将数组最后一个数和前面随机位置的数交换。for (int i=cards.length; i>1; i--){int j = cards[rnd.nextInt(i)];int tmp = cards[i-1];cards[i-1] = cards[j];cards[j] = tmp;}return cards;}//发牌public static int[] dealCards(int[] oriCard,int num){int [] myCards = new int[num];for(int i = 0;i<num;i++){myCards[i] = cards[i];}return myCards;}}
现在写个Main方法测试一下这个工具类好不好用。
public class SelectionSort {public static void main(String[] args) {//工具类的方法因为用 static 修饰所以不需要new对象//洗牌int[] cards = CardUtil.ruffle();System.out.println( Arrays.toString(cards));//发牌、int[] myCards =CardUtil.dealCards(cards,17);System.out.println(Arrays.toString(myCards));}}——————————————[][]Process finished with exit code 0
02
—
选择排序法
现在发到你手中有17张牌，都是乱序的，为了更好地管理牌型，首先要将手中的牌从小到大排好序。
选择排序法，提供了一种思路，就是每次拿出最小的一张牌进行排序。
1）从左边第一张牌开始到最后一张牌进行扫描，拿出最小的牌，放到最左边。
2）从左边第二张牌开始到最后一张牌进行扫描，拿出最小的牌，放到左边第二位。
3）从左边第三张牌开始到最后一张牌进行扫描，拿出最小的牌，放到左边第三位。
……
16）从左边第十六张牌开始到最后一张牌（第十七张牌）进行扫描，拿出最小的牌，放到左第十六位。
因为数组最左边的索引是0，再小不能小过0，所以如果拿出最小的牌放到最左边，就只能放到索引为0的位置，而为了保留索引为0位置上的值，只能交换到最小的牌所在的最初位置上。
03
—
代码实现
// 选择排序public class SelectionSort {public void sort(int[] arr){// 每次循环只做一件事：将最小值放到 i 所在的位置for(int i =0 ; i<arr.length ;i++){//1. 找到最小的值int minIndex = i;for(int j =i;j<arr.length;j++){if(arr[j]<arr[minIndex]){minIndex = j;}}//2. 交换位置：将最小值插到 i 这个位置int tmp = arr[minIndex];arr[minIndex] = arr[i];arr[i] = tmp;}}}// 测试选择排序class TestSelectionSort{public static void main(String[] args) {//洗牌int[] cards = CardUtil.ruffle();System.out.println( Arrays.toString(cards));//发牌、int[] myCards =CardUtil.dealCards(cards,17);System.out.println(Arrays.toString(myCards));//整理牌SelectionSort selectionSort = new SelectionSort();selectionSort.sort(myCards);System.out.println(Arrays.toString(myCards));}}————————————————————————————————————[][][]Process finished with exit code 0
小结：
1）数组arr的索引是：[0,n) —— n是数组的长度；左闭右开是，包含0，不包含n。
2）for循环的每一次目的，就是在数组 arr[i,n) 当中找到最小的值，并将其与 arr[i] 进行交换。
3）也就是说：每次for循环前，arr[0,i) 是排好序的，而arr[i,n) 是未排序状态，每次循环就是为 arr[i] 找到合适的值。