算法之插入排序

ゝ一纸荒年。 2022-06-15 01:15 140阅读 0赞

## 插入排序算法介绍 ##

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

## 插入排序算法Java实现 ##

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

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

**\[java\]**  [view plain][]  [copy][view plain]

[print][view plain] [?][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

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. \}

**\[java\]**  [view plain][view plain 1]   [copy][view plain 1]

[print][view plain 1] [?][view plain 1]

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

**\[java\]**  [view plain][]  [copy][view plain]

[print][view plain] [?][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

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, -1, 0, -8, 2, 1 \};  
25.         ArrayUtils.printArray(array);  
26.         insertSort(array);  
27.         ArrayUtils.printArray(array);  
28.     \}  
29. \}

[Link 1]: http://lib.csdn.net/base/31
[Link 2]: http://lib.csdn.net/base/datastructure
[Java]: http://lib.csdn.net/base/17
[Java 1]: http://lib.csdn.net/base/javase
[view plain]: http://blog.csdn.net/kimylrong/article/details/17121519#
[CODE]: https://code.csdn.net/assets/CODE_ico.png
[CODE_CODE]: https://code.csdn.net/snippets/96464
[ico_fork.svg]: https://code.csdn.net/assets/ico_fork.svg
[ico_fork.svg 1]: https://code.csdn.net/snippets/96464/fork
[view plain 1]: http://blog.csdn.net/xiangzhihong8/article/details/51590872#
[Link 3]: http://lib.csdn.net/base/softwaretest