洪水淹没

guoshilong

2023-02-27 4d8c6dd77427e8e581fda17b6b65ba86bfb7a815

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
import defined from './defined.js';
import DeveloperError from './DeveloperError.js';
 
    var leftScratchArray = [];
    var rightScratchArray = [];
 
    function merge(array, compare, userDefinedObject, start, middle, end) {
        var leftLength = middle - start + 1;
        var rightLength = end - middle;
 
        var left = leftScratchArray;
        var right = rightScratchArray;
 
        var i;
        var j;
 
        for (i = 0; i < leftLength; ++i) {
            left[i] = array[start + i];
        }
 
        for (j = 0; j < rightLength; ++j) {
            right[j] = array[middle + j + 1];
        }
 
        i = 0;
        j = 0;
        for (var k = start; k <= end; ++k) {
            var leftElement = left[i];
            var rightElement = right[j];
            if (i < leftLength && (j >= rightLength || compare(leftElement, rightElement, userDefinedObject) <= 0)) {
                array[k] = leftElement;
                ++i;
            } else if (j < rightLength) {
                array[k] = rightElement;
                ++j;
            }
        }
    }
 
    function sort(array, compare, userDefinedObject, start, end) {
        if (start >= end) {
            return;
        }
 
        var middle = Math.floor((start + end) * 0.5);
        sort(array, compare, userDefinedObject, start, middle);
        sort(array, compare, userDefinedObject, middle + 1, end);
        merge(array, compare, userDefinedObject, start, middle, end);
    }
 
    /**
     * A stable merge sort.
     *
     * @exports mergeSort
     * @param {Array} array The array to sort.
     * @param {mergeSort~Comparator} comparator The function to use to compare elements in the array.
     * @param {*} [userDefinedObject] Any item to pass as the third parameter to <code>comparator</code>.
     *
     * @example
     * // Assume array contains BoundingSpheres in world coordinates.
     * // Sort them in ascending order of distance from the camera.
     * var position = camera.positionWC;
     * Cesium.mergeSort(array, function(a, b, position) {
     *     return Cesium.BoundingSphere.distanceSquaredTo(b, position) - Cesium.BoundingSphere.distanceSquaredTo(a, position);
     * }, position);
     */
    function mergeSort(array, comparator, userDefinedObject) {
        //>>includeStart('debug', pragmas.debug);
        if (!defined(array)) {
            throw new DeveloperError('array is required.');
        }
        if (!defined(comparator)) {
            throw new DeveloperError('comparator is required.');
        }
        //>>includeEnd('debug');
 
        var length = array.length;
        var scratchLength = Math.ceil(length * 0.5);
 
        // preallocate space in scratch arrays
        leftScratchArray.length = scratchLength;
        rightScratchArray.length = scratchLength;
 
        sort(array, comparator, userDefinedObject, 0, length - 1);
 
        // trim scratch arrays
        leftScratchArray.length = 0;
        rightScratchArray.length = 0;
    }
 
    /**
     * A function used to compare two items while performing a merge sort.
     * @callback mergeSort~Comparator
     *
     * @param {*} a An item in the array.
     * @param {*} b An item in the array.
     * @param {*} [userDefinedObject] An object that was passed to {@link mergeSort}.
     * @returns {Number} Returns a negative value if <code>a</code> is less than <code>b</code>,
     *          a positive value if <code>a</code> is greater than <code>b</code>, or
     *          0 if <code>a</code> is equal to <code>b</code>.
     *
     * @example
     * function compareNumbers(a, b, userDefinedObject) {
     *     return a - b;
     * }
     */
export default mergeSort;