C语言必学的12个排序算法：折半插入排序（第2篇）

悠悠 2023-03-03 15:30 2阅读 0赞

# 基本思想 #

直接插入排序实现简单，但是对于待排数据量较大时，时间性能差，因此可以对其改进。

改进排序算法性能，无外乎从减少“比较”和“移动”操作次数，折半插入排序是其中一种改进，插入排序需要在有序子表查找合适的位置，此时可以使用折半查找的方式实现，减少比较次数。

折半查找，举例来说明：

对于9个数据的有序数据表：(1,2,3,4,6,7,8,9,10)，给定一个数据5，如何查找合适的位置插入，保持数据表有序。

1.首先有序表长折半9/2=4，可以和第4个数据4比较，发现5大，因此5的位置肯定在有序表后一半(6,7,8,9,10)中；

2.再次在(6,7,8,9,10)中折半5/2=2，5可以和第2个数据7比较，发现5小，因此5的位置肯定在有序表前一半(6,7)中；

3.再次在(6,7)中折半2/2=1，5可以和第1个数据6比较，发现5小，因此5的位置肯定有序表前一半中，此时前一半已经没有数据，因此可以直接插入，5就插入到6的前面。

# 算法性能 #

空间复杂度和直接插入排序一致，时间复杂度同样是O(n^2)，但是与直接插入排序相比，关键字比较的次数减少。

# 代码实现 #

/*
    #include <stdio.h>
    
    // a[0]临时辅助空间，数据从a[1]开始 
    void binary_insert_sort(int a[], int length)
    {
      int i,j,m,t;
      // 临时变量保存折半查找位置
      int low,high; 
      for(i=1; i<length; i++)
      {
        if(a[i] < a[i-1] )
        {
          t = a[i];
          // 在有序子表折半查找
          // 1..i-1 是有序的 
          low = 0;
          high = i-1;
          while(low <= high)
          {
            m = (low + high)/2;
            if(t < a[m])
              high = m - 1;
            else
              low = m + 1; 
          }
          // 移动位置
          // 使用low或high均等价 
          // for(j=i-1; j>=high+1; j--)
          //   a[j+1] = a[j]; 
          // a[high+1] = t;
          
          for(j=i-1; j>=low; j--)
            a[j+1] = a[j]; 
          a[low] = t;
        }
      }
    }
    int main(void)
    {
      // a[0] 不保存数据 
      // a[0] 初始化为0仅为方便，不参与排序 
        int a[10] = {4,3,1,2,6,5,0,9,8,7};
        binary_insert_sort(a,10);
        int i;
        for(i=0; i<10; i++)
          printf("%d ", a[i]);
        return 0;
    }

其实做为一个学习者，有一个学习的氛围跟一个交流圈子特别重要这里我推荐一个C/C++基础交流583650410，不管你是小白还是转行人士欢迎入驻，大家一起交流成长。  
![format_png][]  
![format_png 1][]

[format_png]: /images/20230208/89724f453ca645968608e26b3876c85b.png
[format_png 1]: /images/20230208/761c6bc515bf4190bbb5c92a5f4fac16.png