Java基础知识强化55：经典算法之插入排序（InsertSort）

 1 package cn.itcast;
 2 
 3 /*
 4  * 插入排序基本思想
 5  * 将n个元素的数列分为已有序和无序两个部分，如插入排序过程示例下所示： 　　
 6  * {{a1}，{a2，a3，a4，…，an}} 　　
 7  * {{a1⑴，a2⑴}，{a3⑴，a4⑴ …，an⑴}} 　
 8  * {{a1(n-1），a2(n-1) ，…},{an(n-1)}} 　　
 9  * 每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，
10  * 找出插入位置，将该元素插入到有序数列的合适位置中。
11  */
12 public class InsertSort {
13     public static void sort(int[] data) {
14         for (int i = 1; i < data.length; i++) {
15             for (int j = i; (j > 0) && (data[j] < data[j - 1]); j--) {
16                 swap(data, j, j - 1);
17             }
18         }
19 
20     }
21 
22 /*
23      * 交换数组中的两个元素
24      */
25     public static void swap(int[] data, int i, int j) {
26         int temp = data[i];
27         data[i] = data[j];
28         data[j] = temp;
29     }
30 }