二分插入排序.md

二分插入排序

(一) 概念及其实现

二分查找插入排序的原理：是直接插入排序的一个变种，区别是：在有序区中查找新元素插入位置时，为了减少元素比较次数提高效率，采用二分查找算法进行插入位置的确定。

• 1.将原序列分成有序区和无序区。a[0…i-1]为有序区，a[i…n] 为无序区。（i从1开始）
• 2.从无序区中取出第一个元素，即a[i]，使用二分查找算法在有序区中查找要插入的位置索引j。
• 3.将a[j]到a[i-1]的元素后移，并将a[i]赋值给a[j]。
• 4.重复步骤2~3，直到无序区元素为0。

示例{123，126，165，226，272，312，123}：

123	28	126	165	226	272	312	123
0	1	2	3	4	5	6	7
	left = 1			mid = 3		right = 6

• 先保存带插入的排序码，123 < 126,right = mid - 1 = 2

123	28	126	165	226	272	312	123
0	1	2	3	4	5	6	7
	left = 1	right = 2
	mid = 1

• 123 !< 28 ,left = right + 1 = 2

123	28	126	165	226	272	312	123
0	1	2	3	4	5	6	7
		left = 2
		right = 2
		mid = 2

• 123 < 126,right = mid - 1 = 1,left > right，二分查找结束，left = 2即为查找位置

123	28		126	165	226	272	312
0	1	2	3	4	5	6	7

• left = 2为插入位置，后移，空出插入位置

123	28	123	126	165	226	272	312
0	1	2	3	4	5	6	7

• 在插入位置插入排序码，结束

代码

#include "stdio.h"
#include "stdlib.h"
#define MAXSIZE 100
typedef struct {
    int r[MAXSIZE + 1];
    int length;
}table;

//二分插入排序
void binarysort(table *tab)
{
    int i; //循环的基数
    int left, right, mid;
    for (i = 2; i <= tab->length; i++)  //依次插入从第二个开始的所有元素
    {
    tab->r[0] = tab->r[i];  //保存待插入的数到第一个缓存上
    left = 1, right = i - 1;  //设置查找范围的左右位置值
        while (left <= right)  //查找第i个元素的插入位置
        {
            mid = left + right / 2; //取中点的位置
            if (tab->r[i] < tab->r[mid])
                right = mid - 1;
            else
                left = mid + 1;  //插入位置为left
        }
        for (int j = i - 1; j >= left; j--)
            tab->r[j + 1] = tab->r[j];  //后移，空出插入位置
        tab->r[left] = tab->r[0];  //插入第i个元素的副本
    }
}

int main()
{
    table tab;
    int num = 0;
    tab.length = 0;
    printf("请输入想要排序的数的个数：\n");
    scanf("%d", &num);
    for (int i = 1;i <= num;i++)
    {
        scanf("%d",&tab.r[i]);
        tab.length++;
    }
    binarysort(&tab);
    for (int i = 1; i <= tab.length; i++)
        printf("%d ", tab.r[i]);
    system("pause");
    return 0;
}

(二)算法复杂度

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

二分查找插入位置，因为不是查找相等值，而是基于比较查插入合适的位置，所以必须查到最后一个元素才知道插入位置。

二分查找最坏时间复杂度：当2^X>=n时，查询结束，所以查询的次数就为x，而x等于log2n（以2为底，n的对数）。即O(log2n),所以，二分查找排序比较次数为：x=log2n

• 1)最好情况：查找的位置是有序区的最后一位后面一位，则无须进行后移赋值操作，其比较次数为：log2n 。即O(log2n)

• 2)最坏情况：查找的位置是有序区的第一个位置，则需要的比较次数为：log2n，需要的赋值操作次数为n(n-1)/2加上 (n-1) 次。即O(n^2)

• 3)渐进时间复杂度（平均时间复杂度）：O(n^2)

2.空间复杂度：O(1)

• 从实现原理可知，二分查找插入排序是在原输入数组上进行后移赋值操作的（称“就地排序”），所需开辟的辅助空间跟输入数组规模无关，所以空间复杂度为：O(1)

(三)稳定性

二分查找排序是稳定的，不会改变相同元素的相对顺序。

(四)与冒泡、直接插入排序复杂度对比

冒泡排序	直接插入排序	二分插入排序