—————  第二天  —————

————————————

人们如何进行扑克牌的排序呢？

举个例子，比如我手中有红桃6,7,9,10这四张牌，已经处于升序排列：

这时候，我又抓到了一张红桃8，如何让手中的五张牌重新变成升序呢？用冒泡排序，选择排序，亦或是快速排序？

恐怕正常人打牌的时候都不会那么做。最自然也最简单的方式，是在已经有序的四张牌中找到红桃8应该插入的位置，也就是7和9之间，把红桃8插入进去：

给定无序数组如下：

把数组的首元素5作为有序区，此时有序区只有这一个元素：

第一轮

让元素8和有序区的元素依次比较。

8>5，所以元素8和元素5无需交换。

此时有序区的元素增加到两个：

第二轮

让元素6和有序区的元素依次比较。

6<8，所以把元素6和元素8进行交换：

6>5，所以把元素6和元素5无需交换。

此时有序区的元素增加到三个：

第三轮

让元素3和有序区的元素依次比较。

3<8，所以把元素3和元素8进行交换：

3<6，所以把元素3和元素6进行交换：

3<5，所以把元素3和元素5进行交换：

此时有序区的元素增加到四个：

以此类推，插入排序一共会进行（数组长度-1）轮，每一轮的结果如下：

什么意思呢？让我们以第三轮举例：

在第三轮操作中，我们需要让元素3逐个与有序区的元素进行比较和交换，与8交换、与6交换、与5交换，最终交换到有序区的第一个位置。

但是我们并不需要真的进行完整交换，只需把元素3暂存起来，再把有序区的元素从左向右逐一复制。

第一步，暂存元素3：

第二步，和前一个元素比较，由于3<8，复制元素8到它下一个位置：

第三步，和前一个元素比较，由于3<6，复制元素6到它下一个位置：

第四步，和前一个元素比较，由于3<5，复制元素5到它下一个位置：

第五步，也是最后一步，把暂存的元素3赋值到数组的首位：

显然，这样的优化方法减少了许多无谓的交换。

1. public static void sort(int[] array){

2. for(int i=1;i<array.length;i++){

3. int insertValue =array[i];

4. int j=i-1;

5. //从右向左比较元素的同时，进行元素复制

6. for(; j>=0&&insertValue<array[j]; j--){

7. array[j+1]=array[j];

8. }

9. //insertValue的值插入适当位置

10. array[j+1]=insertValue;

11. }

12. }

13. 
    

14. public static void main(String[] args) {

15. int array[]={12,1,3,46,5,0,-3,12,35,16};

16. sort(array);

17. System.out.println(Arrays.toString(array));

18. }

最后，给大家推荐一本，不仅能帮你擦掉泪痕与皱纹，还能轻轻松松把算法学懂的灵药——《漫画算法：小灰的算法之旅》