排序算法之插入排序--Java语言

时间:2021-03-04 11:10:31

插入排序是一种简单且有效的比较排序算法。在每次迭代过程中算法从输入序列中移除一个元素,并将该元素插入待排序序列的正确位置。重复该过程,直到所有输入元素都被选择一次。

算法优点:

a.实现简单

b.数据量较少时效率高

c.适应性:如果输入序列已经预排序,则时间复杂度几乎是线性的。

d.稳定性:键值相同时它能够保持输入数据的原有次序。

e.原地:不需要额外的空间。

算法思路:从第二个元素作为当前元素,依次往下标较小的位置遍历,当前一个元素比该元素小,则将该元素放入当前位置,否则前一个元素后移,同理依次遍历;然后以第三个元素作为当前元素,重复上述操作;依次往后直到到达最后一个元素完成排序。

代码:

package insertionsort;

public class InsertionSort {
	private static int count;
	
	public static int[] insertionSort(int[] A,int n)
	{
		int i,j,v;
		for(i=1;i<n;i++)
		{
			v=A[i];
			j=i;
			while(j>=1&&A[j-1]>v)//此处应该将j>=1的条件限制放在前面,然后用短路与&&,这样使用才不会导致A[j-1]报错;
			{
				A[j]=A[j-1];//满足条件则需继续遍历,则将j-1位置的元素往后移;
				j--;
				count++;
			}
			A[j]=v;//当A[j-1]<v的时候,则将A[j]的位置放v。
			print(A);
		}
		return A;
	}
	private static void print(int[] A)
	{
		int n=A.length;
		for(int i=0;i<n;i++)
			System.out.print(A[i]+" ");
		System.out.println();
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] A= {8,9,1,4,5,3,7,2};
		int n=8;
		System.out.println("插入排序步骤中插入元素位置变化:");
		int[] ans=InsertionSort.insertionSort(A, n);
		System.out.println("完成排序后的序列:");
		for(int i=0;i<n-1;i++)
			System.out.print(ans[i]+" ");
		System.out.print(ans[n-1]);
		System.out.println();
	}

}
测试结果:

插入排序步骤中插入元素位置变化:
8 9 1 4 5 3 7 2 
1 8 9 4 5 3 7 2 
1 4 8 9 5 3 7 2 
1 4 5 8 9 3 7 2 
1 3 4 5 8 9 7 2 
1 3 4 5 7 8 9 2 
1 2 3 4 5 7 8 9 
完成排序后的序列:
1 2 3 4 5 7 8 9

插入排序最坏情况下的时间复杂度为O(n^2),在数据几乎都已经排序或者输入数据规模较小时可以使用插入排序。