转载

数据结构图文解析之：直接插入排序及其优化（二分插入排序）解析及C++实现

0. 数据结构图文解析系列

数据结构系列文章
数据结构图文解析之：数组、单链表、双链表介绍及C++模板实现
数据结构图文解析之：栈的简介及C++模板实现
数据结构图文解析之：队列详解与C++模板实现
数据结构图文解析之：树的简介及二叉排序树C++模板实现.
数据结构图文解析之：AVL树详解及C++模板实现
数据结构图文解析之：二叉堆详解及C++模板实现
数据结构图文解析之：哈夫曼树与哈夫曼编码详解及C++模板实现
数据结构图文解析之：直接插入排序及其优化（二分插入排序）解析及C++实现

1. 插入排序简介

插入排序是一种简单直观的排序算法，它也是 基于比较 的排序算法。它的工作原理是通过不断扩张有序序列的范围，对于未排序的数据，在已排序中从后向前扫描，找到相应的位置并插入。插入排序在实现上通常采用 就地排序 ，因而 空间复杂度为O（1） 。在从后向前扫描的过程中，需要反复把已排序元素逐步向后移动，为新元素提供插入空间，因此插入排序的 时间复杂度为O（n^2） ;

2. 直接插入排序图解

一般来说，插入排序都采用在数组上就地排序实现。具体算法描述如下：

从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤2~5

假设我们要对数组{12，4，5，2，6，14}进行插入排序，排序过程为：

2.1. 代码实现

template <typename T> void InsertSort(T array[],int length) {     if (array == nullptr || length < 0)         return;     int i, j;     for (i = 1; i < length; i++)     {         if (array[i]<array[i - 1])         {             int temp = array[i];                  for (j = i - 1; array[j]>temp; j--) //元素后移             {                 array[j + 1] = array[j];             }             array[j+1] = temp;        //在合适的位置上出入元素         }     } }

2.2. 复杂度分析

插入排序的最好情况是数组已经有序，此时只需要进行n-1次比较，时间复杂度为O（n）;
最坏情况是数组逆序排序，此时需要进行n(n-1)/2次比较以及n-1次赋值操作（插入）；
平均来说插入排序算法的复杂度为O(n^2)。

插入排序不适合对大量数据进行排序应用，但排序数量级小于千时插入排序的效率还不错，可以考虑使用。插入排序在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序（通常为8个或以下）。

直接插入排序采用就地排序，空间复杂度为O（1）.

2.3. 稳定性

直接插入排序是稳定的，不会改变相同元素的相对顺序。

3. 二分查找插入排序

上面的插入排序实现中，为了找到元素的合适的插入位置，我们采用从后到前遍历的 顺序查找 进行比较，为了减少比较的次数，我们可以换种查找策略：采用 二分查找 。

我们定义一个二分查找函数，函数返回插入位置的下标：

/*二分查找函数，返回插入下标*/ template <typename T> int BinarySearch(T array[], int start, int end, T k) {     while (start <= end)     {         int middle = (start + end) / 2;         int middleData = array[middle];         if (middleData > k)         {             end = middle - 1;         }         else             start = middle + 1;     }     return start; } //二叉查找插入排序 template <typename T> void InsertSort(T array[], int length) {     if (array == nullptr || length < 0)         return;     int i, j;     for (i = 1; i < length; i++)     {         if (array[i]<array[i - 1])         {             int temp = array[i];             int insertIndex = BinarySearch(array, 0,i, array[i]);//使用二分查找在有序序列中进行查找，获取插入下标             for (j = i - 1; j>=insertIndex; j--) //移动元素             {                 array[j + 1] = array[j];                }                    array[insertIndex] = temp;    //插入元素         }     } }