算法-排序

发表于 分类于
本文字数： 8.9k 阅读时长 ≈ 8 分钟

概述

排序算法 用于将无序数组转换为有序数组。常见排序算法有：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序。

我们将实现上述常见排序算法，并给出相应算法的时间复杂度、空间复杂度及稳定性。

  • 假定待排序数组中存在关键字相同的元素，我们使用排序算法排序该数组。如果排序前后，具有相同关键字的元素在数组中相对顺序保持不变，则该排序算法是稳定的。举例：以数组元素的第一个值为关键字排序数组 $a = [[1,11],[2,22],[1,9]]$，如果排序算法稳定，则排序结果中元素 $[1,11]$ 总是在元素 $[1,9]$ 之前。

  • 假定我们需要基于多关键字 $[a,b,c]$ 排序待排序数组，通常做法就是重新编写比较函数。如果一个排序算法是稳定的，我们还可以这样做：首先基于关键字 $a$ 排序待排序数组，随后基于关键字 $b$ 排序待排序数组，最后基于关键字 $c$ 排序待排序数组。

  • 冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序均基于比较元素实现排序，计数排序、桶排序、基数排序则不是如此。

实现

实现各排序算法之前，首先做如下声明：

  1. 为简化实现流程，假定数组元素中仅有关键字一项内容。
  2. 所有排序算法按照从小到大进行排序。

冒泡排序

冒泡排序的思想在于：遍历未排序部分数组，如果当前元素关键字大于下一个元素关键字，则交换二者，如此操作会将未排序部分数组中含最大关键字的元素逐步交换 (冒泡) 至排序部分数组首部/未排序部分数组尾部。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void bubbleSort(Integer[] objects) {
    // 每次循环可冒泡一个元素。为实现排序，只需冒泡objects.length-1次即可。
    for (int i = 0; i < objects.length - 1; i++) {
        // 遍历未排序部分数组。
        for (int j = 0; j < objects.length - i - 1; j++) {
            // 相邻元素关键字大小关系不符递增要求，则交换二者。
            if (objects[j] > objects[j + 1]) {
                Integer tmp = objects[j];
                objects[j] = objects[j + 1];
                objects[j + 1] = tmp;
            }
        }
    }
}

  • 时间复杂度

    排序算法使用双重循环，而且每次循环所需 $O(N)$ 时间，故而该算法的时间复杂度为 $O(N^2)$。

  • 空间复杂度

    排序算法需要一个额外空间以实现元素交换，故而该算法的空间复杂度为 $O(1)$。

  • 稳定性

    代码实现中，只有当前元素关键字大于下一个元素关键字，元素交换才会发生。如果当前元素关键字等于下一个元素关键字，交换不会发生，从而保证具有相同关键字元素之间的相对顺序保持不变，故而该算法是稳定的。

选择排序

选择排序的思想在于：遍历未排序部分数组，将其中含最小关键字的元素置于排序部分数组尾部。

选择排序与冒泡排序的区别有两点：

  1. 选择排序的排序部分数组位于未排序部分数组的前方，冒泡排序则正好相反。
  2. 选择排序将含最小关键字的元素置于排序部分数组尾部，冒泡排序则是将含最大关键字的元素置于排序部分数组首部。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void selectSort(Integer[] objects) {
    // 每次循环排序一个元素。为实现排序，只需循环objects.length-1次即可。
    for (int i = 0; i < objects.length - 1; i++) {
        // 记录当前位置下标。
        int k = i;
        // 遍历未排序部分数组，获取具有最小关键字的元素下标。
        for (int j = i + 1; j < objects.length; j++) {
            if (objects[j] < objects[k]) {
                k = j;
            }
        }
        // 如果当前位置与具有最小关键字的元素位置不同，则需交换二者(以此实现插入含最小关键字的元素至排序部分数组尾部)。
        if (k != i) {
            Integer tmp = objects[i];
            objects[i] = objects[k];
            objects[k] = tmp;
        }
    }
}

  • 时间复杂度

    排序算法使用双重循环，而且每次循环所需 $O(N)$ 时间，故而该算法的时间复杂度为 $O(N^2)$。

  • 空间复杂度

    排序算法需要两个额外空间，一个用于记录当前位置下标，一个用于实现元素交换，故而该算法的空间复杂度为 $O(1)$。

  • 稳定性

    代码实现中，从前往后遍历未排序部分数组以获取具有最小关键字的元素下标，并且只有当前元素的关键字小于当前最小关键字时才更新具有最小关键字的元素下标，如此两项操作足以保证具有相同关键字元素之间的相对顺序保持不变，故而该算法是稳定的。

插入排序

插入排序的思想在于：将未知元素依次插入至排序部分数组之中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void insertSort(Integer[] objects) {
    // 将未知元素插入至排序部分数组之中，故而从下标1处开始即可。
    for (int i = 1; i < objects.length; i++) {
        // 获取未知元素。
        Integer item = objects[i];
        int j;
        
        // 寻找插入位置，并插入。
        for (j = i - 1; j >= 0; j--) {
            if (objects[j] > item) {
                objects[j + 1] = objects[j];
            } else {
                break;
            }
        }
        objects[j + 1] = item;
    }
}

  • 时间复杂度

    排序算法使用双重循环，而且每次循环所需 $O(N)$ 时间，故而该算法的时间复杂度为 $O(N^2)$。

  • 空间复杂度

    排序算法需要两个额外空间，一个用于记录未知元素，一个用于记录插入位置，故而该算法的空间复杂度为 $O(1)$。

  • 稳定性

    寻找插入位置的代码实现中，只有当前元素的关键字大于未知元素的关键字，才将当前元素后移一位。另外，所有元素采用从前往后顺序依次插入。如此两项操作足以保证具有相同关键字元素之间的相对顺序保持不变，故而该算法是稳定的。

希尔排序

希尔排序是插入排序的一种改进版本。在插入排序中，为将未知元素插入至排序部分数组，我们需要按位后移元素。如果未知元素位于排序部分数组前部，则其所需后移元素过多。在希尔排序中，它基于步长将数组划分为若干子数组，对子数组实行插入排序，此时基于步长可将元素快速放至合适位置，最后通过逐步减少步长到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
// 开始位置为begin，步长为k所构建的子数组进行排序(过程类似插入排序)。
private void shell(Integer[] objects, int begin, int k) {
    for (int i = begin; i < objects.length; i = i + k) {
        Integer item = objects[i];
        int j;
        for (j = i - k; j >= 0; j = j - k) {
            if (objects[j] > item) {
                objects[j + k] = objects[j];
            } else {
                break;
            }
        }
        objects[j + k] = item;
    }
}

public void shellSort(Integer[] objects) {
    // 定义步长数组，最后一个元素一定为1。
    int[] steps = {5,3,1};
    // 逐步缩小步长。
    for (int i = 0; i < steps.length; i++) {
        // 按照步长对所有子数组进行插入排序。
        for (int j = 0; j < steps[i]; j++) {
            shell(objects, j, steps[i]);
        }
}

  • 时间复杂度

    其复杂度分析比较困难，而且不同步长具有不同的时间复杂度。这里给出一个大致的时间复杂度：$O(N^{3/2})$。

  • 空间复杂度

    基本与插入排序相同，故而该算法的空间复杂度为 $O(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
// 递归合并objects[l,r]中元素。
private void merge(Integer[] objects, int l, int r) {
    // 仅有一个元素，无需合并，直接返回即可。
    if (l >= r) {
        return ;
    }

    // 获取中间位置，递归合并左右部分子数组。
    int mid = (l + r) >> 1;
    merge(objects, l, mid);
    merge(objects, mid + 1, r);

    // 借助临时数组合并两个子数组。
    Integer[] tmp = new Integer[objects.length];
    int index1 = l, index2 = mid + 1, index3 = l;
    for (; index1 <= mid && index2 <= r;) {
        if (objects[index1] <= objects[index2]) {
            tmp[index3++] = objects[index1++];
        } else {
            tmp[index3++] = objects[index2++];
        }
    }

    while (index1 <= mid) {
        tmp[index3++] = objects[index1++];
    }
    while (index2 <= r) {
        tmp[index3++] = objects[index2++];
    }

    // 复制临时数组中内容至objects。
    for (int i = l; i <= r; i++) {
        objects[i] = tmp[i];
    }
}


public void mergeSort(Integer[] objects) {
    merge(objects, 0, objects.length - 1);
}

  • 时间复杂度

    记归并排序的时间复杂度为 $T(N)$，其中 $N$ 为待排序数组长度。

    根据递归过程，我们可得到：$T(N) = 2 \times T(N/2) + N$。求解该式，最终将得到：$T(N) = Nlog^N$。故而该算法的时间复杂度为 $O(Nlog^N)$。

  • 空间复杂度

    排序算法需要一个额外数组空间用于合并子数组、若干额外空间用于记录下标位置。故而该算法的空间复杂度为 $O(N)$。

  • 稳定性

    代码实现中，子数组合并过程可以保证具有相同关键字元素之间的相对顺序保持不变，故而该算法是稳定的。

快速排序

快速排序的思想在于：每个过程将数组中一个元素放置到正确位置 (即其前方元素的关键字均小于该元素的关键字，其后方元素的关键字均大于该元素的关键字)，随后递归处理左半部分和右半部分即可。

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
// 递归排序objects[l,r]中元素。(这是一个快排模板)
public void quick(Integer[] objects, int l, int r) {
    // 仅有一个元素，无需排序，直接返回即可。
    if (l >= r) {
        return ;
    }

    
    int i = l - 1, j = r + 1;
    Integer x = objects[(l + r) >> 1];

    // 调整元素顺序，使得x之前元素关键字均小于其关键字，x之后元素关键字均大于其关键字。
    while (i < j) {
        do {
            i++;
        } while (objects[i] < x);
        do {
            j--;
        } while (objects[j] > x);
        if (i < j) {
            Integer tmp = objects[i];
            objects[i] = objects[j];
            objects[j] = tmp;
        }
    }

    // 递归处理左右部分。
    quick(objects, l, j);
    quick(objects, j + 1, r);
}

public void quickSort(Integer[] objects) {
    quick(objects, 0, objects.length - 1);
}

  • 时间复杂度

    记快速排序的时间复杂度为 $T(N)$，其中 $N$ 为待排序数组长度。

    根据递归过程，我们可得到：$T(N) = 2 \times T(N/2) + N$。求解该式，最终将得到：$T(N) = Nlog^N$。故而该算法的时间复杂度为 $O(Nlog^N)$。

  • 空间复杂度

    排序算法需要若干额外空间用于记录下标位置，故而该算法的空间复杂度为 $O(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
// 调整index位置元素至堆中合适位置(堆结构从数组下标0开始，故而左儿子为2*index+1，右儿子为2*index+2)。
private void heap(Integer[] objects, int index, int end) {
    Integer x = objects[index];
    
    // 寻找合适位置。
    for (int j = 2 * index + 1; j <= end; j = 2 * j + 1) {
        if (j < end && objects[j] < objects[j + 1]) {
            j++;
        }
        if (objects[j] > x) {
            objects[index] = objects[j];
            index = j;
        } else {
            break;
        }
    }
    
    // 填入原本index位置的值。
    objects[index] = x;
}

// 堆排序
public void heapSort(Integer[] objects) {
    // 建堆过程。
    for (int i = objects.length / 2; i >= 0; i--) {
        heap(objects, i, objects.length - 1);
    }

    // 每次循环将堆顶元素与堆数组中最后一个元素交换，随后堆数组长度减一并调整堆顶元素。当堆数组长度为1时，该数组就是递增的。
    for (int i = objects.length - 1; i > 0; i--) {
        Integer tmp = objects[0];
        objects[0] = objects[i];
        objects[i] = tmp;

        heap(objects, 0, i - 1);
    }
}

  • 时间复杂度

    堆是一棵完全二叉树，其树高为 $O(log^N)$，故而 heap() 的时间复杂度为 $O(log^N)$。

    建堆过程的时间复杂度为 $O(N)$，循环操作的时间复杂度为 $O(Nlog^N)$，故而该算法的时间复杂度为 $O(N + Nlog^N) = O(Nlog^N)$。

  • 空间复杂度

    排序算法需要若干额外空间用于记录下标位置，故而该算法的空间复杂度为 $O(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
public void countSort(Integer[] objects) {
    // 构建额外数组，它指代关键字数据范围。
    Integer[] count = new Integer[MAX];
    Arrays.fill(count, 0);
    // 构建临时数组，用于存放排序结构。
    Integer[] sorted = new Integer[objects.length];

    // 统计关键字出现次数。
    for (int i = 0; i < objects.length; i++) {
        count[objects[i]]++;
    }

    // 构建前缀值，此时count[i]表示i应当位于元素数组中的下标位置(此部分作用类似于基数排序)。
    for (int i = 1; i < count.length; i++) {
        count[i] += count[i - 1];
    }

    // 根据count[i]将原始数组中元素依次放入到临时数组之中(必须为逆序放入)。
    for (int i = objects.length - 1; i >= 0; i--) {
        sorted[--count[objects[i]]] = objects[i];
    }
	
    // 拷贝排序结果至原始数组。
    for (int i = 0; i < objects.length; i++) {
        objects[i] = sorted[i];
    }
}

  • 时间复杂度

    排序算法的时间复杂度依赖于额外数组 (即关键字数据范围)，我们假定其长度为 $M$。

    排序算法实现中，多次需要遍历额外数组及原始数组。通常关键字数据范围远大于数组元素个数，故而该算法的时间复杂度为 $O(M + N) \approx O(M)$ 。

  • 空间复杂度

    排序算法的空间复杂度同样依赖于额外数组，故而该算法的空间复杂度为 $O(M)$。

  • 稳定性

    该算法是稳定的，其稳定性基于此实现——根据前缀值将原始数组中元素逆序放入临时数组。

基数排序

基数排序的思想在于：它将元素关键字 (限定为数字) 拆分为若干数位，例如 789 可拆分为 7\8\9 三个数位。从低到高依次对数位执行计数排序可实现排序元素。

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
// 假定关键字为十进制数字，则数位取值范围为[0,9]。
public void radixSort(Integer[] objects) {
    // 构建数位数组，它指代数位取值范围。
    Integer[] buckets = new Integer[10];
    // 构建临时数组，存储排序结果。
    Integer[] tmp = new Integer[objects.length];

    // 十进制数字第0位基数为1,第1位基数为10,...，主要用于求解指定位置的数位。
    Integer radix = 1;
    while (true) {
        // 按照从低到高排序数位，即首先根据个位排序，随后根据十位排序,...。
        
        // 重置数位数组。
        Arrays.fill(buckets, 0);
        
        // 统计数位出现次数。
        // (objects[i] / radix) % 10表示获取当前待处理位置的数位。
        for (int i = 0; i < objects.length; i++) {
            buckets[(objects[i] / radix) % 10]++;
        }

        // 如果所有元素当前位置的数位均为0，表明已无需再做排序，退出即可。
        if (buckets[0] == objects.length) {
            break;
        }

        // 构建前缀值。
        for (int i = 1; i < buckets.length; i++) {
            buckets[i] += buckets[i - 1];
        }

        // 根据数位信息将原始数组中元素逆序填入临时数组。
        for (int i = objects.length - 1; i >= 0; i--) {
            tmp[--buckets[(objects[i] / radix) % 10]] = objects[i];
        }

        // 拷贝排序结果至原始数组。
        for (int i = 0; i < objects.length; i++) {
            objects[i] = tmp[i];
        }

        // 更新数位为下一位。
        radix *= 10;
    }
}

  • 时间复杂度

    排序算法实现中，需要多次循环数位数组和原始数组。通常数位数组远小于原始数组，故而该算法的时间复杂度为 $O(N)$。

  • 空间复杂度

    排序算法需要使用数位数组及临时数组。如上所述，数位数组通常远小于原始数组，故而该算法的空间复杂度为 $O(N)$。

  • 稳定性

    就本质而言，基数排序基于多次使用计数排序而实现的。由于计数排序是稳定的，该算法亦是稳定的。

桶排序

桶排序十分简单，首先将数组元素映射到若干桶 (桶表示区间范围)，随后桶内排序元素，最后按序输出桶内元素即可。

如果将桶区间范围的大小限定为 1，此时桶排序就是计数排序。

桶排序比较简单，故而不再实现。