简单排序

发表于 | 分类于 | 阅读次数:
字数统计: 1,783 | 阅读时长 ≈ 8

《算法(第4版)》介绍了不少简单的排序算法，这里亲手码一遍。

排序算法

涉及的算法有插入排序、选择排序、希尔排序、冒泡排序、快速排序、归并排序以及堆排序。

插入排序

主要思想就是还未排序的元素，依次插入已排序好的序列中，直接放代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class InsertionSort {
    public static <T extends Comparable> void sort(T[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (less(arr[j + 1], arr[j])) {
                    exch(arr, j + 1, j);
                } else {
                    break;
                }
            }
        }
    }
    public static void main(String[] args) {
        Integer[] ar = new Integer[]{1, 7, 6, 4, 3};
        String[] strings = new String[]{"abcab", "ababc", "acbac"};
        sort(strings);
        sort(ar);
        System.out.println(isSorted(ar));
        show(ar);
        show(strings);
    }
}

从for循环可以看出，新近要插入的元素从后向前依次和排序好的序列元素进行比较，最好的情况是交换次数为0，此时目标序列本身就是有序的，排序时间复杂度是O(n)，最坏的情况是目标序列本身是逆序的，此时排序的时间复杂度是O(n2)。

选择排序

选择排序的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class SelectionSort{
public static <T extends Comparable> void sort(T[] arr) {
    for (int i = 0; i < arr.length; i++) {
//            T temp = arr[i];
        for (int j = i; j < arr.length; j++) {
            if (less(arr[j], arr[i])) {
                exch(arr, j, i);
            }
        }
    }
}
public static void main(String[] args) {
    Integer[] ar = new Integer[]{5, 2, 6, 4, 3};
    sort(ar);
    show(ar);
  }
}

主要思想是，每次选取还未排序序列的最小元素，放入序列头。具体到选取过程，是采用遍历的方式，挨个比较，所以无论原本的序列处于什么情形，排序的时间复杂度都是O(n2)。

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class ShellSort {
    public static <T extends Comparable> void sort(T[] arr) {
        int h = arr.length;
        while (h >= 1){
            h = h / 3;
            for (int i = h; i < arr.length; i++) {
                for (int j = i - h; j >= 0; j -= h) {
                    if (less(arr[j + h], arr[j])) {
                        exch(arr, j + h, j);
                    } else {
                        break;
                    }
                }
            }
        }
    }
    public static void main(String[] args) {
        Integer[] ar = new Integer[]{1, 7, 6, 4, 3};
        String[] strings = new String[]{"abcab", "ababc", "acbac"};
        sort(strings);
        sort(ar);
        System.out.println(isSorted(ar));
        show(ar);
        show(strings);
    }
}

希尔排序只需要对插入排序稍加修改，核心思想就是利用插入排序在部分有序的情况下会减少它的时间复杂度，所以可以将整个序列分成几条等索引差序列，先对这些序列进行插入排序。希尔排序的平均时间复杂度是O(nlog2n)。

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class BubbleSort{
    public static  <T extends Comparable> void sort(T[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            boolean flag = false;
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (less(arr[j + 1], arr[j])) {
                    exch(arr, j + 1, j);
                    flag = true;
                }
            }
            if (!flag) {
                break;
            }
        }
    }
    public static void main(String[] args) {
        Integer[] ar = new Integer[]{1, 7, 6, 4, 3};
        String[] strings = new String[]{"abcab", "ababc", "acbac"};
        sort(strings);
        sort(ar);
        System.out.println(isSorted(ar));
        show(ar);
        show(strings);
    }
}

两两交换，每次固定一个位置，时间复杂度是O(n2)，优化后在有序的情况下，时间复杂度可以是O(n)。

快速排序

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class QuickSort {
    public static <T extends Comparable> void sort(T[] arr, int left, int right) {
        if (left >= right)
            return;
        int i = left;
        int j = right;
        T k = arr[left];
        while (i < j) {
            while (!less(arr[j], k)) {
                j--;
                if (j == left)
                    break;
            }
            while (!less(k, arr[i]) && i < j) {
                i++;
            }
            if (i < j) {
                exch(arr, i, j);
            }
        }
        exch(arr, left, i);
        sort(arr, left, i - 1);
        sort(arr, i + 1, right);
    }
    public static void main(String[] args) {
        Integer[] ar = new Integer[]{1, 5, 7, 5, 6, 7, 3, 2};
        String[] strings = new String[]{"abcab", "ababc", "acbac"};
       sort(strings, 0, strings.length - 1);
        sort(ar, 0, ar.length - 1);
        System.out.println(isSorted(ar));
        show(ar);
        show(strings);
    }
}

这里采用的是一种常规实现，书中说左侧扫描最好是在遇到大于等于切分元素值的元素时停下，右侧扫描则是遇到小于等于切分元素值的元素时停下，但在本实现中，步进的i在遇到大于切分元素值时停下，j则是遇到小于时停下。由于本解答中，切分初始元素总是采用序列的第一个，所以在最外层while的内循环里，两个while的循环条件必须保证i < j，或者在循环体内部保证i不大于j。快排的平均时间复杂度是O(nlog2n)，主要缺点时非常脆弱，在某且情况时间复杂度会变成O(n2)。

归并排序

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
public class MergeSort {
    public static <T extends Comparable> void sort(T[] arr) {
        List<T> aux = new ArrayList<>(arr.length);
        sort(arr, 0, arr.length - 1, aux);
    }
    private static <T extends Comparable> void sort(T[] arr, int left, int right, List<T> aux) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        sort(arr, left, mid, aux);
        sort(arr, mid + 1, right, aux);
        merge(arr, left, mid, right, aux);
    }
    public static <T extends Comparable> void merge(T[] arr, int left, int mid, int right, List<T> aux) {
        int i = left;
        int j = mid + 1;
        int t = 0;
        while (i <= mid && j <= right) {
            if (!less(arr[j], arr[i])) {
                aux.add(t++, arr[i++]);
            } else {
                aux.add(t++, arr[j++]);
            }
        }
        while (i <= mid) {
            aux.add(t++, arr[i++]);
        }
        while (j <= right) {
            aux.add(t++, arr[j++]);
        }
        t = 0;
        while (left <= right) {
            arr[left++] = aux.get(t++);
        }
    }
    public static void main(String[] args) {
        Integer[] ar = new Integer[]{1, 7, 7, 6, 4, 3};
        String[] strings = new String[]{"abcab", "ababc", "acbac"};
        sort(strings);
        sort(ar);
        System.out.println(isSorted(ar));
        show(ar);
        show(strings);
    }
}

这是一个自顶向下的原地归并算法，比较关键的代码在于两个sort()后再进行merge()那段，sort()执行后会不断递归向下，所以merge()一定是对两段已经排序的序列进行操作。该算法在最坏的情况下的比较次数是O(nlog2n)。

堆排序

这里只涉及堆排序的操作，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class HeapSort{
    public static <T extends Comparable> void sort(T[] arr) {
        int N = arr.length;
        for (int k = N / 2 - 1; k >= 0; k--) {
            sink(arr, k, N);
        }
        while (N > 0) {
            exch(arr, 0, N - 1);
            N--;
            sink(arr, 0, N);
        }
    }
    private static <T extends Comparable> void sink(T[] arr, int k, int N) {
        while (k <= N / 2 - 1) {
            int j = 2 * k + 1;
            // 找到左节点和右节点中较大的一个
            if (j + 1< N && less(arr[j], arr[j + 1])) {
                j++;
            }
            if (!less(arr[k], arr[j]))
                break;
            exch(arr, k, j);
            k = j;
        }
    }
    public static void main(String[] args) {
        Integer[] ar = new Integer[]{5, 1, 7, 6, 4, 7, 3};
        String[] strings = new String[]{"abcab", "ababc", "acbac"};
        sort(strings);
        sort(ar);
        System.out.println(isSorted(ar));
        show(ar);
        show(strings);
    }
}

堆排序的关键是：

  • 构造堆，使其有序化。所谓有序化，就是每个节点都大于等于它的两个子节点。有序化的堆为大顶堆，根节点是最大元素；
  • 下沉排序。将根节点与最末端的节点交换，然后将交换后的根节点做下沉操作(sink())，将除了末尾元素的部分构造成新的大顶堆；

堆排序是唯一能够同时最优的利用空间和时间的算法，在最坏的情况下也能保证使用2nlog2n次比较和恒定的额外空间。缺点是数组元素很少和相邻元素做比较，缓存命中率低，无法有效利用缓存。

小结

这里主要侧重于对排序算法的熟悉。

附录

工具类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
package Algorithms_FOURTH_EDITION.tools;
public class SortTool {
    public static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }
    public static <T> void exch(T[] a, int i, int j) {
        T t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    public static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i] + " ");
        }
    }
    public static boolean isSorted(Comparable[] a)
    {
        for (int i = 1; i < a.length; i++)
            if (less(a[i], a[i-1]))  return false;
        return true;
    }
}