【21天算法学习】折半插入排序

作者简介：

🍀姓姜，字君竹。

🍁浅薄观点：科以载文，文以载道

🌱软件技术升计科，计划考研

🌾要有最朴素的生活和最遥远的梦想，即使明日，天寒地冻，路遥马亡

1.概念及介绍

 折半插入排序与直接插入排序算法原理相同。只是，在向已排序的数据中插入数据时，采用来折半查找（二分查找）。先取已经排序的序列的中间元素，与待插入的数据进行比较，如果中间元素的值大于待插入的数据，那么待插入的数据属于数组的前半部分，否则属于后半部分。依次类推，不断缩小范围，确定要插入的位置。

 折半插入排序相对稳定，相对于直接插入排序，减少了比较次数；但是相对直接插入排序，移动次数不变。

2.时间空间复杂度

 对于折半插入排序来说，由于元素的串位次数没有发生改变，只是在查找位置是更加快速了，所以与直接插入排序处于同一量级，在数据量很大时，要优于直接插入排序。

 如果输入的元素刚好是反向有序的，那么每次都需要进行位置的查找，但是在查找的次数要少一些。所以时间复杂度为O(n2)；最好的情况就是与直接插入排序相同，如果元素已经是正向有序的，呢么最开始比较的时候就会认为是在适合的位置，不需要再进行位置的寻找和串位，因此时间复杂度为O(n)。正常情况下折半插入排序的时间复杂度为O(n2)。

 算符执行过程中直接在元集合上操作，只需要几个额外的变量记录关键信息，所以空间复杂度为常数级O(1)。

3.图解

1. 代码实现
   

int main() {
  int a[] = { 1, 12, 35, 54, 13, 21, 34, 56, 78, 22, 11 };
  int i = 0;
  int sz = sizeof(a) / sizeof(a[0]);
  for (i = 1; i < sz; i++) {
    int tmp = a[i];
    int left = 0;
    int right = i - 1;
    int j = 0;
    while (left <= right) {
      int mid = (right - left) / 2 +left;
      if (a[mid] > tmp) {
        right = mid - 1;
      }
      else{
        left = mid + 1;
      }
    }
    for (j = i - 1; j >= right + 1; j--) {
      a[j + 1] = a[j];
    }
    a[right + 1] = tmp;
  }
  for (i = 0; i < sz; i++) {
    printf("%d ", a[i]);
  }
  return 0;
}

学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰。