算法-插入排序(insetion sort)

插入排序(insetion sort),就是将每个带排序序元素逐个插入到有序元素序列中的合适位置。

function insertSortBasic(aArr){
	var	iLength = aArr.length,
		i,
		j,
		k,
		mTemp;
	for(i = 1; i < iLength; i++){
		//在已排好序的序列中找合适的位置
		for(j = i - 1; j >= 0; j--){
			if(aArr[j] < aArr[i]){
				//找到插入的位置
				break;
			}
		}
		//只有在找到合适的位置,才进行插入
		if(j != i - 1){
			mTemp = aArr[i];
			//采用后移的方法插入
			for(k = i - 1; k > j; k--){
				aArr[k + 1] = aArr[k];
			}
			aArr[k + 1] = mTemp;
		}
	}
}

这个实现就是根据定义来写的,所以代码很长,我们可以对其进行优化:

function insertSort1(aArr){
	var	iLength = aArr.length,
		i,
		j,
		mTemp;
	for(i = 1; i < iLength; i++){
		//因为i之前的元素都是排好序的
		//所以仅当第i个元素比第i-1个元素小的时才需插入
		if(aArr[i] < aArr[i - 1]){
			mTemp = aArr[i];
			//把第i个元素之前的所有比第i个元素大的元素后移
			for(j = i - 1; j >= 0 && aArr[j] > mTemp; j--){
				aArr[j + 1] = aArr[j];
			}
			aArr[j + 1] = mTemp;
		}
	}
}

因为for中的aArr[j] > mTemp,和if语句中的判断是同理的,所以,还可以简化一下:

function insertSort2(aArr){
	var	iLength = aArr.length,
		i,
		j,
		mTemp;
	for(i = 1; i < iLength; i++){
		for(j = i - 1; j >= 0 && aArr[j] > aArr[j + 1]; j--){
			mTemp = aArr[j];
			aArr[j] = aArr[j + 1];
			aArr[j + 1] = mTemp;
		}
	}
}

Post a Comment

Your email is never shared. Required fields are marked *

*
*