java初学--希尔(Shell)法排序和数组排序

haveatry

java初学--希尔(Shell)法排序和数组排序

Java 私塾跟我学系列——JAVA 篇
从前面介绍的冒泡排序法，选择排序法，插入排序法可以发现，如果数据已经大致排好序的时候，其交换数据位置的动作将会减少。例如在插入排序法过程中，如果某一整数 d不是较小时，则其往前比较和交换的次数会更少。如何用简单的方式让某些数据有一定的大小次序呢？Donald Shell（Shell 排序的创始人）提出了希尔法排序。

基本思路：先将数据按照固定的间隔分组，例如每隔 4 个分成一组，然后排序各分组的数据，形成以分组来看数据已经排序，从全部数据来看，较小值已经在前面，较大值已经在后面。将初步处理了的分组再用插入排序来排序，那么数据交换和移动的次数会减少。可以得到比插入排序法更高的效率。

示例如下：

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.       // shell法排序
    
13.       int j = 0;
    
14.       int temp = 0;
    
15.       //分组
    
16.       for (int increment = a.length / 2; increment > 0; increment /= 2)
    
17.          {
    
18.          //每个组内排序
    
19.          for (int i = increment; i < a.length; i++) {
    
20.             temp = a;
    
21.             for (j = i; j >= increment; j -= increment) {
    
22.                if (temp < a[j - increment]){
    
23.                   a[j] = a[j - increment];
    
24.                }
    
25.             }
    
26.          }else{
    
27.              break;
    
28.          }
    
29.       }
    
30.       a[j] = temp;
    
31.    }
    
32. }
    
33. 
    
34. // 检测一下排序的结果
    
35. for (int i2 : a) {
    
36.    System.out.println("i=" + i2);
    
37. }

复制代码

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

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

数组排序

事实上，数组的排序不用那么麻烦，上面只是想让大家对一些基本的排序算法有所了解而已。在 java.util.Arrays 类中有一个静态方法 sort，可以用这个类的 sort 方法来对数组进行排序。

示例如下：

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.       java.util.Arrays.sort(a);
    
14.       // 检测一下排序的结果
    
15.       for (int i2 : a) {
    
16.          System.out.println("i=" + i2);
    
17.       }
    
18.    }
    
19. }

复制代码

注意：现在的 sort 方法都是升序的，要想实现降序的，还需要 Comparator 的知识。