1. 排序-插入类排序

插入排序(direct Insert Sort)的基本思想是：顺序地将待排序的记录按其关键码的大小插入到已排序的记录子序列的适当位置。子序列的记录个数从1开始逐渐增大，当子序列的记录个数与顺序表中的记录个数相同时排序完毕。

设待排序的顺序表sqList中有n个记录，初始时子序列中只有一个记录sqList[0]。第一次排序时，准备把记录sqList[1]插入到已排好序的子序列中，这时只需要比较sqList[0]和sqList[1]的大小，若sqList[0]≤sqList[1]，说明序列已有序，否则将sqList[1]插入到sqList[0]的前面，这样子序列的大小增大为2。第二次排序时，准备把记录sqList[2]插入到已排好序的子序列中，依次类推。

根据寻找插入位置的不同，插入排序可以有：直接插入和折半插入

1. 直接插入算法代码：

package sort.insert;

/***
 * 直接插入算法
 * @author king
 */
public class InsertSort {
	//取一个数插入到有序序列中
	private static void insertSort(int[] dataList ){
		int count =1;
		for(int i=1;i< dataList.length;i++){
			if(dataList[i] < dataList[i-1]){
				int temp=dataList[i];
				int j=0;//插入的位置
				for(j=i-1;j>=0 && temp<dataList[j];--j){//用直接插入算法寻找可以插入的位置
					dataList[j+1] = dataList[j];
				}
			 dataList[j+1]=temp;
			}
			System.out.println("第"+count+"趟排序:");
			for(int k=0;k<dataList.length;k++){
				System.out.print( dataList[k]+" ");
			}
			System.out.print("\n");
			count++;
		}
	}
	public static void main(String[] args) {
		int[] dataList = new int[]{11,10,9,8,7,6,5,4,3,2,1};
		insertSort(dataList);
	}
	
}

运行结果：

第1趟排序:

10 11 9 8 7 6 5 4 3 2 1 

第2趟排序:

9 10 11 8 7 6 5 4 3 2 1 

第3趟排序:

8 9 10 11 7 6 5 4 3 2 1 

第4趟排序:

7 8 9 10 11 6 5 4 3 2 1 

第5趟排序:

6 7 8 9 10 11 5 4 3 2 1 

第6趟排序:

5 6 7 8 9 10 11 4 3 2 1 

第7趟排序:

4 5 6 7 8 9 10 11 3 2 1 

第8趟排序:

3 4 5 6 7 8 9 10 11 2 1 

第9趟排序:

2 3 4 5 6 7 8 9 10 11 1 

第10趟排序:

1 2 3 4 5 6 7 8 9 10 11 

 

2. 折半插入算法代码

package sort.insert;

/***
 * 折半插入算法
 * 
 * @author king
 */
public class BinaryInsertSort {
	// 取一个数插入到有序序列中
	private static void insertSort(int[] dataList) {
		int count = 1;
		for (int i = 1; i < dataList.length; i++) {
			if (dataList[i] < dataList[i - 1]) {
				int temp = dataList[i];
				int j = 0;// 插入的位置
				// 用折半插入的算法寻找可以插入的位置
				int low = 0;
				int high = i - 1;
				int mid = 0;
				//二叉数查找到的插入位置
				while (low <= high) {
					mid = (low + high) / 2;
					if (dataList[mid] > temp) {
						high = mid - 1;
					} else {
						low = mid + 1;
					}
				}
				j = mid;// 二叉数查找到的插入位置
				// 移动换值
				for (int k = i;k>j; k--) {
					dataList[k] = dataList[k - 1];
				}
				dataList[j] = temp;
			}
			System.out.println("第" + count + "趟排序:");
			for (int k = 0; k < dataList.length; k++) {
				System.out.print(dataList[k] + " ");
			}
			System.out.print("\n");
			count++;
		}
	}
	public static void main(String[] args) {
		int[] dataList = new int[] { 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
		insertSort(dataList);
	}
}

 第1趟排序:

10 11 9 8 7 6 5 4 3 2 1 

第2趟排序:

9 10 11 8 7 6 5 4 3 2 1 

第3趟排序:

8 9 10 11 7 6 5 4 3 2 1 

第4趟排序:

7 8 9 10 11 6 5 4 3 2 1 

第5趟排序:

6 7 8 9 10 11 5 4 3 2 1 

第6趟排序:

5 6 7 8 9 10 11 4 3 2 1 

第7趟排序:

4 5 6 7 8 9 10 11 3 2 1 

第8趟排序:

3 4 5 6 7 8 9 10 11 2 1 

第9趟排序:

2 3 4 5 6 7 8 9 10 11 1 

第10趟排序:

1 2 3 4 5 6 7 8 9 10 11 

如果看每一趟的排序顺序，就大概明白了。

直接插入排序和折半插入排序都是

插入类排序类算法。

明天带来交换类排序算法：

起泡排序和快速排序。

 

 

评论

1 楼 cash331 2013-08-27  

int[] dataArray = new int[]{12,11,7,8,9,6,5,4,3,2,1};   数组排序有问题，
应改动如下：

public static void getBinaryInsertSort(int[] dataArray) {
		int count = 1 ;
		for(int i=1; i<dataArray.length; i++){
			if(dataArray[i] < dataArray[i-1]) {
				int temp = dataArray[i] ;
				int low = 0	 ;
				int high = i - 1 ;
				int mid = 0 ;
				while(high >= low) {
					mid = (high + low)/2 ;
					
					if(dataArray[mid] > temp) {
						if(mid > 0 && dataArray[mid - 1] < temp ) {
							break ;
						}
						high = mid - 1 ;
					} else {
						low = mid + 1 ;
					}
				}
				int j = mid ;
				for(int k=i; k>j; k--) {
					dataArray[k] = dataArray[k-1] ;
				}
				dataArray[j] = temp ;
				System.out.println("第" + count + "趟排序:");
				for (int k = 0; k < dataArray.length; k++) {
					System.out.print(dataArray[k] + " ");
				}
				System.out.print("\n");
				count++; 
			}
		}
	}