排序算法那么多，我该怎么选

发表于

小知识，大挑战！本文正在参与“程序员必备小知识”创作活动。

本篇文章并不是讲解各排序算法的具体的实现，而是讲解排序算法的核心特性。通过理解各排序算法的核心特性，从而在具体的场景中能选择合适的排序算法。

各排序算法的具体实现和学习可参考：

《搞懂基本排序算法》

《大排序算法全面解析-Java实现》

《十大经典排序算法总结（JavaScript描述）》

冒泡排序和选择排序

冒泡排序和选择排序是最好理解、最容易的实现的两种排序算法。

冒泡排序：通过交换相邻两个元素，将最大元素升至最后位置（像水中的冒泡）

选择排序：遍历所有元素，选择最小元素，与未排好序的元素的一个元素进行交换。以此遍历n趟，最终达到所有元素有序。

适用场景：相对其他排序算法，除了实现简单、容易理解外，并没有任何任何优势。所以在实际开发中，并不推荐这两种排序算法，除非你实在写不出其他排序算法了。

插入排序

插入排序也是一种非常简单的排序，核心就是每次将某个元素插入到合适的位置，而该元素之后的所有元素都需要往后挪一个位置。在生活中玩扑克牌时，想要对扑克牌进行排序，我们通常使用的也是「插入」排序，比如大王，就插入到最前面。

具体实现：

1
2
3
4
5
6
7
ini复制代码public void sort(Comparable[] data) {
    for (int i = 1; i < data.length; i++) {
        for (int j = i; j - 1 > 0 && less(data[j], data[j - 1]); j--) {
            exch(data, j, j - 1);
        }
    }
}

说明：

  1. less(arg1, agr2) 方法为比较arg1,arg2大小，如果arg1小于arg2则返回true，否则返回false
  2. exch(data, j, j - 1) 为交换数组data中j和j-1位置。

适用场景：大部分数据距离它正确的位置很近，近乎有序，如原始数据根据订单完成时间排序，现在需要根据订单发起时间排序。这样，每个元素就能很快挪到正确位置，所以在这种场景中，其效率远高于其他元素。

快速排序

“快速排序是最快的通用排序算法”——《算法 第4版》

快速排序算法原理很简单，将数据分为两部分，其中一部分所有元素小于某个值，另外一部分所有元素大于某个值。然后再将这两部分的每一部分数据按刚才原则进行划分，以此类推，直至每部分只有一个元素。最终，数据就成为有序数据。

核心部分：

  1. 找出数据的标定点pivot，并将数据以标定点为间隔，分为两部分。

实现过程：

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
kotlin复制代码/**
 * 将data数组数据分成两部分，并返回划分位置j，使得左边部分小于data[j],右边部分大于data[j]
 * @param data
 * @param lo
 * @param hi
 * @return
 */
private int partition(Comparable[] data, int lo, int hi) {
    // 将第一个元素选为标定点
    Comparable pivot = data[lo];
    // 使用双指针遍历数组，使得数组左边部分小于pivot，右边部分大于pivot
    // i 表示 较小部分的最后一个元素（左侧）；j 表示  较大部分的第一个元素（右侧）。
    // 初始值设为lo和hi+1，即可表示未开始划分
    int i = lo;
    int j = hi + 1;
    while (true) {
        // 从左侧开始寻找第一个比pivot大或等于的元素
        while (less(data[++i], pivot)) {
            // 已遍历到右侧
            if (i >= hi) {
                break;
            }
        }
        // 从右侧开始寻找第一个比pivot小的元素
        while (less(pivot, data[--j])) {
            // 已遍历到右侧
            if (j <= lo) {
                break;
            }
        }
        if (j <= i) {
            break;
        }
        exch(data, i, j);
    }
    exch(data, lo, j);
    return j;
}
  1. 递归调用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
java复制代码/**
 * 对数组data[lo,hi]部分进行快速排序
 * @param data
 * @param lo
 * @param hi
 */
private void quickSort(Comparable[] data, int lo, int hi) {
    // 不需要再排了
    if (lo >= hi) {
        return;
    }
    int partition = partition(data, lo, hi);
    quickSort(data, lo, partition - 1);
    quickSort(data, partition + 1, hi);
}

适用场景：在大多数实际情况中，都适合使用快速排序。（但它不是稳定的排序算法，稳定是指：两个相等元素，排序前先后顺序与排序后先后顺序一致。比如元素a和元素b相等,排序前a在b前面，若排序后，a也b在前面，则说明其排序算法是稳定的）。

当包含大量重复的元素适合三路快排，三路快排是快速排序的优化版本，其核心思想与普通快速排序一致。但它多出「一路」为相等元素大小的处理。普通快速排序只找出一个标定点，即使其他元素与标定点相等，也还是会放入其余部分再次进行递归快速排序。

计数排序

计数排序核心原理：通过原数据取值范围大小的辅助数组，记录每个元素的出现的次数，然后再根据记录结果依次赋值。比如，对全省高考成绩进行排序。分数取值范围为0到750，记录每一分数的人数。最终在根据记录结果，依次重新赋值各分数已到达排序效果。

适合场景：数据的取值范围非常有限，比如对学生成绩排序、

归并排序

核心特性：将已排好序的两部分进行归并（合在一起）。

归并实现代码：

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
ini复制代码/**
 * 归并data[lo, hi]数组，data[lo,mid]有序数据，data[mid+1,hi]有序
 * @param data 原始数据
 * @param lo
 * @param mid
 * @param hi
 */
private void merge(Comparable[] data, int lo, int mid, int hi) {
    for (int k = lo; k <= hi; k++) {
        aux[k] = data[k];
    }
    int i = lo;
    int j = mid + 1;
    for (int k = lo; k <= hi; k++) {
        if (i > mid) {
            data[k] = aux[j++];
        } else if (j > hi) {
            data[k] = aux[i++];
        } else if (less(aux[i], aux[j])) {
            data[k] = aux[i++];
        } else {
            data[k] = aux[j++];
        }
    }
}

归并排序有两种实现方式：递归方式和非递归方式

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
scss复制代码/**
 * 将数组data[lo, hi]排序(递归方式)
 * @param data
 * @param lo
 * @param hi
 */
private void merge(Comparable[] data, int lo, int hi) {
    // 表示单个元素已有序
    if (lo >= hi) {
        return;
    }
    int mid = lo + (hi - lo) / 2;
    // 将data[lo,mid]部分排序
    merge(data, lo, mid);
    // 将data[mid+1, hi]部分排序
    merge(data, mid + 1, hi);
    // 将排好序部部分归并
    merge(data, lo, mid, hi);
}

非递归

1
2
3
4
5
6
7
8
9
10
11
css复制代码/**
 * 非递归的方式
 * @param data
 */
private void mergeBU(Comparable[] data) {
    for (int i = 1; i < data.length; i = i * 2) {
        for (int j = 0; j < data.length - i; j = j + i * 2) {
            merge(data, j, j + i - 1, Math.min(j + 2 * i - 1, data.length - 1));
        }
    }
}

堆排序

堆排序，借助堆特性（堆中某个结点的值总是不大于或不小于其父结点的值）获取最大元素，然后再使其变为堆。

堆的两个核心方法：

上浮（swim）：添加元素时，新元素上浮，使数据保持堆结构不变。

下沉（sink）：移除元素堆顶元素，把最后元素放置堆顶，再使其下沉到某个位置，保持堆结构不变

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
ini复制代码/**
 * 元素上升，调整成堆
 * @param data
 * @param k
 */
private void swim(Comparable[] data, int k) {
    while (k > 0 && less(data[(k - 1) / 2], data[k])) {
        exch(data, (k - 1) / 2, k);
        k = (k - 1) / 2;
    }
}

/**
 * 元素下层，调整成堆
 * @param data
 * @param k
 * @param length
 */
private void sink(Comparable[] data, int k, int length) {
    while ((k + 1) * 2 <= length) {
        int j = (k + 1) * 2 - 1;
        if (length > j + 1 && less(data[j],data[j + 1])) {
            j++;
        }
        // 节点的最大子节点小于当前节点，则不需要
        if (less(data[j], data[k])) {
            break;
        }
        exch(data, k, j);
        k = j;
    }
}

堆排序的实现：将数据变为堆结构，再根据堆特性将元素排序。

1
2
3
4
5
6
7
8
9
10
11
scss复制代码public void sort(Comparable[] data) {
    // 将数据组装成堆
    for (int i = data.length / 2 - 1; i >= 0; i--) {
        sink(data, i, data.length);
    }
    for (int i = data.length - 1; i > 0; i--) {
        // 将堆顶元素与最后一个元素交换
        exch(data, 0, i);
        sink(data, 0, i);
    }
}

总结

追求更快的性能是每个优秀程序员的必备素质。当需要对数据进行排序时，要根据实际情况来选择最合适的排序算法，而不是简单的「快速排序」走遍天下！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%