数据结构

排序算法

源码地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
package utils.sort;

import chapter02.MergeSort;

/**
 * Created by hero on 17-3-24.
 */
public interface Sort {
    void sort(int[] data);

    public static void main(String[] args) {
        int[] data = {3, 4, 2, 6, 1, 5, 11, 7, 4};
        Sort s = new TwoWayMergeSort();
        s.sort(data);
        for (int d : data) {
            System.out.println(d);
        }
    }
}

冒泡排序

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 utils.sort;

/**
 * Created by hero on 17-3-24.
 * 冒泡排序
 * 算法缺点
 * O(n^2)
 */
public class BubbleSort implements Sort {

    public void sort(int[] data) {
        for (int i = 0, j; i < data.length; i++) {
            for (j = i + 1; j < data.length; j++) {
                if (data[i] > data[j]) {
                    swap(data, i, j);
                }
            }
        }
    }

    private void swap(int[] data, int a, int b) {
        int v = data[a];
        data[a] = data[b];
        data[b] = v;
    }
}

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package chapter02;

import utils.sort.Sort;

/**
 * Created by hero on 17-3-24.
 * 插入排序（非递归）
 * 算法缺点
 * 有可能每次都要移动数组，效率很低
 * O(n^2)
 */
public class InsertSort implements Sort {

    public void sort(int[] data) {
        for (int i, j = 1, v; j < data.length; j++) {
            v = data[j];
            for (i = j; i - 1 >= 0 && data[i - 1] > v; i--) {
                data[i] = data[i - 1];
            }
            data[i] = v;
        }
    }
}

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package utils.sort;

/**
 * Created by hero on 17-3-24.
 * 希尔排序
 * 算是变步长的插入排序
 * 希尔排序和折半插入排序都是对直接插入排序的优化
 */
public class ShellSort implements Sort {

    public void sort(int[] data) {
        for (int step = data.length >> 1, i, j, v; step > 0; step >>= 1) {
            for (i = step; i < data.length; i++) {
                v = data[i];
                for (j = i - step; j >= 0 && data[j] > v; j -= step) {
                    data[j + step] = data[j];
                }
                data[j + step] = v;
            }
        }
    }
}

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package utils.sort;

/**
 * Created by hero on 17-3-25.
 * 简单选择排序
 */
public class SelectionSort implements Sort {
    /**
     * 每次都选择一个最小的值，排到前面
     * k是最小值的下标
     */
    public void sort(int[] data) {
        for (int i = 0, j, k; i < data.length; i++) {
            for (k = i, j = i + 1; j < data.length; j++)
                if (data[k] > data[j])
                    k = j;
            j = data[i];    //为了节省空间，可读性差了，工作中不推荐这么利用临时变量
            data[i] = data[k];
            data[k] = j;
        }
    }
}

树形选择排序

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
package utils.sort;

import utils.common.Queue;

/**
 * Created by hero on 17-3-25.
 * 树形选择排序
 * 算法描述
 * data[n]共有n个数，两两比较，小者成为父节点的值
 * 依次结合，直到根节点，此时，根节点就是n个数的最小值
 * 然后去掉最小值所在的节点，更新此节点的父节点最小值，直到根节点
 * n次更新之后，排序完成
 * （类似比赛中的对决，先两两对决，胜者再两两对决，直到选出冠军）
 * 树形选择排序是对简单选择排序的优化，堆排序是对树形选择排序的优化
 * O(nlogn)，时间复杂度很稳定，但是需要额外的2n-1个临时节点
 */
public class TreeSelectionSort implements Sort {
    public void sort(int[] data) {
        Queue<Node> queue = new Queue<>();
        for (int d : data) {
            queue.addLast(new Node(d));
        }

        /** 构建二叉树 */
        while (queue.length > 1) {
            Node lch = queue.removeFirst();
            Node rch = queue.removeFirst();
            Node parent = new Node(lch, rch);
            queue.addLast(parent);
        }

        Node root = queue.removeFirst();

        /**
         * 第i次循环，可以确定第i个最小值
         * 然后将该值对应的叶节点去掉，更新整个二叉树
         */
        for (int i = 0; i < data.length; i++) {
            data[i] = root.min.value;
            Node parentOfMin = root.min.parent;
            if (parentOfMin == null)
                return;
            if (parentOfMin.lch == root.min)
                parentOfMin.lch = null;
            else
                parentOfMin.rch = null;
            update(parentOfMin);
        }
    }

    private void update(Node node) {
        while (node != null) {
            if (node.lch == null && node.rch == null) {
                Node parent = node.parent;
                if (parent == null)
                    return;
                if (parent.lch == node)
                    parent.lch = null;
                else
                    parent.rch = null;
            } else
                node.selectMin(node.lch, node.rch);
            node = node.parent;
        }
    }

    private class Node {
        private int value;
        private Node min;    //指向value对应的叶节点
        private Node lch, rch, parent;

        //叶节点初始化
        Node(int value) {
            this.value = value;
            this.min = this;
            this.lch = this.rch = this.parent = null;
        }

        //非叶节点初始化
        Node(Node lch, Node rch) {
            this.lch = lch;
            this.rch = rch;
            this.parent = null;
            selectMin(lch, rch);
            lch.parent = this;
            rch.parent = this;
        }

        private void selectMin(Node lch, Node rch) {
            if (lch == null && rch == null)
                throw new IllegalArgumentException();
            if (lch == null && rch != null)
                min = rch.min;
            else if (lch != null && rch == null)
                min = lch.min;
            else if (lch.min.value > rch.min.value)
                min = rch.min;
            else
                min = lch.min;
        }
    }
}

归并排序

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
package chapter02;

import utils.sort.Sort;

/**
 * Created by hero on 17-3-24.
 * 归并排序（递归）
 * 算法缺点
 * merge时需要额外的数组，空间占用大
 */
public class MergeSort implements Sort {

    public void sort(int[] data) {
        divided(data, 0, data.length - 1);
    }

    private void divided(int[] data, int head, int tail) {
        if (head < tail) {
            int mid = (head + tail) >> 1;
            divided(data, head, mid);
            divided(data, mid + 1, tail);
            merge(data, head, mid, tail);
        }
    }

    private void merge(int[] data, int head, int mid, int tail) {
        int i = head, j = mid + 1, k = 0;
        int[] temp = new int[tail - head + 1];
        while (i <= mid && j <= tail) {
            temp[k++] = data[i] > data[j] ? data[j++] : data[i++];
        }
        if (i <= mid) {
            System.arraycopy(data, i, temp, k, mid - i + 1);
        } else {
            System.arraycopy(data, j, temp, k, tail - j + 1);
        }
        System.arraycopy(temp, 0, data, head, tail - head + 1);
    }
}

２路归并排序

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
package utils.sort;

/**
 * Created by hero on 17-3-25.
 * 2路归并排序（非递归）
 * 第一次步长为1，相当于每一路只有一个元素，然后两两合并
 * 第2次两两合并，每一路有2个元素
 * 第3次两两合并，每一路有4个元素
 * ......
 * 最终步长会超过数组总长度，分路合并结束
 *
 * 分步长是logn，合并是n，总时间复杂度是O(nlogn)
 * 算法缺点
 * 需要一个等长的数组，并且来回的复制，数组操作太多
 */
public class TwoWayMergeSort implements Sort {

    public void sort(int[] data) {
        int[] copy = new int[data.length];   //需要一个等长的数组
        for (int step = 1, i, j, alen, blen, pa, pb; step < data.length; step <<= 1) {    //各路的长度：1,2,4,8...
            for (i = 0, j = 0; i < data.length; ) {    //分路，a路加到copy[0,alen]，b路加到copy[data.length-blen, data.length]
                if (i + step < data.length) {
                    System.arraycopy(data, i, copy, 0, step);
                    alen = step;
                    i += step;
                } else {
                    System.arraycopy(data, i, copy, 0, data.length - i);
                    alen = data.length - i;
                    i = data.length;
                }
                if (i + step - 1 < data.length) {
                    System.arraycopy(data, i, copy, data.length - step, step);
                    blen = step;
                    i += step;
                } else if (i < data.length) {
                    System.arraycopy(data, i, copy, i, data.length - i);
                    blen = data.length - i;
                    i = data.length;
                } else
                    blen = 0;

                for (pa = 0, pb = data.length - blen; pa < alen && pb < data.length; ) {    //合路
                    data[j++] = copy[pa] > copy[pb] ? copy[pb++] : copy[pa++];
                }
                if (pa == alen) {
                    System.arraycopy(copy, pb, data, j, data.length - pb);
                    j += (data.length - pb);
                } else {
                    System.arraycopy(copy, pa, data, j, alen - pa);
                    j += (alen - pa);
                }
            }
        }
    }
}

快速排序

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
package chapter07;

import utils.sort.Sort;

/**
 * 快速排序算法（递归）
 * 每次取第一个值作为比较值key，用一个临时变量key可以避免作交换
 * 1.从最后向前找比key小的值，赋给data[i]，这里就不是交换
 * 2.从前面向后找比key大的值，赋给data[j]，相当于数组中每次都空一个等待赋值的位置
 * 3.递归结束
 * <p>
 * 算法缺点
 * 每次取第一个作为比较值，情况不够随机，很容易遇到最坏情况
 */
public class QuickSort implements Sort {

    public void sort(int[] data) {
        sort(data, 0, data.length - 1);
    }

    private void sort(int[] data, int first, int last) {
        if (first >= last) return;
        int key = data[first];
        int i = first, j = last;
        while (i < j) {
            while (i < j && data[j] >= key) j--;
            data[i] = data[j];
            while (i < j && data[i] <= key) i++;
            data[j] = data[i];
        }
        data[i] = key;
        sort(data, first, i - 1);
        sort(data, i + 1, last);
    }
}

堆排序

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
package utils.sort;

/**
 * Created by hero on 17-3-25.
 * 堆排序（非递归）
 * 算法关键
 * 1.首先要构造一个最大堆
 * 2.在1基础上交换根节点和尾节点，然后维护最大堆
 *
 * 因为非递归，所以在处理大量数据时，可以使用堆排序
 */
public class HeapSort implements Sort {

    public void sort(int[] data) {
        /** 构造最大堆 */
        for (int i = (data.length - 1) / 2; i >= 0; i--)
            sift(data, i, data.length - 1);

        for (int i = data.length - 1, v; i > 0; i--) {
            v = data[0];
            data[0] = data[i];
            data[i] = v;
            sift(data, 0, i - 1);
        }
    }

    /**
     * 从i向其左右孩子节点更新维护最大堆
     * 因为本身就是最大堆，所以只需维护改变的分支
     */
    private void sift(int[] data, int i, int m) {
        int v = data[i];    // v为“根”元素，将作为某分支的父节点
        for (int j = 2 * i + 1; j <= m; j = 2 * j + 1) {    // 从根元素向子元素更新
            if (j + 1 <= m && data[j + 1] > data[j])        //  若有右孩子并且右孩子大于左孩子
                j++;
            if (data[j] > v) {    // 子节点大于父节点
                data[i] = data[j];
                i = j;    // i为等待填值的父节点
            } else
                break;
        }
        data[i] = v;
    }
}

基数排序