java初学之排序——插入法排序

haveatry

java初学之排序——插入法排序

Java私塾跟我学系列——JAVA篇  
基本思路：每拿到一个元素，都要将这个元素与所有它之前的元素遍历比较一遍，让符合排序顺序的元素挨个移动到当前范围内它最应该出现的位置。

举个例子来说，就用前面的数组，我们要对一个有 5 个元素的数组进行升序排列，假设第一个元素的值被假定为已排好序了，那么我们就将第 2 个元素与数组中的部分进行比较，如果第 2 个元素的值较小，则将它插入到第 1 个元素的前面，现在就有两个元素排好序了，我们再将没有排序的元素与排好序的元素列表进行比较，同样，如果小于第一个元素，就将它插入到第一个元素前面，但是，如果大于第一个元素的话，我们就将它再与第 2 个元素的值进行比较，小于的话就排在第 2 个元素前面，大于的话，就排在第 2 个元素的后面。以此类推，直到最后一个元素排好序。

示例如下：

1. 
   
2. public class Test {
   
3.    public static void main(String[] args) {
   
4.    // 需要排序的数组，目前是按照升序排列的
   
5.       int a[] = new int[5];
   
6.       a[0] = 3;
   
7.       a[1] = 4;
   
8.       a[2] = 1;
   
9.       a[3] = 5;
   
10.       a[4] = 2;
    
11. 
    
12.       // 插入法排序
    
13.       int temp;
    
14.       for (int i = 1; i < a.length; i++) {// i=1开始，因为第一个元素认为是已经排好序了的
    
15.          for (int j = i; (j > 0) && (a[j] < a[j - 1]); j--) {
    
16.             //交换
    
17.             temp = a[j];
    
18.             a[j] = a[j - 1];
    
19.             a[j - 1] = temp;
    
20.          }
    
21.       }
    
22.       // 检测一下排序的结果
    
23.       for (int i : a) {
    
24.          System.out.println("i=" + i);
    
25.       }
    
26.    }
    
27. }

复制代码

运行结果：
i=1
i=2
i=3
i=4
i=5

如果你想要按照降序排列，很简单，只需要把： a[j] < a[j - 1]这句话修改成：a[j] > a[j - 1]就可以了。