排序---初级排序算法（选择排序、插入排序和希尔排序）

写在前面的话：

一枚自学Java和算法的工科妹子。

  • 算法学习书目：算法（第四版） Robert Sedgewick
  • 算法视频教程：Coursera  Algorithms Part1&2

本文是根据《算法（第四版）》的个人总结，如有错误，请批评指正。

一、排序算法介绍

1.排序算法的目的：将所有元素的主键（如学生类，主键可以是姓名、学号、年龄等）按照某种方式排列（通常按照大小或字母排序）。

2.排序算法类模板：sort()排序方法；less()元素比较；exch()元素交换位置；show()打印字符数组内容；isSorted()判断元素是否有序。

 1 public class Example {
 2 
 3     private Example () { }
 4 
 5     public static void sort(Comparable[] a) {
 6       // 选择排序、插入排序、希尔排序、归并排序、快速排序,实现Comparable接口
 7     }
 8     public static void sort(Object[] a, Comparator comparator) {
 9       //  数据类型中定义内部类实现Comparator
10     }
11 
12     // 判断元素大小
13     private static boolean less(Comparable v, Comparable w) {
14         return v.compareTo(w) < 0;
15     }
16     private static boolean less(Comparator comparator, Object v, Object w) {
17         return comparator.compare(v, w) < 0;
18     }
19 
20     // 交换元素位置
21     private static void exch(Object[] a, int i, int j) {
22         Object swap = a[i];
23         a[i] = a[j];
24         a[j] = swap;
25     }
26 
27     // 判断元素是否已排序
28     private static boolean isSorted(Comparable[] a, int lo, int hi) {
29         for (int i = lo + 1; i <= hi; i++)
30             if (less(a[i], a[i-1])) return false;
31         return true;
32     }
33 
34     private static boolean isSorted(Object[] a, Comparator comparator, int lo, int hi) {
35         for (int i = lo + 1; i <= hi; i++)
36             if (less(comparator, a[i], a[i-1])) return false;
37         return true;
38     }
39 
40     // 打印字符数组内容
41     private static void show(Comparable[] a) {
42         for (int i = 0; i < a.length; i++) {
43             StdOut.println(a[i]);
44         }
45     }
46 }

3.排序算法需要注意的问题

  • 验证：在测试代码中添加一条语句 assert isSorted(a) 来确认排序后数组元素都是有序的。
  • 运行时间：在研究排序算法时，我们需要计算比较和交换的数量。对于不交换元素的算法，我们会计算访问数组的次数。
  • 额外的内存使用：（1）原地排序算法：除了函数调用所需的栈和固定数目的实例变量之外无需额外内存；（2）其他排序算法：需要额外内存空间来存储另一份数组副本。
  • 数据类型：上述排序算法模板使用与实现了Comparable接口或者在类中定义了内部类实现Comparator接口的数据类型。Java中Integer、Double、String、File、URL等数据类型都实现了Comparable接口。当然也可以自己设计数据类型实现Comparable接口，实现compareTo()方法来自定义目标类型对象的自然次序。可参考Comparable和Comparator区别（实现和使用）。

二、初级排序算法

1. 选择排序介绍

1.1 选择排序算法流程

Step1：从待排序序列中，找到关键字最小的元素；

Step2：如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；

Step3：从余下的 N - 1 个元素中，找出关键字最小的元素，重复Step1和Step2，直到排序结束。

图1 选择排序的轨迹

1.2 选择排序算法代码实现

 1 import java.util.Comparator;
 2 
 3 public class Selection {
 4 
 5     private Selection() { }
 6 
 7     public static void sort(Comparable[] a) {
 8         int n = a.length;
 9         for (int i = 0; i < n; i++) {
10             int min = i;
11             for (int j = i+1; j < n; j++) {
12                 if (less(a[j], a[min])) min = j;
13             }
14             exch(a, i, min);
15             assert isSorted(a, 0, i);
16         }
17         assert isSorted(a);
18     }
19 
20     public static void sort(Object[] a, Comparator comparator) {
21         int n = a.length;
22         for (int i = 0; i < n; i++) {
23             int min = i;
24             for (int j = i+1; j < n; j++) {
25                 if (less(comparator, a[j], a[min])) min = j;
26             }
27             exch(a, i, min);
28             assert isSorted(a, comparator, 0, i);
29         }
30         assert isSorted(a, comparator);
31     }
32 
33     // is v < w ?
34     private static boolean less(Comparable v, Comparable w) {
35         return v.compareTo(w) < 0;
36     }
37 
38     // is v < w ?
39     private static boolean less(Comparator comparator, Object v, Object w) {
40         return comparator.compare(v, w) < 0;
41     }
42          
43     // exchange a[i] and a[j]
44     private static void exch(Object[] a, int i, int j) {
45         Object swap = a[i];
46         a[i] = a[j];
47         a[j] = swap;
48     }
49 
50     // is the array a[] sorted?
51     private static boolean isSorted(Comparable[] a) {
52         return isSorted(a, 0, a.length - 1);
53     }
54         
55     // is the array sorted from a[lo] to a[hi]
56     private static boolean isSorted(Comparable[] a, int lo, int hi) {
57         for (int i = lo + 1; i <= hi; i++)
58             if (less(a[i], a[i-1])) return false;
59         return true;
60     }
61 
62     // is the array a[] sorted?
63     private static boolean isSorted(Object[] a, Comparator comparator) {
64         return isSorted(a, comparator, 0, a.length - 1);
65     }
66 
67     // is the array sorted from a[lo] to a[hi]
68     private static boolean isSorted(Object[] a, Comparator comparator, int lo, int hi) {
69         for (int i = lo + 1; i <= hi; i++)
70             if (less(comparator, a[i], a[i-1])) return false;
71         return true;
72     }
73 
74     // print array to standard output
75     private static void show(Comparable[] a) {
76         for (int i = 0; i < a.length; i++) {
77             StdOut.println(a[i]);
78         }
79     }
80 }

 1.3 选择排序算法性能分析

  • 对于长度为N的数组，选择排序需要大约(N-1)+(N-2)+...+2+1=N(N-1)/2~N2/2次比较和N次交换;
  • 运行时间和输入无关；
  • 数据移动是最少的；
  • 算法不稳定。

2. 插入排序介绍

2.1 插入排序算法流程

Step1：从第一个元素开始，该元素可以认为已经被排序;
Step2：取出下一个元素，在已经排序的元素序列中从后向前扫描;
Step3：如果该元素（已排序）大于新元素，将该元素移到下一位置;
Step4：重复Step3，直到找到已排序的元素小于或者等于新元素的位置;
Step5：将新元素插入到该位置后;
Step6：重复步骤Step2~Step5.

图2 插入排序的轨迹

 2.2 插入排序算法代码实现

  1 import java.util.Comparator;
  2 
  3 public class Insertion {
  4 
  5     // This class should not be instantiated.
  6     private Insertion() { }
  7 
  8     public static void sort(Comparable[] a) {
  9         int n = a.length;
 10         for (int i = 0; i < n; i++) {
 11             for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
 12                 exch(a, j, j-1);
 13             }
 14             assert isSorted(a, 0, i);
 15         }
 16         assert isSorted(a);
 17     }
 18 
 19     public static void sort(Comparable[] a, int lo, int hi) {
 20         for (int i = lo; i <= hi; i++) {
 21             for (int j = i; j > lo && less(a[j], a[j-1]); j--) {
 22                 exch(a, j, j-1);
 23             }
 24         }
 25         assert isSorted(a, lo, hi);
 26     }
 27 
 28    
 29     public static void sort(Object[] a, Comparator comparator) {
 30         int n = a.length;
 31         for (int i = 0; i < n; i++) {
 32             for (int j = i; j > 0 && less(a[j], a[j-1], comparator); j--) {
 33                 exch(a, j, j-1);
 34             }
 35             assert isSorted(a, 0, i, comparator);
 36         }
 37         assert isSorted(a, comparator);
 38     }
 39 
 40     public static void sort(Object[] a, int lo, int hi, Comparator comparator) {
 41         for (int i = lo; i <= hi; i++) {
 42             for (int j = i; j > lo && less(a[j], a[j-1], comparator); j--) {
 43                 exch(a, j, j-1);
 44             }
 45         }
 46         assert isSorted(a, lo, hi, comparator);
 47     }
 48 
 49 
 50     public static int[] indexSort(Comparable[] a) {
 51         int n = a.length;
 52         int[] index = new int[n];
 53         for (int i = 0; i < n; i++)
 54             index[i] = i;
 55 
 56         for (int i = 0; i < n; i++)
 57             for (int j = i; j > 0 && less(a[index[j]], a[index[j-1]]); j--)
 58                 exch(index, j, j-1);
 59 
 60         return index;
 61     }
 62 
 63     // is v < w ?
 64     private static boolean less(Comparable v, Comparable w) {
 65         return v.compareTo(w) < 0;
 66     }
 67 
 68     // is v < w ?
 69     private static boolean less(Object v, Object w, Comparator comparator) {
 70         return comparator.compare(v, w) < 0;
 71     }
 72         
 73     // exchange a[i] and a[j]
 74     private static void exch(Object[] a, int i, int j) {
 75         Object swap = a[i];
 76         a[i] = a[j];
 77         a[j] = swap;
 78     }
 79 
 80     // exchange a[i] and a[j]  (for indirect sort)
 81     private static void exch(int[] a, int i, int j) {
 82         int swap = a[i];
 83         a[i] = a[j];
 84         a[j] = swap;
 85     }
 86 
 87     private static boolean isSorted(Comparable[] a) {
 88         return isSorted(a, 0, a.length - 1);
 89     }
 90 
 91     // is the array sorted from a[lo] to a[hi]
 92     private static boolean isSorted(Comparable[] a, int lo, int hi) {
 93         for (int i = lo+1; i <= hi; i++)
 94             if (less(a[i], a[i-1])) return false;
 95         return true;
 96     }
 97 
 98     private static boolean isSorted(Object[] a, Comparator comparator) {
 99         return isSorted(a, 0, a.length - 1, comparator);
100     }
101 
102     // is the array sorted from a[lo] to a[hi]
103     private static boolean isSorted(Object[] a, int lo, int hi, Comparator comparator) {
104         for (int i = lo + 1; i <= hi; i++)
105             if (less(a[i], a[i-1], comparator)) return false;
106         return true;
107     }
108 
109    // print array to standard output
110     private static void show(Comparable[] a) {
111         for (int i = 0; i < a.length; i++) {
112             StdOut.println(a[i]);
113         }
114     }
115 }

2.3 插入排序算法性能分析

  • 对于长度为N且主键不重复的数组，平均情况下需要~N2/4次比较和~N2/4次交换，最坏情况下（逆序数组）需要~N2/2次比较和~N2/2次交换，最好情况下（数组已经有序）需要~N-1次比较和0次交换；
  • 比较的总次数总是在交换的总次数上加一个额外项，该项为N减去被插入的元素正好是已知排序中的最小元素的次数；
  • 插入排序算法适用于部分有序的数组：1）数组中每个元素的距离离它的终点位置都不远；2）一个有序的大数组接一个小数组；3）数组中只有几个元素的位置不确定；
  • 算法稳定。

3. 希尔排序介绍

希尔(Shell)排序又称为缩小增量排序，它是一种插入排序。它是直接插入排序算法的一种威力加强版。

3.1 希尔排序算法流程

把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。
随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。

图3 希尔排序的轨迹

 3.2 希尔排序算法代码实现

 1 public class Shell {
 2 
 3     // This class should not be instantiated.
 4     private Shell() { }
 5 
 6     public static void sort(Comparable[] a) {
 7         int n = a.length;
 8 
 9         // 3x+1 increment sequence:  1, 4, 13, 40, 121, 364, 1093, ... 
10         int h = 1;
11         while (h < n/3) h = 3*h + 1; 
12 
13         while (h >= 1) {
14             // h-sort the array
15             for (int i = h; i < n; i++) {
16                 for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) {
17                     exch(a, j, j-h);
18                 }
19             }
20             assert isHsorted(a, h); 
21             h /= 3;
22         }
23         assert isSorted(a);
24     }
25     
26     // is v < w ?
27     private static boolean less(Comparable v, Comparable w) {
28         return v.compareTo(w) < 0;
29     }
30         
31     // exchange a[i] and a[j]
32     private static void exch(Object[] a, int i, int j) {
33         Object swap = a[i];
34         a[i] = a[j];
35         a[j] = swap;
36     }
37 
38     private static boolean isSorted(Comparable[] a) {
39         for (int i = 1; i < a.length; i++)
40             if (less(a[i], a[i-1])) return false;
41         return true;
42     }
43 
44     // is the array h-sorted?
45     private static boolean isHsorted(Comparable[] a, int h) {
46         for (int i = h; i < a.length; i++)
47             if (less(a[i], a[i-h])) return false;
48         return true;
49     }
50 
51     // print array to standard output
52     private static void show(Comparable[] a) {
53         for (int i = 0; i < a.length; i++) {
54             StdOut.println(a[i]);
55         }
56     }
57 }

3.3 希尔排序算法性能分析

  • 对于长度为N且主键不重复的数组，平均情况下需要~NlgN次比较，最坏情况需要~N1.5次比较；
  • 目前最好的排序序列是1,5,19,41,109...,由Sedgewick提出；
  • 希尔排序算法属于插入排序，但是不稳定。

三、一种洗牌方法的实现（直接上代码）

public class StdRandom
{// 这是一个随机数静态方法库，包含各种随机数生成方法和随机数操作方法
...
   public static void shuffle(int[] a) {
        // 参数可以改成其他数据类型double
        if (a == null) throw new IllegalArgumentException("argument array is null");
        int n = a.length;
        for (int i = 0; i < n; i++) {
            int r = i + StdRandom.uniform(n-i);       
            //StdRandom.uniform(n-i) 方法随机产生1到n-i之间的整数
            int temp = a[i];
            a[i] = a[r];
            a[r] = temp;
        }
    }
}

作者： 邹珍珍（Pearl_zhen）

出处： http://www.cnblogs.com/zouzz/

声明：本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出 原文链接 如有问题， 可邮件（zouzhenzhen@seu.edu.cn）咨询.

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/zouzz/p/6095345.html