java初学之常见排序

java初学之常见排序

节选自：Java私塾跟我学系列——JAVA篇

【冒泡排序】

对几个无序的数字进行排序，比较常用的方法是冒泡排序法。冒泡法排序是一个比较简单的排序方法，在待排序的数列基本有序的情况下排序速度较快。

基本思路：对未排序的各元素从头到尾依次比较相邻的两个元素是否逆序（与欲排顺序相反），若逆序就交换这两元素，经过第一轮比较排序后便可把最大（或最小）的元素排好，然后再用同样的方法把剩下的元素逐个进行比较，就得到了你所要的顺序。

可以看出如果有 N 个元素，那么一共要进行 N-1 轮比较，第 I 轮要进行 N-I 次比较。如：

有 5 个元素，则要进行 5-1 轮比较。第 3 轮则要进行 5-3 次比较）

示例如下：

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.       for(int i=0;i<a.length;i++){
    
14.             for(int j=i+1;j<a.length;j++){
    
15.             //注意j的开始值是i+1，因为按照排序规则，比a大的值都应该在它后面
    
16.             if(a > a[j]){
    
17.                     int temp = a[j];
    
18.                     a[j] = a;
    
19.                     a = temp;
    
20.                  }
    
21.              }
    
22.          }
    
23.       //检测一下排序的结果
    
24.      for(int i : a){
    
25.              System.out.println("i="+i);
    
26.         }
    
27.     }
    
28. }

复制代码

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

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

【选择排序】

基本思路：从所有元素中选择一个最小元素 a放在 a[0]（即让最小元素 a与 a[0]交换），作为第一轮；第二轮是从 a[1]开始到最后的各个元素中选择一个最小元素，放在 a[1]中；……依次类推。n 个数要进行（n－1）轮。比较的次数与冒泡法一样多，但是在每一轮中只进行一次交换，比冒泡法的交换次数少，相对于冒泡法效率高。

示例如下：

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 = 0; ia.length; i++) {
    
15.          int lowIndex = i;
    
16.          //找出最小的一个的索引
    
17.          for (int j=i+1;ja.length;j++) {
    
18.             if (a[j]  a[lowIndex]) {
    
19.                lowIndex = j;
    
20.             }
    
21.          }
    
22.          //交换
    
23.          temp=a;
    
24.          a=a[lowIndex];
    
25.          a[lowIndex]=temp;
    
26.       }
    
27. 
    
28.      //检测一下排序的结果
    
29.      for(int i  a){
    
30.         System.out.println(i=+i);
    
31.      }
    
32.    }
    
33. }

复制代码

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

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

【插入法排序】
  
基本思路：每拿到一个元素，都要将这个元素与所有它之前的元素遍历比较一遍，让符合排序顺序的元素挨个移动到当前范围内它最应该出现的位置。

举个例子来说，就用前面的数组，我们要对一个有 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]就可以了。

【希尔(Shell)法排序】

从前面介绍的冒泡排序法，选择排序法，插入排序法可以发现，如果数据已经大致排好序的时候，其交换数据位置的动作将会减少。例如在插入排序法过程中，如果某一整数 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 的知识。