Java教程

算法学习之插入排序

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

一、总体思路

分成两个区域:排好序区(数组前面部分,绿色部分) + 待排序区(数组后面部分,黑色部分)。

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

 

ABCDEFGH

 

 

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

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

 

ABCDEFGH

 

 

如上: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;
		}
	}
}

 

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