03. 打牌中真实使用的排序——插入排序法
“ 每次只处理当下的元素。”
01
—
交换牌 VS 移动牌
周末，打斗地主，上次拿到发的乱序的17张牌，是使用——查找最小的牌交换到靠左的位置，实现的。
使用交换而不是直接插入的原因就是因为数组并不像手掌一样灵活，可以自动地向左或向右拓展空间，数组最开始开辟多大的空间，最多就能存储多少元素。
举例来讲，数组的最小索引就是0，第一次找到最小的牌需要放到最左边，因为不能开辟 -1 这个索引的空间，所以只能放到索引为 0 的位置，那原来在索引为 0 位置上的牌，就只能交换到最小牌原来所在的位置。
但是如果移动牌而不是交换牌呢？思路还是，只是将交换牌换成了移动牌：
1）从左边第一张牌开始，到最后一张牌进行扫描，拿出最小的牌，这时最小的牌所在的位置就空出来一位。
2）选中从左边第一张牌开始，到最小的牌最初所在位置的上一张牌为止的所有牌，同时向右平移一位，补全空出来一位，这时第一张牌最初所在的位置就空出来了。
3）将拿出来的最小牌放到第一位。
4）从左边第二张牌开始，到最后一张牌进行扫描，拿出最小的牌，这时最小的牌所在的位置就空出来一位。
5）选中从左边第二张牌开始，到最小的牌最初所在位置的上一张牌为止的所有牌，同时向右平移一位，补全空出来一位，这时第二张牌最初所在的位置就空出来了。
6）将拿出来的最小牌放到第二位。
…………
但这有一个问题，在都使用全盘（未排序的部分）扫描的时候，平移可能会比交换位置多出来很多步骤，例如如果第一次全盘扫描的时候，最小的牌正好在最后一位，这时如果使用平移就要将所有的牌都右移一位，而如果使用交换牌的话，固定就是三个步骤，无论最小的牌在哪。
02
—
插入排序
选择排序，每次都要扫描右边未排好序的全部牌张，从而找到其中最小的牌放到当下位置，如果不去扫描，而是和平时打牌一张一张摸牌一样， 摸到什么牌就是处理什么牌呢？
手中的牌是排好序的，摸到什么牌就是使用平移插入法将牌放到手中相应的位置。
如果将手中的牌看作排好序的左边部分，每次摸到的牌都是索引 i 位置上的元素，那插入排序就是，将索引 i 位置上的元素插入到左边排好序的部分。
1）处理左边第一张牌，不需要移动插入。
2）处理左边第二张牌，比较这张牌与前边的牌大小，如果比前边的牌大，不需要移动插入，如果比前边的牌小，就将前边的牌右移，将第二张牌插入到合适的位置。
3）处理左边第三张牌，比较这张牌与前边的牌大小，如果比前边的牌大，不需要移动插入，如果比前边的牌小，就将前边的牌右移，继续向前比较，直至第一张牌，将前边的比较大的牌右移，将第三张牌插入到合适的位置。
……
17）处理左边第张十七牌，比较这张牌与前边的牌大小，如果比前边的牌大，不需要移动插入，如果比前边的牌小，就将前边的牌右移，继续向前比较，直至第一张牌，将前边的比较大的牌右移，将第十七张牌插入到合适的位置。
03
—
代码实现
import java.util.Arrays;public class InsertionSort {public void sort(int[] arr){for(int i = 1; i< arr.length ;i++){//拿出待处理元素int pendingElm = arr[i];// 将 arr[i] 插入到合适的位置int j = i;while(j-1 >= 0 && arr[j-1] > pendingElm){// 向右平移arr[j] = arr[j-1];j--;}// 插入到相应的位置。arr[j] = pendingElm;}}}class TestInsertionSort{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));//整理牌InsertionSort insertionSort = new InsertionSort();insertionSort.sort(myCards);System.out.println(Arrays.toString(myCards));}}————————————[][][]// 整理好的牌：两个A，有个炸弹，6-12顺子缺一个 10，// 分析：这样的牌型适合作为门板位置，抗地主的牌，有机会炸弹送队友胜利Process finished with exit code 0
总结：
1）选择排序和插入排序相同点，都是索引 i 所在位置的左边是排好序的， 右边是待排序的。
2）选择排序，是每次都只处理当下 索引 i 的位置，在 i 的右边找到合适的牌放到 i 上。
3）插入排序，是每次都只处理当下 索引 i 位置上的牌，在 i 的左边找到合适的位置，插进入。