排序算法复习

 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 bubble;

import java.util.Random;

/**
 * @author Boli Tao
 */
public class BubbleSort {
    /**
     * 交换 arr 数组中索引为 index1 和 index2 的值
     *
     * @param arr    array
     * @param index1 index1
     * @param index2 index2
     */
    public static void swap(int[] arr, int index1, int index2) {
        int tmp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = tmp;
    }

    /**
     * bubble sort
     *
     * @param arr the array to be sorted
     */
    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
            }
        }
    }

    public static void main(String[] args) {
        Random random = new Random();
        int[] array = new int[100000];
        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt(Integer.MAX_VALUE);
        }
        bubbleSort(array);
        for (int i = 0; i < array.length - 1; i++) {
            if (array[i + 1] < array[i]) {
                throw new IllegalArgumentException("冒泡排序写错了");
            }
        }
        System.out.println("Test complete.");
    }
}

 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

package selection;

/**
 * @author Boli Tao
 */
public class SelectionSort {
    /**
     * 交换 arr 数组中索引为 index1 和 index2 的值
     *
     * @param arr    array
     * @param index1 index1
     * @param index2 index2
     */
    private static void swap(int[] arr, int index1, int index2) {
        int tmp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = tmp;
    }

    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int min_idx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[min_idx]) {
                    min_idx = j;
                }
            }
            swap(arr, i, min_idx);
        }
    }

    public static void main(String[] args) {
        int[] arr = {37, 18, 7, 5, 24, 46, 28, 35, 11, 13, 2};
        selectionSort(arr);
        System.out.print("Sorted array:\n[");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if (i != arr.length - 1) {
                System.out.print(" ,");
            }
        }
        System.out.print("]");
    }
}

 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

package insertion;

/**
 * @author Boli Tao
 */
public class InsertionSort {
    static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            // 后移
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            // 插入
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {37, 18, 7, 5, 24, 46, 28, 35, 11, 13, 2};
        insertionSort(arr);
        StringBuilder builder = new StringBuilder();
        builder.append("Sorted array:\n[");
        for (int i = 0; i < arr.length; i++) {
            builder.append(arr[i]);
            if (i != arr.length - 1) {
                builder.append(" ,");
            }
        }
        builder.append("]");
        System.out.println(builder.toString());
    }
}

 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

package merge;

/**
 * @author 陶波利
 */
public class MergeSort {
    private static void merge(int[] arr, int l, int m, int r) {
        int leftArraySize = m - l + 1;
        // r - (m + 1) + 1
        int rightArraySize = r - m;

        // temp array
        int[] leftTempArray = new int[leftArraySize];
        int[] rightTempArray = new int[rightArraySize];

        // 把 arr 中的数据拷入两个 temp 数组
        for (int i = 0; i < leftArraySize; i++) {
            leftTempArray[i] = arr[l + i];
        }
        for (int i = 0; i < rightArraySize; i++) {
            rightTempArray[i] = arr[m + 1 + i];
        }

        // 两个 temp 数组的索引
        int i = 0, j = 0;
        // arr 数组的索引
        int k = l;

        // 将 temp 数组的数据按顺序填入 arr
        while (i < leftArraySize && j < rightArraySize) {
            if (leftTempArray[i] <= rightTempArray[j]) {
                arr[k] = leftTempArray[i];
                i++;
            } else {
                arr[k] = rightTempArray[j];
                j++;
            }
            k++;
        }

        while (i < leftArraySize) {
            arr[k] = leftTempArray[i];
            i++;
            k++;
        }

        while (j < rightArraySize) {
            arr[k] = rightTempArray[j];
            j++;
            k++;
        }
    }

    public static void mergeSort(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int m = (l + r) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }

    public static void main(String[] args) {
        int[] arr = {37, 18, 7, 5, 24, 46, 28, 35, 11, 13, 2};
        mergeSort(arr, 0, arr.length - 1);
        StringBuilder builder = new StringBuilder();
        builder.append("Sorted array:\n[");
        for (int i = 0; i < arr.length; i++) {
            builder.append(arr[i]);
            if (i != arr.length - 1) {
                builder.append(" ,");
            }
        }
        builder.append("]");
        System.out.println(builder.toString());
    }
}

 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

package quick;

import java.util.Random;

/**
 * @author 陶波利
 */
public class QuickSort {
    /**
     * 交换 arr 数组中索引为 index1 和 index2 的值
     *
     * @param arr    array
     * @param index1 index1
     * @param index2 index2
     */
    private static void swap(int[] arr, int index1, int index2) {
        int tmp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = tmp;
    }

    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        int pivotIndex = left;
        while (left < right) {
            // 从右侧开始寻找比基准数小的元素的索引
            while (left < right && arr[right] >= pivot) {
                right--;
            }
            //从左侧开始寻找比基准数大的元素的索引
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            // 把大数移到右边，小数移到左边
            swap(arr, left, right);
        }
        // 把 pivot 移到中间
        swap(arr, pivotIndex, left);
        return left;
    }

    private static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int pi = partition(arr, left, right);
        quickSort(arr, left, pi - 1);
        quickSort(arr, pi + 1, right);
    }

    public static void sort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    public static void main(String[] args) {
        Random random = new Random();
        int[] array = new int[1000000];
        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt(Integer.MAX_VALUE);
        }
        sort(array);
        for (int i = 0; i < array.length - 1; i++) {
            if (array[i + 1] < array[i]) {
                throw new IllegalArgumentException("快排写错了");
            }
        }
    }
}

  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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153

package heap;

import array.Array;

import java.util.Random;

/**
 * @author 陶波利
 */
public class MaxHeap<E extends Comparable<E>> {
    private Array<E> data;

    public MaxHeap(int capacity) {
        data = new Array<>(capacity);
    }

    public MaxHeap() {
        data = new Array<>();
    }

    /**
     * 构造函数：将传入数组组成为最大堆
     *
     * @param arr 待化为最大堆的数组
     */
    public MaxHeap(E[] arr) {
        data = new Array<>(arr);
        for (int i = parent(arr.length - 1); i >= 0; i--) {
            siftDown(i);
        }
    }

    public int size() {
        return data.getSize();
    }

    public boolean isEmpty() {
        return data.isEmpty();
    }

    /**
     * @param index index
     * @return index 的父节点的索引
     */
    private int parent(int index) {
        if (index == 0) {
            throw new IllegalArgumentException("index 0 doesn't have parent.");
        }
        return (index - 1) / 2;
    }

    private int leftChild(int index) {
        return index * 2 + 1;
    }

    private int rightChild(int index) {
        return index * 2 + 2;
    }

    /**
     * 向堆中添加元素
     *
     * @param e 待添加的元素值
     */
    public void add(E e) {
        data.addLast(e);
        siftUp(data.getSize() - 1);
    }

    /**
     * 为满足最大堆性质而设计的元素上浮方法
     *
     * @param k 需要被上浮的元素索引
     */
    private void siftUp(int k) {
        while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0) {
            data.swap(k, parent(k));
            k = parent(k);
        }
    }

    /**
     * 取出堆中最大元素
     *
     * @return
     */
    public E extractMax() {
        E ret = getMax();
        data.swap(0, data.getSize() - 1);
        data.removeLast();
        siftDown(0);
        return ret;
    }

    public E getMax() {
        if (data.getSize() == 0) {
            throw new IllegalArgumentException("Size is 0, no element in heap.");
        }
        return data.get(0);
    }

    /**
     * 为满足最大堆性质而设计的元素下沉方法
     * TODO: 需要进一步理解
     *
     * @param k 需要被下沉的元素索引
     */
    private void siftDown(int k) {
        while (leftChild(k) < data.getSize()) {
            int j = leftChild(k);
            if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0) {
                j = rightChild(k);
            }
            // ↑此时 j 表示孩子节点中更大元素的索引
            if (data.get(k).compareTo(data.get(j)) > 0) {
                break;
            }
            data.swap(k, j);
            k = j;
        }
    }

    public E replace(E e) {
        E ret = getMax();
        data.set(0, e);
        siftDown(0);
        return ret;
    }

    /**
     * 测试类
     *
     * @param args args
     */
    public static void main(String[] args) {
        int n = 1000000;
        MaxHeap<Integer> maxHeap = new MaxHeap<>();
        Random random = new Random();
        for (int i = 0; i < n; i++) {
            maxHeap.add(random.nextInt(Integer.MAX_VALUE));
        }
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = maxHeap.extractMax();
        }
        for (int i = 1; i < n; i++) {
            if (arr[i - 1] < arr[i]) {
                throw new IllegalArgumentException("Error: 最大堆实现出现问题！");
            }
        }
        System.out.println("Completed!");
    }
}

  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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173

package array;

/**
 * 自定义的 Array 类
 *
 * @author 陶波利
 */
public class Array<E> {
    private E[] data;
    private int size;

    public Array() {
        this(10);
    }

    public Array(int capacity) {
        data = (E[]) new Object[capacity];
        size = 0;
    }

    public Array(E[] arr) {
        data = (E[]) new Object[arr.length];
        for (int i = 0; i < arr.length; i++) {
            data[i] = arr[i];
        }
        size = arr.length;
    }

    public int getSize() {
        return size;
    }

    public int getCapacity() {
        return data.length;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("get() failed, index is illegal.");
        }
        return data[index];
    }

    public void set(int index, E value) {
        data[index] = value;
    }

    public boolean isContaianed(E value) {
        for (E m : data) {
            if (value.equals(m)) {
                return true;
            }
        }
        return false;
    }

    public int find(E value) {
        for (int i = 0; i < data.length; i++) {
            if (value.equals(data[i])) {
                return i;
            }
        }
        return -1;
    }

    public void add(int index, E value) {
//        if (size >= data.length) {
//            throw new IllegalArgumentException("add() method failed, array is full.");
//        }
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("add() failed. Requirement: 0 <=index <= size.");
        }
        if (size == data.length) {
            resize(2 * data.length);
        }
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        data[index] = value;
        size++;
    }

    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

    public void addFirst(E value) {
        add(0, value);
    }

    public void addLast(E value) {
        add(size, value);
    }

    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("remove() failed, index is illegal.");
        }
        E removedValue = data[index];
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }
        size--;
        // loitering objects != memory leak
        data[size] = null;
        if (size == data.length / 4 && data.length / 2 != 0) {
            // TODO: / 4?
            resize(data.length / 2);
        }
        return removedValue;
    }

    public E removeFirst() {
        return remove(0);
    }

    public E removeLast() {
        return remove(size - 1);
    }

    public void removeElement(E value) {
        int index = find(value);
        if (-1 != index) {
            remove(index);
        }
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
        builder.append("[");
        for (int i = 0; i < size; i++) {
            builder.append(data[i]);
            if (i != size - 1) {
                builder.append(", ");
            }
        }
        builder.append("]");
        return builder.toString();
    }

    public E getLast() {
        return get(size - 1);
    }

    public E getFirst() {
        return get(0);
    }

    /**
     * 交换索引为 i j 的元素
     *
     * @param i index i
     * @param j index j
     */
    public void swap(int i, int j) {
        if (i < 0 || i >= size || j < 0 || j >= size) {
            throw new IllegalArgumentException("Index is illegal");
        }
        E temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}

 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

package shell;

import java.util.Random;

/**
 * @author 陶波利
 */
public class ShellSort {
    private static void shellInsert(int[] arr, int d) {
        for (int i = d; i < arr.length; i++) {
            int j = i - d;
            //记录要插入的数据
            int temp = arr[i];
            //从后向前，找到比其小的数的位置
            while (j >= 0 && arr[j] > temp) {
                //向后挪动
                arr[j + d] = arr[j];
                j -= d;
            }
            //存在比其小的数
            if (j != i - d) {
                arr[j + d] = temp;
            }
        }
    }

    public static void shellSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int d = arr.length / 2;
        while (d >= 1) {
            shellInsert(arr, d);
            d /= 2;
        }
    }

    public static void main(String[] args) {
        Random random = new Random();
        int[] array = new int[1000000];
        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt(Integer.MAX_VALUE);
        }
        shellSort(array);
        for (int i = 0; i < array.length - 1; i++) {
            if (array[i + 1] < array[i]) {
                throw new IllegalArgumentException("希尔排序写错了");
            }
        }
        System.out.println("Test complete.");
    }
}