插入排序

插入排序的思想：

插入排序算法与我们打牌时，排列牌的顺序差不多。在我们摸牌时，我们一次一张牌的摸，并将这张牌放在手中的正确位置，如何放在正确位置，其实很简单，直接与手中的每一张牌对比，就能找到他的正确位置；很显然，我们没摸一张牌时，前面的牌的顺序其实就已经排好了，插入排序就是把一组数分为有序部分（一开始有序部分只有1个数）和无序部分，然后每次从无序的部分中，抽取一个放入有序部分中，直到无序部分全部变为有序部分。插入排序是一种原地排序算法，即输入的个数字在数组中进行重新排序，在任何时刻，至多只有其中常数个数字存储在数组之外。

插入排序伪代码实现：

经验：通过伪代码实现，我们就不必拘泥于用那种编程语言来实现这个算法了。因此，我们要学会使用伪代码描述算法。

INSERT_SORT(A)
             for j<-----1 to length[A]
                       do key <----- A[j]
                       Insert A[j] into the sorted sequence A[1,2,3,4.....j-1]
                       i <---- j - 1
                       while i>0  and A[i] > key
                                do  A[i+1] = A[i]        //交换位置
                                      A[i] = key
                                      i <----i-1              //让i减1，逐次对比前面的数，找到正确的位置
                       

 插入排序图示过程：

 （本人无艺术细胞，图有点丑）

插入排序java代码实现：

public class InsertSort
{
	public static void main(String []args)
	{
		int array[]={10,9,8,7,6,5,1,9,65,34,2232,121,65};
		for(int i=0;i<array.length;i++)
		{
			System.out.print("未排序前： "+array[i]+"  ");
		}
		System.out.println();
		insertSortWay(array);
		for(int i=0;i<array.length;i++)
		{
			System.out.print("排序后： "+array[i]+"  ");
		}
		
	}
	/**
	 *插入排序的方法
	 */
	public static void insertSortWay(int array[])
	{
		int key,i=0;
		for(int j=1;j<array.length;j++)
		{
			key=array[j];
			i=j-1;
			while(i>=0&&array[i]>key)
			{
				array[i+1]=array[i];
				array[i]=key;
				i--;	
			}
			
		}
	}
}

 运行结果：

未排序前： 10  未排序前： 9  未排序前： 8  未排序前： 7  未排序前： 6  未排序前： 5  未排序前： 1  未排序前： 9  未排序前： 65  未排序前： 34  未排序前： 2232  未排序前： 121  未排序前： 65  

 

排序后： 1  排序后： 5  排序后： 6  排序后： 7  排序后： 8  排序后： 9  排序后： 9  排序后： 10  排序后： 34  排序后： 65  排序后： 65  排序后： 121  排序后： 2232