算法学习之插入排序

本文主要是介绍算法学习之插入排序，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、总体思路

分成两个区域：排好序区（数组前面部分，绿色部分） + 待排序区（数组后面部分，黑色部分）。

不断将后面未排序区的数据往已排序区插入，使得已排序区不断扩大。

初始时刻：已排序区只有一个数。

每趟：尝试将未排序区第一个元素插入已排序区，具体做法：从已排序区末尾元素开始往前遍历，若未排序区第一个元素比之小，则可以加入已排序区，且需从已排序区腾出一个位置出来。

如上：A，B，C属于排好序区域，D及其之后为待排序区。将D及其之后的数据往A，B，C已排序区域插入。

二、优化

    从后往前遍历排序区过程中，若已经比元素大，则不用再往前遍历了，因为更前面的数更小，可以提前退出本趟查找，不用将排序区遍历完。

三、代码

// 插入排序
void InsertSort(int arrayData[], int arraySize)
{
	int i, j;

	for (i = 0; i < arraySize - 1; i++) {
		int tempValue = arrayData[i + 1];
		int tempIdx = i + 1;

		for (j = i; j >= 0; j--) {
			if (tempValue < arrayData[j]) {
				tempIdx = j;
				arrayData[j + 1] = arrayData[j];  // 往后移动空出位置
			} else if (tempValue > arrayData[j]) {
				break;  // 不用再往前比较了，前面存的更小
			}
		}

		if (tempIdx != i + 1) {
			arrayData[tempIdx] = tempValue;
		}
	}
}

这篇关于算法学习之插入排序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！