算法学习(三)--插入排序

package com.tw.ds.sort;



/**
 * 
 * <p>插入排序算法
 * 插入排序算法步骤 
 *1.从有序数列和无序数列{a2,a3,…,an}开始进行排序； 
 *2.处理第i个元素时(i=2,3,…,n) , 数列{a1,a2,…,ai-1}是已有序的,而数列{ai,ai+1,…,an}是无序的。
 *用ai与ai-1，a i-2,…,a1进行比较,找出合适的位置将ai插入； 
 *3.重复第二步，共进行n-1次插入处理，数列全部有序。
 * </p>
 * @author tangw  2010-11-26
 *
 */
public class InsertSortMain {
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int []arData = {2,6,5,8,7,9,10,256,248,14};
		sortAscending2(arData);
		//sortAscending(test1);
		for(int i=0; i<arData.length; i++){
			System.out.println("---i="+i+"---v="+arData[i]);
		}
	}
	
	/**
	 *插入排序方法2
	 * @param arData
	 */
	public static void sortAscending2(int[] arData){
		int in,out;
		int len = arData.length;
		for(out=1;out<len;out++){
			int temp = arData[out];
			in = out;
			while(in>0 && arData[in-1]>temp){
				arData[in] = arData[in-1];
				--in;
			}
			arData[in] = temp;
		}
	}
	/**
	 *插入排序方法1
	 * @param with
	 * @return
	 */
	public static int[] sortAscending(int []arData){	//整数递增排序
		int length = arData.length;	//获取待排数组的元素个数；
		int []temp = new int[length];
		temp[0] = arData[0];	//定义一个只有一个元素的有序数组

		for(int i=1; i<length; i++){
			for(int j=i-1; j>=0;j--){
				if(arData[i] >= temp[j]){	//如果待排序列中的元素大于等于有有序序列中的元素，则插入
					temp[j+1] = arData[i];
					break;
				}else {
					temp[j+1] = temp[j];	//给待插入元素预留空间
					if(j == 0)
						temp[j] = arData[i];	//arData[[i]是有序序列中最小的，因此排在开头
				}
			}
		}
		return temp;
	}
	
	


}