十大经典排序算法动画与解析,看我就够了!(配代码完全版) (3)

image

image

5.3 参考代码 1public class MergeSort implements IArraySort {
2
3    @Override
4    public int[] sort(int[] sourceArray) throws Exception {
5        // 对 arr 进行拷贝,不改变参数内容
6        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
7
8        if (arr.length < 2) {
9            return arr;
10        }
11        int middle = (int) Math.floor(arr.length / 2);
12
13        int[] left = Arrays.copyOfRange(arr, 0, middle);
14        int[] right = Arrays.copyOfRange(arr, middle, arr.length);
15
16        return merge(sort(left), sort(right));
17    }
18
19    protected int[] merge(int[] left, int[] right) {
20        int[] result = new int[left.length + right.length];
21        int i = 0;
22        while (left.length > 0 && right.length > 0) {
23            if (left[0] <= right[0]) {
24                result[i++] = left[0];
25                left = Arrays.copyOfRange(left, 1, left.length);
26            } else {
27                result[i++] = right[0];
28                right = Arrays.copyOfRange(right, 1, right.length);
29            }
30        }
31
32        while (left.length > 0) {
33            result[i++] = left[0];
34            left = Arrays.copyOfRange(left, 1, left.length);
35        }
36
37        while (right.length > 0) {
38            result[i++] = right[0];
39            right = Arrays.copyOfRange(right, 1, right.length);
40        }
41
42        return result;
43    }
44
45}
6. 快速排序 6.1 算法步骤

从数列中挑出一个元素,称为 “基准”(pivot);

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wsfpsj.html