[Java数据结构与算法]简单排序之插入排序

  • 算法描述

??大多数情况下,在三种简单排序中,插入排序都是最优的选择。虽然插入排序算法仍需要 O(N^2) 的时间,但在一般情况下,它要比冒泡排序快一倍,比选择排序还要快一点。插入排序可以简单表述为:使“标定项”的一侧局部有序,每次将标定项插入有序一侧,同时将另一侧的下一项设为“标定项”。

  • 代码部分
//array为数组 nElems为数组元素个数
public void insetSort() {
	int in,out;
		
	for(out = 1; out < this.nElems; out++) {	//由左向右设置标定项,左侧局部有序
		int temp = array[out]; 	                //标定项
			
		in = out;
			
		while(in > 0 && temp < array[in -1]) {	//搜索将标定项插入到左侧的局部有序中的位置
			array[in] = array[in - 1];	//比标定项大的元素右移
			--in;
		}
		array[in] = temp;			//插入标定项
	}
}
  • 测试结果

??以{50,14,72,6,28,33,15,99,0,5}为测试用例,在每次排序中调用打印方法,可得排序过程如下:

??[Java数据结构与算法]简单排序之插入排序

??标红项为每次排序的标定项。

相关推荐