【排序算法】插入排序（C语言）

【排序算法】—— 插入排序

一、插入排序的基本思想

​ 直接插入排序是一种简单的插入排序法，对数组进行一个遍历，每次都对待排的数据按照大小顺序插入到一个有序数组中的特定位置，直到所有的数据全部插入完毕，就得到一个有序数列。

​ 插入排序的算法非常简单，依次对每一个元素进行单趟排序就行了，由于要前一个数比较则只需要从1开始遍历n-1次，代码如下：

void InsertSort(int* arr, int size)
{
	int i = 0;
	for (i = 1; i < size; i++)
	{
		//单趟排序
	}
}
1
2
3
4
5
6
7
8

二、插入排序的单趟排序

​ 直接插入排序的单趟排序是将当前数值插入到有序序列的指定位置，我们通过当前位置开始从后往前遍历数组，将数值向前移动，直到移动到该数据的指定位置，就完成单趟排序。

​ 由于被插数组是有序的，所以可以顺序向前比较找到插入位置，这种方法称为直接插入排序，也可以通过二分查找找到插入位置，称为二分法插入排序

1. 直接插入排序

​ 每一次比较都将待排数据向前移动一格，直到插入到指定位置

1. 如图，当前待排数据为i指向的数据4，则要将4插入到[2 3 5 6 8]中使其构成有序数组，变量end从当前位置开始遍历

2. end向前移动，4比8小，则8向后移动一格，4插入到8的前面

3. end接着向前移动，与前一个进行比较，4比6小，则6向后移动一位，4插入到6的前面

4. end继续遍历，直到遇到比4小的数停止插入，此时单趟排序排序完成

void InsertSort(int* arr, int size)
{
	int i = 0;
	for (i = 1; i < size; i++)
	{
	    int end = i;
        int temp = arr[end];	//记录待排数值
        while (end > 0)
        {
            if (arr[end-1] > temp)	//若前一个数大于待排数值，则后移一位
            {
                arr[end] = arr[end-1];
            	end--;
            }
            else
            {
                break;
            }
        }
        // arr[end-1] = temp;是之前的错误，现已修正
        arr[end] = temp;	//将数据放入插入位置
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2. 二分法插入排序

​ 利用二分查找法查找出插入位置，并将有序数组中插入位置后的数据后移一位，空出插入位置插入数据

1. 定义left和right指针，分别指向有序数组的开头和末尾，计算出中间数据的值与待排数据4比较

2. 中间数值5大于4，则right从mid-1处开始，查找区间缩小一半，计算出中间值

3. 中间值2小于4，则left从mid+1处开始，计算出中间值

4. 中间值3小于4，则left从mid+1处开始，但是此时left大于right，所以循环停止，left的位置就是插入位置

5. 将待排数据之前，left后的数据全部后移一位，空出插入位置，并插入数据，排序完毕

void BInsertSort(int* arr, int size)
{
    int i = 0;
	for (i = 1; i < size; i++)
	{
        int left = 0;
        int right = i - 1;
        
        //查找插入位置
        while (left <= right)
        {
            int mid = (left + right) / 2;
            if (arr[i] < arr[mid])
            {
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }
        
        //后移数据并插入
        int temp = arr[i];
        for (right = i; right > left; right--)
        {
            arr[right] = arr[right-1];
        }
        arr[left] = temp;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

三、插入排序的特点和效率

1. 插入排序的特点

直接插入排序：

1. 越有序的数组单趟移动的次数越少，完全有序的数组时间复杂度只有$O(n)$
2. 插入排序是稳定的排序（相同元素排序时不破坏原来的位置，不稳定对结构体类型数据有影响）

二分法插入排序：

1. 二分法插入排序面对大量数据时能减少数据的比较次数，有效提高时间效率
2. 二分法插入排序也是稳定的

2. 插入排序的效率

​ 时间复杂度：$O(n^2)$

​ 空间复杂度：$O(1)$