【排序算法】插入排序（C语言）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【排序算法】插入排序（C语言）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

一、插入排序的基本思想

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

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

void InsertSort(int* arr, int size)
{
	int i = 0;
	for (i = 1; i < size; i++)
	{
		//单趟排序
	}
}

二、插入排序的单趟排序

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

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

1. 直接插入排序

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

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

c语言插入排序,# 查找排序算法,排序算法,c语言,算法

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

c语言插入排序,# 查找排序算法,排序算法,c语言,算法

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

c语言插入排序,# 查找排序算法,排序算法,c语言,算法

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

c语言插入排序,# 查找排序算法,排序算法,c语言,算法

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;	//将数据放入插入位置
	}
}

2. 二分法插入排序

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

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

c语言插入排序,# 查找排序算法,排序算法,c语言,算法

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

c语言插入排序,# 查找排序算法,排序算法,c语言,算法

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

c语言插入排序,# 查找排序算法,排序算法,c语言,算法

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

c语言插入排序,# 查找排序算法,排序算法,c语言,算法

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

c语言插入排序,# 查找排序算法,排序算法,c语言,算法

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;
	}
}