一、直接插入排序

每次将一个待排序的序列插入到一个前面已排好序的子序列当中
使用到了顺序查找

图片演示

前面是有序的，逐步逐步将后面的插入到前面去

实现步骤

初始$L[1]$ 是一个已经排好序的子序列
对于元素$L(i)(L(2)\sim L(n)$插入到前面已经排好序的子序列当中

1. 查找出 $L(i)$ 在 $L[1...i-1]$ 中应该插入的位置 $k$
2. 将$L[k...i-1]$中所有元素全部后移一个位置
3. 将$L(i)$复制到$L(k)$

例子

*图片来自菜鸟教程

关于选择排序的参数

1、时间复杂度

最好$O(n)$ 所有元素有序，一开始就是有序的

平均$O(n^2)$

最坏$O(n^2)$ 想要递增的，结果是递减的序列

2、空间复杂度

$O(1)$

3、是否稳定

稳定

4、适用于何类型存储

顺序存储和链式存储

5、优缺点

优点 : 稳定，相对于冒泡排序与选择排序更快；
缺点 : 比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量大的时候；

代码实现

C++:

void InsertSort(ElemType A[],int n){  //定义一个数组A，所有元素的个数n
    int i,j;		//
    for(i=2;i<=n;i++){
        A[0]=A[i];	//类似哨兵的概念 1、判断是否已经插入到了最后 2、保存临时插入的值
        for(j=i-1;A[0].key < A[j].key;j--) //从后往前找合适的位置，如果当前的值比我们要插入的值大，则向后移动一个位置
            A[j+1] = A[j];
        A[j+1] = A[0];  // 把A[0]中保存的要插入的元素的值放到A[j+1]中
    }
}

二、折半插入排序

折半插入算法是对直接插入排序算法的改进，排序原理同直接插入算法
使用到了折半查找，折半查找相比直接插入排序的顺序查找，效率更高

关于折半查找

又称二分查找，仅适用于有序的顺序表（存放数组中
折半査找只适用于顺序存储，且要求序列一定有序。

1、算法思想

首先将给定值 key 与表中中间位置元素的关键字比较

若相等，则返回该元素的位置

若不等，则在前半部分或者是后半部分进行查找

2、代码实现

int Binary_Search(SeqList L, ElemType key){
    int low = 0,high = L.TableLen-1,mid; //第一个元素，最后一个元素，中间元素的位置
    while(low<=high){   // 如果low > high，则已经查找结束了
        mid = (low+high)/2;
        if(L.elem[mid] == key)
            return mid;
        else if(L.elem[mid]>key) //在前半部分
            high = mid-1;
        else		//在后半部分
            low = mid+1;
    }
    return -1;
}

插入排序实现步骤

见代码实现

关于折半插入排序的参数

1、时间复杂度

$O(n^2)$

2、空间复杂度

$O(1)$

3、是否稳定

稳定——不影响相对顺序，相同的话会插入到后面

4、使用于何类型存储

顺序存储

折半插入代码实现

C++:

void BInsertSort(ElemType A[],int n){		// 存放所有元素的数组A[],数组大小n
    int i,j;		// 辅助变量
    int low,high,mid;	// 辅助变量
    for(i=2;i<=n;i++){		//向前插入
        A[0] = A[i];		// 哨兵，1、判断是否插入结束	2、保存插入的值
        // ------------折半查找----------
        low = 1; high = i-1;
		while(low<=high){	// 如果是折半查找，相等的时候就应该退出循环了（此时low=high），但这里没有
   			 mid=(low+high)/2;	// 找到了的话，mid,high,low会指向同一个位置
    		if(A[mid].key > A[0].key)
                high = mid - 1;
    		else
        		low = mid + 1;
		}
        // ------------折半查找----------
        // 移动
        for(j=i-1;j>=high+1;j--)
            A[j+1] = A[j];
        A[high+1] = A[0];		// high+1 是最后插入的位置 high+1 也可以用low代替
    }
}

观察他们间的小差别
这是插入排序：

void InsertSort(ElemType A[],int n){  //定义一个数组A，所有元素的个数n
    int i,j;		//
    for(i=2;i<=n;i++){
        A[0]=A[i];	//类似哨兵的概念 1、判断是否已经插入到了最后 2、保存临时插入的值
        for(j=i-1;A[0].key < A[j].key;j--) //从后往前找合适的位置，如果当前的值比我们要插入的值大，则向后移动一个位置
            A[j+1] = A[j];
        A[j+1] = A[0];  // 把A[0]中保存的要插入的元素的值放到A[j+1]中
    }
}

这是折半查找：

int Binary_Search(SeqList L, ElemType key){
    int low = 0,high = L.TableLen-1,mid; //第一个元素，最后一个元素，中间元素的位置
    while(low<=high){   // 如果low > high，则已经查找结束了
        mid = (low+high)/2;
        if(L.elem[mid] == key)
            return mid;
        else if(L.elem[mid]>key) //在前半部分
            high = mid-1;
        else		//在后半部分
            low = mid+1;
    }
    return -1;
}

基本上就是在直接插入排序移动元素前，插入了一个折半查找，提升查找效率
其中的小区别，就是：折半查找是找到key值相等的那个元素的位置，而在折半插入排序中，使用到折半查找的目的，是找到应该插入的位置，并不需要key值相同

所找到的位置就是high+1

而为什么是high+1，而不是low+1，或者mid+1呢？

实际上用low也是可以的
观察中间的while循环，在最后一次循环的时候的时候，low == high
此时，low , high , mid 三者是同一个值
两种情况

if(A[mid].key > A[0].key)
    high = mid - 1;
else
    low = mid + 1;

（1）如果mid的key 大于我们要插入的值的key，那么情况是

（2）如果mid的key 小于我们要插入的值的key，那么情况是

最后

以上就是腼腆盼望为你收集整理的直接插入排序以及折半插入排序详解一、直接插入排序二、折半插入排序的全部内容，希望文章能够帮你解决直接插入排序以及折半插入排序详解一、直接插入排序二、折半插入排序所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。