插入排序.

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

根据找插入位置的方法分为
①、顺序法定位插入位置——直接插入排序
②、二分法定位插入位置——二分插入排序
③、缩小增量多遍插入排序——希尔排序

一、直接插入排序以升序为例

先背模板

void insert_sort(int *a,int len)//传入数组和数组的长度
{
    for(int i = 1;i < len; i++)
    {
        int x = a[i];//复制一份a[i]的副本否则a[j]后移的时候会将a[i]覆盖
        int j = i - 1;//"i-1"表示已排序的有序数组的最后一个元素下标
        while(j >= 0 && a[j] > x)//注意判断条件为两个
        //j>=0对其进行边界限制第二个判断是否插入 k 这个元素
        {
            a[j + 1] = a[j];//若不是合适位置有序组元素向后移动
            j--;
        }
        a[j + 1] = x;//找到合适位置将元素插入。
    }
}

再看逻辑
动画演示请点击这里

时间复杂度 O(n^2)
空间复杂度 O(1)

二、折半插入排序

即采用折半二分查找的插入排序。

void insert_sort(int a[], int len){
	for (int i = 1; i < len; ++i){
		int x = a[i];
		int low = 0, high = i - 1;
		while(low <= high){
			int mid = (low + high) / 2;
			if (a[mid] > x) high = mid - 1;
			else low = mid + 1;
		}
		for (int j = i - 1; j >= high + 1; --j){
			a[j + 1] = a[j];
		}
		a[high + 1] = x;
	}
}

折半查找比顺序查找快且折半插入排序的比较次数与数据初始时的排列无关但直接插入排序与之有关

注
1、当n较大时折半插入的总比较次数比直接插入的最坏情况要好很多但比其最好情况要差
2、当数据的初始序列已经接近有序时直接插入的比较次数要比折半插入要少。
3、折半插入的移动次数与直接插入相同取决于数据的初始序列
4、综上折半插入总体上平均性能优于直接插入减少了比较次数但未减少移动次数。
5、折半插入的时间复杂度为O(n^2)空间复杂度为O(1)是一种稳定的排序。