IT虾米网

算法之插入排序详解

luoye 2018年07月09日 程序员 397 0

插入排序算法介绍

排序算法是最简单的算法,也是最基本的算法。顾名思义,插入排序就是把当前待排序的元素插入到一个已经排好序的列表里面。 一个非常形象的例子就是右手抓取一张扑克牌,并把它插入左手拿着的排好序的扑克里面。插入排序的最坏运行时间是O(n2), 所以并不是最优的排序算法。特点是简单,不需要额外的存储空间,在元素少的时候工作得好。

插入排序算法Java实现

Java里面有很多数据类型,我们选取的是最简单的整数,但这并不失一般性。即使是自己定制化的对象,实现了java.lang.Comparable, 把对应的 大于号(>)以及小于号(<)换成compareTo即可。

由于需要频繁的操作以及打印数组,先写一个小的数组工具类。代码如下:

  1. public class ArrayUtils {  
  2.       
  3.     public static void printArray(int[] array) {  
  4.         System.out.print("{");  
  5.         for (int i = 0; i < array.length; i++) {  
  6.             System.out.print(array[i]);  
  7.             if (i < array.length - 1) {  
  8.                 System.out.print(", ");  
  9.             }  
  10.         }  
  11.         System.out.println("}");  
  12.     }  
  13. }  
public class ArrayUtils { 
	 
	public static void printArray(int[] array) { 
		System.out.print("{"); 
		for (int i = 0; i < array.length; i++) { 
			System.out.print(array[i]); 
			if (i < array.length - 1) { 
				System.out.print(", "); 
			} 
		} 
		System.out.println("}"); 
	} 
}

从数组的第二个元素开始,取得当前待处理的元素,插入到当前元素之前的子数组里面,直到数组的末尾。插入排序的Java实现以及测试代码如下:

  1. public class InsertSortTest {  
  2.     public static void insertSort(int[] array) {  
  3.         if (array == null || array.length < 2) {  
  4.             return;  
  5.         }  
  6.   
  7.         for (int i = 1; i < array.length; i++) {  
  8.             int currentValue = array[i];  
  9.             int position = i;  
  10.             for (int j = i - 1; j >= 0; j--) {  
  11.                 if (array[j] > currentValue) {  
  12.                     array[j + 1] = array[j];  
  13.                     position -= 1;  
  14.                 } else {  
  15.                     break;  
  16.                 }  
  17.             }  
  18.   
  19.             array[position] = currentValue;  
  20.         }  
  21.     }  
  22.   
  23.     public static void main(String[] args) {  
  24.         int[] array = { 3, -10, -821 };  
  25.         ArrayUtils.printArray(array);  
  26.         insertSort(array);  
  27.         ArrayUtils.printArray(array);  
  28.     }  
  29. }  
发布评论

分享到:

IT虾米网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

算法之冒泡排序详解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。