常见排序及代码实现_2 代码

1 冒泡排序

1.1 排序说明

以升序为例，从第一个元素开始，和第二个元素相比，较小的放前面，然后第二个元素再和第三个元素对比，第三个和第四个…直到对比到最后一个元素，整个过程就像不断在冒泡一样，并且一轮冒泡下来，可以保证最大的元素一定被移到了最后；然后继续第二轮冒泡，还是从第一个元素开始，只不过这次只需冒泡到倒数第二个元素…如此反复，就能完成排序了。

1.2 时间复杂度

O(n²)

s = (n - 1) + (n -2) + (n - 3) + … + 2 + 1 + 0
   = n * (n- 1) / 2
   = ½n² - ½n

取最大影响因子，即½n²，再去除系数，得出时间复杂度：O(n²)

1.3 代码实现

1.3.1 Java代码

package sort;

import java.util.Arrays;

public class BubbleSort {
    private static void sort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]){
                    arr[j] = arr[j]^arr[j + 1];
                    arr[j + 1] = arr[j]^arr[j + 1];
                    arr[j] = arr[j]^arr[j + 1];
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 1, 6, 5, 0};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

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

1.3.2 Python代码

def sort(arr):
    length = len(arr)
    for i in range(length - 1):
        for j in range(length - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]


if __name__ == '__main__':
    arr = [2, 3, 1, 6, 5, 0]
    sort(arr)
    print(arr)
1
2
3
4
5
6
7
8
9
10
11
12

1.3.3 JavaScript代码

function sort(arr){
    for (let i = 0; i < arr.length - 1; i++) {
        for (let j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]){
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
            }
        }
    }
}

let arr = [2, 3, 1, 6, 5, 0];
sort(arr);
console.log(arr);
1
2
3
4
5
6
7
8
9
10
11
12
13

2 选择排序

2.1 排序说明

以升序为例，从第一个元素开始，和第二个元素相比，如果比第一个元素小，就互换位置，然后第一个再和第三个比，第四个比，…，直到和最后一个元素比，可以看到，每次都是选择和第一个元素比较，并且这样一轮选择比较下来，可以确定第一个元素一定是最小的元素；然后再接着第二轮比较，不过这次选择和第二个元素比较，…，如此反复，就能完成排序了。

2.2 时间复杂度

O(n²)，情况和冒泡排序完全一样，只不过一个是通过冒泡的方式比较相邻元素，一个是选择的方式和某一个元素比较，但是二者每轮比较的次数时完全一样的。

2.3 代码实现

2.3.1 Java代码

package sort;

import java.util.Arrays;

public class ChooseSort {
    private static void sort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]){
                    arr[i] = arr[i]^arr[j];
                    arr[j] = arr[i]^arr[j];
                    arr[i] = arr[i]^arr[j];
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 1, 6, 5, 0};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.3.2 Python代码

def sort(arr):
    for i in range(len(arr) - 1):
        for j in range(i + 1, len(arr)):
            if arr[i] > arr[j]:
                arr[i], arr[j] = arr[j], arr[i]


if __name__ == '__main__':
    arr = [2, 3, 1, 6, 5, 0]
    sort(arr)
    print(arr)
1
2
3
4
5
6
7
8
9
10
11

2.3.3 JavaScript代码

function choose(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[i] > arr[j]){
                [arr[j], arr[i]] = [arr[i], arr[j]]
            }
        }
    }
}

let arr = [2, 3, 1, 6, 5, 0];
choose(arr);
console.log(arr);

1
2
3
4
5
6
7
8
9
10
11
12
13
14

3 插入排序

3.1 排序说明

插入排序和冒泡、选择相比，后者都是和后面的元素比较，而插入则是和前面的元素比较，以升序为例，第一个元素没有前一个元素，所以从第二个元素开始，和第一个元素比较，如果第二个元素小，就把第二个元素插入到第一个元素的位置，这也就意味着要将被插入的元素到插入元素之间的所有元素整体往后移动一个位置；然后开始第三个元素，和第一个元素比较、再和第二个元素比较，如果发现比自己大，就进行插入操作，和前面的所有元素都要依次进行比较之后，就能保证前面的所有元素总是升序的，等到最后一个元素和前面的所有元素都比较完成，那么整体排序也就完成了。

3.2 时间复杂度

第一次比较，也就是第二个元素和第一个元素比较，只比较了1次，第二次是第三个元素和前两个元素比较，所以有2次，最后一个则是和前 n - 1 个进行比较，所以整体下来，时间复杂度和冒泡、选择的一样，都是：O(n²)。

3.3 代码实现

3.3.1 Java代码

package sort;

import java.util.Arrays;

public class InsertSort {
    private static void sort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[i]){
                    int tmp = arr[i];
                    for (int k = i; k > j; k--) {
                        arr[k] = arr[k - 1];
                    }
                    arr[j] = tmp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 1, 6, 5, 0};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
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

3.3.2 Python代码

def sort(arr):
    for i in range(1, len(arr)):
        for j in range(i):
            if arr[j] > arr[i]:
                tmp = arr[i]
                arr[j + 1: i + 1] = arr[j:i]  # 注：分片前闭后开
                arr[j] = tmp


if __name__ == '__main__':
    arr = [2, 3, 1, 6, 5, 0]
    sort(arr)
    print(arr)

1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.3.3 JavaScript代码

function insert(arr) {
    for (let i = 1; i < arr.length; i++) {
        for (let j = 0; j < i; j++) {
            if (arr[j] > arr[i]){
                let tmp = arr[i];
                for (let k = i; k > j; k--) {
                    arr[k] = arr[k - 1];
                }
                arr[j] = tmp;
            }
        }
    }
}

let arr = [2, 3, 1, 6, 5, 0];
insert(arr);
console.log(arr);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

4 堆排序

4.1 排序说明

以升序为例，可以分成两步：

1. 初始化
   将数组构建成一个大根堆。堆构建：常见数据结构及代码实现
2. 堆调整
   经过堆的初始化，知首元素最大，所以将第一个元素和最后一个元素互换，这样最后一个元素就是最大值；接着开始做堆调整，由于最后一个元素已经确定，所以调整的范围是第一个元素到倒数第二个元素，并且只是第一个元素和最后一个元素进行了互换打乱了原本的大根堆，所以只需要对第一个元素做调整，调整之后就又是一个大根堆，于是第一个元素又是最大值，再和倒数第二个元素互换，就可以确定倒数第二个元素…如此反复调整，就可以完成升序了。

4.2 时间复杂度

1. 初始化堆构建的时间复杂度
   O(n) 。具体计算过程：常见数据结构及代码实现
2. 堆调整的时间复杂度
   O(nlog₂n)，推导过程如下（自己推的，如有问题欢迎指正）：

       所以，总时间复杂度为：

---

       s = 2¹ * 1 + 2² * 2 + … + 2ʰ⁻² * (h - 2) + 2ʰ⁻¹ * (h - 1)

---

       2s = 2² * 1 + 2³ * 2 + … + 2ʰ⁻¹ * (h - 2) + 2ʰ * (h - 1)

---

       s - 2s = 2¹ + 2² + 2³ + … + 2ⁿ⁻¹ - 2ʰ(h - 1)
                 = 2¹ (1 - 2ʰ⁻¹) / (1 - 2) - 2ʰ(h - 1)
                 = 2ʰ - 2 - 2ʰ(h - 1)

---

       将：h = log₂n + 1（n节点数）代入：

---

       s = 2ʰ(h - 1) + 2 - 2ʰ
          = 2ʰ(h - 2) + 2
          = 2nlog₂n - 2n + 2

---

       取最大影响因子，即2nlog₂n，再去除系数，得出时间复杂度：O(nlog₂n)

---

4.3 代码实现

4.3.1 Java代码

package sort;

public class HeapSort {
    private int leftNodeIndex(int todoNodeIndex){
        return (todoNodeIndex + 1) * 2 - 1;
    }
    private int rightNodeIndex(int todoNodeIndex){
        return (todoNodeIndex + 1) * 2;
    }
    private int parentNodeIndex(int todoNodeIndex){
        return (todoNodeIndex + 1) / 2 - 1;
    }

    /**
     * 调整节点，用于构建大根堆
     *
     * @param heap 构建中的堆数组容器
     * @param todoNodeIndex 待进行调整的节点
     * @param heapLength 构建中的堆数组容器的长度
     */
    @SuppressWarnings("unchecked")
    private void adjust(Comparable[] heap, int todoNodeIndex, int heapLength){
        int leftNodeIndex = leftNodeIndex(todoNodeIndex);
        int rightNodeIndex = rightNodeIndex(todoNodeIndex);
        int biggestNodeIndex = todoNodeIndex;
        if (leftNodeIndex < heapLength){
            biggestNodeIndex = heap[biggestNodeIndex].compareTo(heap[leftNodeIndex]) < 0 ? leftNodeIndex : biggestNodeIndex;
        }
        if (rightNodeIndex < heapLength){
            biggestNodeIndex = heap[biggestNodeIndex].compareTo(heap[rightNodeIndex]) < 0 ? rightNodeIndex : biggestNodeIndex;
        }
        if (biggestNodeIndex == todoNodeIndex) return;
        Comparable biggestNodeValue = heap[biggestNodeIndex];
        heap[biggestNodeIndex] = heap[todoNodeIndex];
        heap[todoNodeIndex] = biggestNodeValue;
        adjust(heap, biggestNodeIndex, heapLength);
    }

    private void create(Comparable[] heap){
        int parentNodeIndex = parentNodeIndex(heap.length - 1);
        for (int i = parentNodeIndex; i >= 0; i--) {
            adjust(heap, i, heap.length);
        }
    }

    public void sort(Comparable[] heap){
        //先初始化：构建大根堆
        create(heap);
        //再进行堆排序：对每个节点进行堆调整
        for (int i = heap.length - 1; i > 0; i--) {
            //先将前一轮的调整进行处理：调换首尾
            Comparable biggestNodeValue = heap[0];
            heap[0] = heap[i];
            heap[i] = biggestNodeValue;
            //互换后继续下一轮调整
            adjust(heap, 0, i);
        }
    }
}

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

import org.junit.Test;
import sort.HeapSort;
import java.util.Arrays;

public class HeapSortTest {
    @Test
    public void test(){
        HeapSort heapSort = new HeapSort();
        Comparable[] arr = {9, 5, 12, 9, 15, 16, 7, 21, 19};
        heapSort.sort(arr);
        System.out.println(Arrays.toString(arr)); //[5, 7, 9, 9, 12, 15, 16, 19, 21]
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

4.3.2 Python代码

def get_left_node_index(todo_node_index):
    return (todo_node_index + 1) * 2 - 1


def get_right_node_index(todo_node_index):
    return (todo_node_index + 1) * 2


def get_parent_node_index(todo_node_index):
    return (todo_node_index + 1) // 2 - 1


def adjust(heap, todo_node_index, heap_length):
    left_node_index = get_left_node_index(todo_node_index)
    right_node_index = get_right_node_index(todo_node_index)
    biggest_node_index = todo_node_index
    if left_node_index < heap_length:
        biggest_node_index = [biggest_node_index, left_node_index][heap[biggest_node_index] < heap[left_node_index]]
    if right_node_index < heap_length:
        biggest_node_index = [biggest_node_index, right_node_index][heap[biggest_node_index] < heap[right_node_index]]
    if biggest_node_index == todo_node_index:
        return
    heap[todo_node_index], heap[biggest_node_index] = heap[biggest_node_index], heap[todo_node_index]
    adjust(heap, biggest_node_index, heap_length)


def create(heap):
    first_parent_node_index = get_parent_node_index(len(heap) - 1)
    for i in range(first_parent_node_index, -1, -1):
        adjust(heap, i, len(heap))


def sort(heap):
    create(heap)
    for i in range(len(heap) - 1, 0, -1):
        heap[0], heap[i] = heap[i], heap[0]
        adjust(heap, 0, i)


if __name__ == '__main__':
    arr = [9, 5, 12, 9, 15, 16, 7, 21, 19]
    sort(arr)
    print(arr)  # [5, 7, 9, 9, 12, 15, 16, 19, 21]

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

4.3.3 JavaScript代码

let getLeftNodeIndex = (todoNodeIndex => (todoNodeIndex + 1) * 2 - 1);
let getRightNodeIndex = (todoNodeIndex => (todoNodeIndex + 1) * 2);
let getParentNodeIndex = (todoNodeIndex => parseInt((todoNodeIndex + 1) / 2 + "") - 1);
let adjust = ((heap, todoNodeIndex, heapLength) => {
    let leftNodeIndex = getLeftNodeIndex(todoNodeIndex);
    let rightNodeIndex = getRightNodeIndex(todoNodeIndex);
    let biggestNodeIndex = todoNodeIndex;
    if (leftNodeIndex < heapLength) biggestNodeIndex = heap[biggestNodeIndex] < heap[leftNodeIndex] ? leftNodeIndex : biggestNodeIndex;
    if (rightNodeIndex < heapLength) biggestNodeIndex = heap[biggestNodeIndex] < heap[rightNodeIndex] ? rightNodeIndex : biggestNodeIndex;
    if (biggestNodeIndex === todoNodeIndex) return;
    [heap[todoNodeIndex], heap[biggestNodeIndex]] = [heap[biggestNodeIndex], heap[todoNodeIndex]];
    adjust(heap, biggestNodeIndex, heapLength);
});
let create = (heap => {
    let parentNodeIndex = getParentNodeIndex(heap.length - 1);
    for (let i = parentNodeIndex; i >= 0; i--) {
        adjust(heap, i, heap.length);
    }
});
let sort = (heap => {
    create(heap);
    for (let i = heap.length - 1; i > 0; i--) {
        [heap[0], heap[i]] = [heap[i], heap[0]];
        adjust(heap, 0, i);
    }
});

let arr = [9, 5, 12, 9, 15, 16, 7, 21, 19];
sort(arr);
console.log(arr);

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

5 快速排序

5.1 排序说明

快速排序，是一种高级的选择排序，都有一个基准数的概念，即从数组中选择的一个用于同其他元素进行对比的元素。
以升序为例，快速排序的也选择从第一个元素开始作为基准数，然后从最后一个元素开始进行对比，如果最后一个元素比基准数大，则继续从后往前用倒数第二个元素和基准数做对比，直到有某个数比基准数还小，这时记录下这个数的索引（假设是higherIndex）、调转方向，从第一个元素开始和基准数对比，和从后往前对比不同的是，只要对比的数比基准数小则继续从前往后继续对比，直到某个元素比基准数大，一样记录这个元素索引（假设是lowerIndex）。
然后，互换higherIndex和lowerIndex的值。
接着，从higherIndex前一个元素、再次从后往前开始做同样的对比…对比到最后，就可以保证：基准数左边的元素都比基准数小、基准数右边的元素都比基准数大。
以上就是一轮对比的过程，接着就是以递归的方式，将基准数左右两边元素都视为一个新数组，然后都进行一轮同样的操作，循环反复，就能实现排序了。

5.2 时间复杂度

通常，视快速排序的事件复杂度为：O(nlog₂n)

5.2.1 最优时间复杂度

O(nlog₂n)。

计算过程如下：

f(n) = 2 * f(n/2) + n
      = 2 * (2 * f(n/4) + n/2) + n
      = 2² * f(n/4) + 2n
      = 2² * (2 * f(n/8) + n/4) + 2n
      = 2³ * f(n/8) + 3n
      = …
      = 2ᵐ * f(n/2ᵐ) + mn

---

又当 m ⇒ +∞ 时，n/2ᵐ = 1，得：

---

f(n) = 2ᵐ * f(n/2ᵐ) + mn
      = 2ᵐ * f(1) + log₂n * n

---

又当n = 1，即只有一个元素时，无需计算，即：f(1) = 0，所以：

---

f(n) = 2ᵐ * f(1) + log₂n * n
      = log₂n * n

5.2.2 最坏时间复杂度

O(n²)。
当基准数每次分割数组时，如果原数组本身就是有序（正序或者逆序），则形成的新数组，有一个为空，另一边则为 n - 1 个元素，此时有最坏时间复杂度。知此时树高为 n，即需要 n 次递归，且第 n 次递归，就要比较 n 次，故总时间复杂度为：1 + 2 + 3 + … + n = n * (n + 1) / 2
PS：理论上每一轮比较应该是可以做到比较 n - 1 次，如第一次比较，总共5个元素，比较4次，所以这里应该是 1 加到 n - 1，但是如果这样，那么最优时间复杂度中也应该是：2 * f(n/2) + (n - 1)，所以仅为了保持一致，总之明白其意即可

5.2.3 期望时间复杂度

O(nlog₂n)。

5.3 代码实现

5.3.1 Java代码实现

package sort;

import java.util.Arrays;

public class QuickSort {
    private static void sort(int[] arr, int originLowerIndex, int originHigherIndex) {
        if (originLowerIndex >= originHigherIndex) return;
        int baseNumber = arr[originLowerIndex]; //基准数
        int lowerIndex = originLowerIndex;
        int higherIndex = originHigherIndex;
        while (lowerIndex < higherIndex) {
            //从后往前和基准数做对比
            while (lowerIndex < higherIndex && baseNumber <= arr[higherIndex]) {
                higherIndex--;
            }
            //从前往后和基准数做对比
            while (lowerIndex < higherIndex && baseNumber >= arr[lowerIndex]) {
                lowerIndex++;
            }
            //互换
            if (lowerIndex < higherIndex) {
                int tmp = arr[lowerIndex];
                arr[lowerIndex] = arr[higherIndex];
                arr[higherIndex] = tmp;
            }
        }
        arr[originLowerIndex] = arr[lowerIndex];//此时lowerIndex = higherIndex，使用higherIndex亦可
        arr[lowerIndex] = baseNumber;
        //将基准数左右的元素视作一个数组，继续执行操作
        sort(arr, originLowerIndex, lowerIndex);
        sort(arr, higherIndex + 1, originHigherIndex);
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 1, 6, 5, 0, 3};
        sort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr)); //[0, 1, 2, 3, 3, 5, 6]
    }
}

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

5.3.2 Python代码实现

def sort(arr, origin_lower_index, origin_higher_index):
    if origin_lower_index >= origin_higher_index:
        return
    base_number = arr[origin_lower_index]
    lower_index = origin_lower_index
    higher_index = origin_higher_index
    while lower_index < higher_index:
        while lower_index < higher_index and base_number <= arr[higher_index]:
            higher_index -= 1
        while lower_index < higher_index and base_number >= arr[lower_index]:
            lower_index += 1
        if lower_index < higher_index:
            arr[lower_index], arr[higher_index] = arr[higher_index], arr[lower_index]
    arr[origin_lower_index], arr[lower_index] = arr[lower_index], arr[origin_lower_index]
    sort(arr, origin_lower_index, lower_index)
    sort(arr, higher_index + 1, origin_higher_index)


if __name__ == '__main__':
    arr = [9, 5, 12, 9, 15, 16, 7, 21, 19]
    sort(arr, 0, len(arr) - 1)
    print(arr)  # [5, 7, 9, 9, 12, 15, 16, 19, 21]

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

5.3.3 JavaScript代码实现

function sort(arr, originLowerIndex, originHigherIndex){
    if (originLowerIndex >= originHigherIndex) return;
    let lowerIndex = originLowerIndex;
    let higherIndex = originHigherIndex;
    let baseNumber = arr[originLowerIndex];
    while (higherIndex > lowerIndex) {
        while (higherIndex > lowerIndex && baseNumber <= arr[higherIndex]) {
            higherIndex--;
        }
        while (higherIndex > lowerIndex && baseNumber >= arr[lowerIndex]) {
            lowerIndex++;
        }
        if (higherIndex > lowerIndex) {
            [arr[lowerIndex], arr[higherIndex]] = [arr[higherIndex], arr[lowerIndex]];
        }
    }
    [arr[lowerIndex], arr[originLowerIndex]] = [arr[originLowerIndex], arr[lowerIndex]];
    sort(arr, originLowerIndex, lowerIndex);
    sort(arr, higherIndex + 1, originHigherIndex);
}

let arr = [9, 5, 12, 9, 15, 16, 7, 21, 19];
sort(arr, 0, arr.length - 1);
console.log(arr); //[5, 7, 9, 9, 12, 15, 16, 19, 21]

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

6 归并排序

6.1 排序说明

以升序为例，对于两个有序数组，首先创建一个临时数组（长度为两个有序数组长度之和），然后两个有序数组从左往右依次取出元素并对比，将较小者放入临时数组中，接着继续取出较小元素所在数组的下一个元素，再次和较大者进行比较，如果此时较大者数值小，则转而从它所在的数组中取下一个元素用来比较，…，通过这样的方式，最终就将能将两个有序数组合并成一个有序数组。
对于归并排序而言，首先是将一个无序数组进行不断地从中部一分为二切分成两个数组，两个数组再各自一分为二切成4个数组，…，直到每个数组都被切分成单个元素，这样做的目的是：单个元素总是有序的；接着，再以切分时相反的顺序，将两个单元素合成一个有序的两个元素数组，两个有序的各自包含两个元素的数组则合成一个有序的四个元素的数组，…，如此就能完成排序了。

6.2 时间复杂度

O(nlog₂n)。

从每次有中间将数组一分为二、每次合并数组总对比元素个数为n，知归并排序的时间复杂度计算 同 快速排序的最优时间复杂度情形。

6.3 代码实现

6.3.1 Java代码实现

package sort;

import java.util.Arrays;

public class MergeSort {
    /**
     * 将无需数组切分成单元素数组过程
     *
     * @param arr        待排序的无序数组
     * @param leftIndex  最小索引
     * @param rightIndex 最大索引
     */
    private static void sort(int[] arr, int leftIndex, int rightIndex) {
        if (leftIndex >= rightIndex) return; //当只有单个元素时无序再切分，此时跳出递归
        int middleIndex = (leftIndex + rightIndex) / 2;
        sort(arr, leftIndex, middleIndex);
        sort(arr, middleIndex + 1, rightIndex);
        merge(arr, leftIndex, rightIndex, middleIndex);
    }

    /**
     * 合并两个有序数组为一个有序数组过程
     *
     * @param arr              待排序的无序数组
     * @param originLeftIndex  待切分成两个数组的数组的起始索引
     * @param originRightIndex 待切分成两个数组的数组的终止索引
     * @param middleIndex      切分点
     */
    private static void merge(int[] arr, int originLeftIndex, int originRightIndex, int middleIndex) {
        int[] tmpArr = new int[originRightIndex - originLeftIndex + 1];//创建一个临时数组作为合并后的有序数组
        int tmpArrIndex = 0;//临时数组的起始索引
        int leftIndex1 = originLeftIndex;//第一个有序数组的起始索引
        int rightIndex1 = middleIndex;//第一个有序数组的终止索引
        int leftIndex2 = middleIndex + 1;//第二个有序数组的起始索引
        int rightIndex2 = originRightIndex;//第二个有序数组的终止索引
        //对比两个有序数组，合并为一个有序数组的过程
        while ((leftIndex1 <= rightIndex1) && (leftIndex2 <= rightIndex2)) {
            if (arr[leftIndex1] < arr[leftIndex2]) {
                tmpArr[tmpArrIndex++] = arr[leftIndex1++];
            } else {
                tmpArr[tmpArrIndex++] = arr[leftIndex2++];
            }
        }
        //如果第一个有序数组仍有未进行对比的元素，则追加到临时数组中
        while (leftIndex1 <= rightIndex1) {
            tmpArr[tmpArrIndex++] = arr[leftIndex1++];
        }
        //如果第二个有序数组仍有未进行对比的元素，则追加到临时数组中
        while (leftIndex2 <= rightIndex2) {
            tmpArr[tmpArrIndex++] = arr[leftIndex2++];
        }
        //将合并好的有序数组替换到原始数组的对应位置上
        for (int i = 0; i < tmpArr.length; i++) {
            arr[originLeftIndex++] = tmpArr[i];
        }
    }

    public static void main(String[] args) {
        int[] arr = {9, 5, 12, 9, 15, 16, 7, 21, 19};
        sort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr)); //[5, 7, 9, 9, 12, 15, 16, 19, 21]
    }
}

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

6.3.2 Python代码实现

def sort(arr, left_index, right_index):
    if left_index >= right_index:
        return
    middle_index = (left_index + right_index) // 2
    sort(arr, left_index, middle_index)
    sort(arr, middle_index + 1, right_index)
    merge(arr, left_index, right_index, middle_index)


def merge(arr, origin_left_index, origin_right_index, middle_index):
    tmp_arr = []
    left_index_1 = origin_left_index
    right_index_1 = middle_index
    left_index_2 = middle_index + 1
    right_index_2 = origin_right_index
    while (left_index_1 <= right_index_1) and (left_index_2 <= right_index_2):
        if arr[left_index_1] < arr[left_index_2]:
            tmp_arr.append(arr[left_index_1])
            left_index_1 += 1
        else:
            tmp_arr.append(arr[left_index_2])
            left_index_2 += 1
    while left_index_1 <= right_index_1:
        tmp_arr.append(arr[left_index_1])
        left_index_1 += 1
    while left_index_2 <= right_index_2:
        tmp_arr.append(arr[left_index_2])
        left_index_2 += 1
    for i in range(origin_left_index, origin_right_index + 1):
        arr[i] = tmp_arr[i - origin_left_index]


if __name__ == '__main__':
    arr = [9, 5, 12, 9, 15, 16, 7, 21, 19]
    sort(arr, 0, len(arr) - 1)
    print(arr)  # [5, 7, 9, 9, 12, 15, 16, 19, 21]

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

6.3.3 JavaScript代码实现

function sort(arr, leftIndex, rightIndex) {
    if (leftIndex >= rightIndex) return;
    let middleIndex = parseInt((leftIndex + rightIndex) / 2 + "");
    sort(arr, leftIndex, middleIndex);
    sort(arr, middleIndex + 1, rightIndex);
    merge(arr, leftIndex, rightIndex, middleIndex);
}

function merge(arr, originLeftIndex, originRightIndex, middleIndex) {
    let tmpArr = [];
    let leftIndex1 = originLeftIndex;
    let rightIndex1 = middleIndex;
    let leftIndex2 = middleIndex + 1;
    let rightIndex2 = originRightIndex;
    while ((leftIndex1 <= rightIndex1) && (leftIndex2 <= rightIndex2)) {
        if (arr[leftIndex1] < arr[leftIndex2]) {
            tmpArr.push(arr[leftIndex1++])
        } else {
            tmpArr.push(arr[leftIndex2++])
        }
    }
    while (leftIndex1 <= rightIndex1) {
        tmpArr.push(arr[leftIndex1++])
    }
    while (leftIndex2 <= rightIndex2) {
        tmpArr.push(arr[leftIndex2++])
    }
    for (let i = 0; i < tmpArr.length; i++) {
        arr[i + originLeftIndex] = tmpArr[i];
    }
}

let arr = [9, 5, 12, 9, 15, 16, 7, 21, 19];
sort(arr, 0, arr.length - 1);
console.log(arr); //[5,  7,  9,  9, 12, 15, 16, 19, 21]

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