普通插入排序

• 算法思路

  整理桥牌时，我们会将每一张牌插入到一个已经有序的序列的适当位置。为了给要插入的元素腾出空间，需要我们将已经有序的序列元素都向右移动一位。

插入排序，以当前插入16为例.png

• 代码示例：

void InsertSort(vector<int> &vec) 
  {
      for (int i = 1; i < vec.size(); i++) 
      {
          int currentNum = vec[i];
          /* 找当前索引元素正确的插入位置 */
          int j = i-1;
          while(j >= 0 && currentNum < vec[j]) 
          {
              vec[j+1] = vec[j];
              j--;
          }
  
          vec[j+1] = currentNum;
      }
  }

• 特点

  • 插入排序和选择排序类似，都是当前索引左边的元素都是有序的，只是插入排序的左边元素的最终位置并不能确定，为了给后面的更小元素腾出空间，它们可能会被移动。

  • 插入排序不会访问当前索引右侧的元素，选择排序不会访问当前索引右侧的元素。

  • 插入排序所需要的时间取决于输入中元素的初始顺序，对一个很大且其中元素已经有序或接近有序时，插入排序会特别快。

  • 插入排序在最坏情况即逆序时，需要比较n(n-1)/2次。最好(顺序) 比较n-1次。

  • 总结

    平均时间	最差	最佳	辅助空间	稳定性
    O(n^2)	O(n^2)	O(n)	O(1)	稳定

希尔插入排序

• 算法思路

对于大规模的乱序数组插入排序很慢，因为它只会交换相邻的元素。因此元素只能一点一点地从数组的一端移到另一端。希尔排序的思想就是使数组中任意间隔为h的元素都是有序的，最后再采用普通的插入排序将局部有序的数组排好序。前文已提到普通插入排序对已经有序或接近有序的排序会特别快。

• 示例代码

  void ShellSort(vector<int>& vec)  
  {
      int N = vec.size();
      int h = 1;
      
      while (h < N/3)
          h = 3 * h + 1;
      
      while (h >= 1) 
      {
          for (int i = h; i < N; i++) 
              for (int j = i; j >= h && less(a[j], a[j - h]); j -= h)
                  swap(vec[j], vec[j-h]);
          h = h / 3;
      }
  }
  

• 特点

  • 希尔排序高效的原因是因为他权衡了子序列的规模和有序性，排序之初，各个子序列都很短，排序之后子序列都是有序的。这2种情况都很适合插入排序。

  平均时间	最差	最佳	辅助空间	稳定性
  O(n^1.5)	O(n^2)	O(n)	O(1)	不稳定