sort:如同整理手牌般的排序

当你在玩扑克之时，庄家发牌的时候，你是怎么处理手上的牌呢？

---

假如现在你的手牌是3 5 9 10，这个时候，来了一张8，你会怎么将手牌处理好呢？插入排序？冒泡排序？堆排序？其实，只需要将这张8插入到5和9中间就可以了。

没错，这就是插入排序。和整理手牌的思路是一样的。

首先，我们维护一个有序区，在这个有序区当中，所有的数字都是有序的。然后，我们按顺序从无序区中得到一个数字，然后，查找这个数字应该在的位置，然后，插入的这个位置当中去。

1 4 7 3

比如，☝这个的有序区是1 4 7，那么我们只需要将7和3对比，顺序不对就交换，然后继续对比下一组(3,4)，直到顺序是正确的时候，就能够插入到想要的位置了，同时，有序区的大小也增加了1，等到有序区有整个数组那么大的时候，排序也就结束了。

vector<int> sortArray(vector<int>& nums) {
      //一开始，最左边的元素作为有序区，然后不断的进行插入
      for(int i = 1;i < nums.size();i++)
      {
          int insertValue = nums[i];
          int j = i - 1;
          for(;j >= 0 && insertValue < nums[j];j--)
          {
              nums[j+1] = nums[j];
          }
          nums[j+1] = insertValue;
      }

      return nums;
  }

这个算法的最坏和平均时间复杂度都是O(n^2)，由于是原地排序因此空间复杂度为O(1)。不过，在大量元素有序的情况下，插入排序的性能还是不错的。因为，在大量有序的情况下，有序区的增长是十分的快的，甚至不需要进行插入操作就可以直接扩张有序区了。

因此，插入排序有时候也是快速排序的一种代替手段。