[原]Java 直接插入排序

直接插入排序（Straight Insertion Sorting）的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。

 

按照这样的思路：

 

 

package com.japher.j2se.sort;

/**
 * 
 * @author liujie , [e-mail]
 * 直接插入排序
 */
public class DerectInsertSort
{
	public static void main(String [] arg)
	{
		int [] src ={83 ,19 ,3 ,62 ,27 ,56 ,9 ,24 ,60 ,88 };
		//int [] src = BubbleSort.createRandom(20, 0, 100);
		
		int temp;
		for( int i = 1 ; i < src.length ; i++)
		{
			for(int m = 0; m<i;m++)
			{
				if( src[i] < src[m])
				{
					temp =src[i];
					for(int j = i; j>m;j--)
					{
						src[j] =src[j-1]; 
					}
					src[m] = temp;
				}	
			}
		}
		
		System.out.println("END:");
		for(int element : src )
		{
			System.out.print(element+" ");
		}
	}

}

 

输出：

 

 

END:

3 9 19 24 27 56 60 62 83 88 

 

后来看到一段更好的代码：

 

void insert_sort(ElemType a[],int n)
//待排序元素用一个数组a表示，数组有n个元素
{ int i,j;
  ElemType t; 
  for ( i=1; i<n; i++) //i表示插入次数，共进行n-1次插入
  { 
     t=a[i]; //把待排序元素赋给t
     j=i-1; 
     while ((j>=0)&& (t<a[j]))
     { a[j+1]=a[j]; j--; } // 顺序比较和移动
    a[j+1]=t;
  }
}
 

一般教科书上的例子都是这样写的，从待排的最右边一个一次往左比较，可以插入就将该位置右边的往右移一位。不过这样的感觉“插入”的概念变淡了很多，我自己写的是先找到符合插入条件的index，然后顺次移动index右边的所有