【数据结构周周练】032 折半插入排序算法原理详解及代码分享

今天药忘吃喽~ 2021-06-11 15:13 358阅读 0赞

## 一、折半插入排序 ##

### 1、折半插入排序简介 ###

直接插入排序是一种最简单的排序方法，简单但也慢。而折半插入排序（Binary Insertion Sort）是对直接插入排序算法的一种改进。主要有下面三个步骤：

1.从第二个元素开始插入，与前面元素中中间元素比较，即折半比较。
    	2.比中间元素大，同样方法比较后半部分；比中间元素小，同样方法比较前半部分；直到 low > high 时跳出循环，即找到该位置，即low所在位置。
    	3.找到位置后，从i的前一个元素开始后移，

这个算法原理是也是比较简单的，同时是一个稳定的算法。这个算法只适用于顺序表，它仅仅是提升了平均比较元素次数，**该算法的比较次数与排序表的初始状态无关**，仅仅取决于元素个数n，但是移动次数并没有变，希望大家能够掌握。

### 2、算法思想及流程 ###

排序时，从第二个数据开始，与其前面数据作比较。主要做如下几个步骤：

1.用中间变量暂存该数据。

2.将该数据与前面数据中间数据作比较，比中间元素大，同样方法比较后半部分；比中间元素小，同样方法比较前半部分；直到 low > high 时跳出循环，即找到该位置，即low所在位置。

3.从该元素所在位置的前一个元素开始后移，直到low位置。

## 二、全部代码 ##

刚才上面是分析，接下来我将所有的代码分享一下。

#include<iostream>
    using namespace std;
    
    
    void InsertSort(int Arr[], int length) {
    	int i, j, low, high, mid, temp;
    	for ( i = 1; i < length; i++)
    	{
    		temp = Arr[i];
    		low = 0;
    		high = i - 1;
    		while (low<=high)
    		{
    			mid = (low + high) / 2;
    			if (Arr[mid] > temp)
    				high = mid - 1;
    			else
    				low = mid + 1;
    		}
    		for (j = i - 1; j >= low; j--)//查找位置，并后移
    			Arr[j + 1] = Arr[j];
    		Arr[high + 1] = temp;
    
    	}
    }
    
    void OutputArr(int Arr[], int length) {
    	for (int i = 0; i < length; i++)
    	{
    		cout << Arr[i] << ", ";
    
    	}
    	cout << endl;
    }
    
    void main() {
    	int Arr[] = { 45,57,12,31,1,60,92,71,87 };
    	InsertSort(Arr, 9);
    	OutputArr(Arr, 9);
    }

## 三、结果 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_22_color_8F879F_t_70][]

大家有什么问题在下面留言哦！！！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_22_color_8F879F_t_70]: /images/20210516/49cccbb42b884ff1a18ee8234cb1c09f.png