最全面的排序算法详解——冒泡、插入、归并、快速...._插入 快速 冒泡 基准 合并

本教程旨在最全面的介绍排序算法包括原理与性能方面的比较。下文中的排序算法都以升序为例进行讲解。

1.冒泡排序

以数组42,3,12,25,9,21为例

基本思想：

相邻的两个数相比较，如果前面的数大于后面的数，就交换两个数，否则不改变数组

按照基本思想，第一次比较42与3，发现42>3，从而交换42与3的次序，其中蓝色表示比较后的较小值，红色表示比较后的较大值

第二次比较42与12，发现42>12，从而交换42与12的次序

第三次比较42与25，发现42>25，从而交换42与25的次序

第四次比较42与9，发现42>9，从而交换42与9次序

第五次比较42与21，发现42>21，从而交换42与21的次序

经过一轮的比较后，42最大数被交换到了最后，使用同样的方法，经过第二轮比较后，数组变为

此时25被交换到了42的前面；依此下去，再经过3轮后，数组变为有序

代码实现：

#include <iostream>
const int SIZE = 6;
using std::cout;
using std::endl;

void Show(int *arr, int len);
void Swap(int *arr, int i, int j);
void bubble_sort(int *arr, int len);

int main() {
    int a[SIZE] = { 42, 3, 12, 25, 9, 21 };
    cout << "before sort: ";
    Show(a, SIZE);
    bubble_sort(a, SIZE);
    cout << "after sort: ";
    Show(a, SIZE);
    return 0;
}

void Show(int *arr, int len){
    for (int i = 0; i<SIZE; i++)
        cout << arr[i] << " ";
    cout << endl;
}

void Swap(int *arr, int i, int j) {
    int temp;
    temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
// 冒泡排序
void bubble_sort(int *arr, int len) {
    for (int i = 0; i < len - 1; i++) {
        for (int j = 0; j < len - i - 1; j++) {
            if (arr[j] > arr[j + 1])
                Swap(arr, j, j + 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

从程序中可以看到冒泡排序的时间复杂度为O(N^2)，空间复杂度为O(1)

2. 插入排序

基本思想：

在前面有序的数组基础上，插入新的元素，使得数组有序

原始数组：

具体过程如下
第一次：

第二次：

第三次：

第四次：

第五次：

第六次：

经过6轮后，数组变为有序。

插入方法主要有两种

1.折半查找找到插入点，插入点后面的元素右移，待插入元素插入到插入点；
2.待插入元素从已排序数组的后面往前面遍历，如果遍历到的元素比待入元素大，则交换两个元素，否则表示找到了插入点并停止遍历。

这里采用第2种方法作为代码实现：

// 插入排序
void insert_sort(int *arr, int len) {
    // 带插入元素角标i
    for (int i = 1; i < len; i++) {
        // 从后往前比较
        for (int j = i-1; j >=0; j--) {
            // 如果大于则交换
            if (arr[j] > arr[j+1])
                Swap(arr, j, j+1);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

插入排序的时间复杂度为O(N^2)，空间复杂度为O(1)

3. 选择排序

基本思想：

找到待排序数组中最小值的位置，然后将最小值与待排序数组头部交换

原始数组：

具体过程如下：
第一次：虚线框内表示待排序数组，红色表示待排序数组中的最小值

第二次：

第三次：

第四次：

第五次：

经过五轮后，数组变为有序

代码实现：

void select_sort(int *arr, int len) {
    for (int i = 0; i < len - 1; i++) {
        int idx = i;
        // 获取待排序数组中最小值角标
        for (int j = i + 1; j < len; j++) {
            if (arr[j] < arr[idx])
                idx = j;
        }
        Swap(arr, idx, i);
    }
}
1
2
3
4
5
6
7
8
9
10
11

4. 希尔排序

基本思想：

插入排序元素移动次数太多，从而每次取一定间隔作为增量，以增量进行插入排序，减少移动次数。开始增量可以取很大，后面越来越小，直至增量为1

原始数组：

具体过程如下

第一次增量为4，对42,9,33进行插入排序

第二次增量为2，对9,12,33，，17,42进行插入排序

第三次增量为1，即普通的插入排序

经过三轮后，数组变为有序

从以上过程可以看出，对于取不同的增量，算法的性能可能会不一样，关于希尔排序增量的取值问题，也有许多相关的研究，下面的算法以一种常用的增量为例，其采用以下公式迭代生成：

$$h_{i+1} = 3*h_{i} + 1$$
通过计算：得到
$$h_0=1$$
$$h_1=3*h_0+1=4$$
$$h_2=3*h_1+1=13$$
$$.....$$

比如对于长度超过14的数组，可以先取增量为13，再取增量为4，最后取增量为1

算法实现：

void shell_sort(int *arr, int len) {
    int h = 1;
    // 找到最大增量
    while (h <= len / 3)
        h = 3 * h + 1;
    while (h >= 1) {
        // 以增量h执行插入排序
        for (int i = h; i < len; i += h) {
            for (int j = i - h; j >= 0; j -= h) {
                if (arr[j] > arr[j + h])
                    Swap(arr, j, j + h);
            }
        }
        //增量递减
        h = (h - 1) / 3;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

希尔排序的时间复杂度根据所选增量不同也有所不同，选取Hibbard增量时间复杂度可以达到$O(N^{3/2})$，关于希尔排序时间复杂度更详细的说明可以看这里，而空间复杂度为O(1)

5. 归并排序

基本思想：

前提：将两个有序的数组合并为新的有序数组，所需时间复杂度为O(N)
思路：采用分治的思想，先使用归并排序将原数组的左侧与右侧变为有序，最后合并左侧与右侧两个有序数组为新的有序数组即为排序好的数组

归并排序过程：

以最后一次归并来解释如何合并两个有序的数组。

第一次：使用两个指针，分别指向两个数组的头部，比较两个指针的值，将较小值放入到新数组中

第二次：较小值的指针右移，继续上述步骤

第三次：

第四次：

第五次：

第六次：

合并两个有序数组的代码如下

void merge(int *arr, int start, int middle, int end) {
    // 两个有序数组[start, middle-1], [middle, end-1]
    // i,j分别指向两个数组的头部
    int i = start, j = middle, k = 0;
    // temp为合并后的数组
    int *temp = new int[end - start];
    while (i < middle && j < end) {
        if (arr[i] < arr[j])
            temp[k++] = arr[i++];
        else
            temp[k++] = arr[j++];
    }
    // 如果j没有到最后。将j后面的元素添加后temp数组后面
    while(j < end)
        temp[k++] = arr[j++];
    // 如果i没有到最后，将i后面的元素添加到temp数组后面
    while(i < middle)
        temp[k++] = arr[i++];
    // temp数组元素复制给原数组
    for (int p = start; p < end; p++)
        arr[p] = temp[p - start];
    delete[] temp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

归并排序的代码如下

void merge_sort(int *arr, int start, int end) {
    int middle = (start + end) >> 1;
    if (middle <= start)
        return;
    // 对数组左侧递归调用归并排序
    merge_sort(arr, start, middle);
    // 对数组右侧递归调用归并排序
    merge_sort(arr, middle, end);
    // 合并左右两个有序数组
    merge(arr, start, middle, end);
}
1
2
3
4
5
6
7
8
9
10
11

可以证明归并排序的时间复杂度为O(NlgN)，空间复杂度为O(N)

6. 快速排序

基本思想：

在数组中选择一个元素作为基准，将大于该数的放在该数的右边，将小于该数的放在该数的左边，对数组进行划分，然后对左右两边继续调用快速排序

划分的步骤：在左右两端放置两个指针，执行以下三步：
1. 左边指针的元素如果小于基准，则右移，否则不动；
2. 右边指针的元素如果大于基准，则左移，否则不动；
3. 如果左边指针的元素大于基准，而右边指针的元素小于基准，则交换两个元素。

下面用例子来说明快速排序的过程：

原始数组：

第一轮：以9作为基准，对数组进行划分:

继续划分步骤，这时两个指针重合，表示划分结束，将基准插入到指针的位置完成第一轮划分

第二轮：对9的左边以8为基准，对9的右边以21为基准进行划分操作后

第三轮：只有21的右边无序，则对21的右边以42作为基准进行划分

可以看到，经过三轮后，数组变为有序。

快速排序所选基准不同，性能可能会有所差距，下面算法实现中使用数组的头部元素作为基准。

划分代码

int partition(int *arr, int start, int end) {
    // 待排序数组[start, end-1], temp为基准
    int lptr = start + 1, rptr = end - 1, temp = arr[start];
    while (true) {
        // 左边指针一直往右找，直到找到大于等于基准的元素
        while (arr[lptr] < temp && lptr < end)
            lptr++;
        // 右边指针一直往左找，直到找到小于等于基准的元素
        while (arr[rptr] > temp && rptr > start)
            rptr--;
        if (lptr >= rptr)
            break;
        // 交换左右元素
        else
            Swap(arr, lptr, rptr);
    }
    // 将基准与右指针的元素交换
    Swap(arr, rptr, start);
    return rptr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

快速排序代码

void quick_sort(int *arr, int start, int end) {
    if (start >= end)
        return;
    // 划分数组，并得到基准位置
    int pivot = partition(arr, start, end);
    // 递归调用，排序左边
    quick_sort(arr, start, pivot);
    // 递归调用，排序右边
    quick_sort(arr, pivot + 1, end);
}
1
2
3
4
5
6
7
8
9
10

快速排序的平均时间复杂度为O(NlgN)，最坏情况为O(N^2)，空间复杂度最少为O(lgN)，最多为O(N)。

7. 堆排序

基本思路：

通过建立最大堆或者最小堆，再从堆中依此删除堆顶元素后，得到的序列即是有序的

堆是一种特殊的完全二叉树结构，如果根节点元素大于所有子节点元素，称为最大堆；如果根节点元素小于所有子节点元素，称为最小堆。

关于堆的创建和删除元素，请参考这篇博客。

原始数组

最大堆建立过程

第四步：25比其根节点3大，所以25与根节点向上交换，直到25小于其根节点，停止向上交换

第五步：

第六步：

第七步：

第八步：

创建完最大堆后，依次删除堆顶元素，即可得到有序数组。

第一步：将堆顶元素与最后一个元素交换，交换过后，不满足最大堆的条件，需要作出调整，使得重新满足堆条件，将8向下比较，与子节点中最大的交换，直到两个子节点都要小于8，停止向下寻找。

第二步：此时堆顶元素33与最后一个元素3交换，蓝色表示已经删除的元素

第三步：堆顶元素25与最后一个元素17交换

第四步：堆顶元素21与最后一个元素12交换

第五步：堆顶元素17与最后一个元素3交换

第六步：堆顶元素12与最后一个元素8交换

第七步：堆顶元素9与最后一个元素3交换

第八步：将堆顶元素8与最后一个元素3交换

此时，从完全二叉树的从上到下，从左到右已经是一个有序的，假设用数组来存储堆数据结构，那么这个数组就是有序的。

下面代码使用数组存储堆

创建堆代码

void build_heap(int *arr, int len) {
    int current, parent;
    for (int i = 1; i < len; i++) {
        current = i;
        parent = (current - 1) >> 1;
        // 当前节点值大于父节点值，执行循环
        while (arr[parent] < arr[current]) {
            Swap(arr, parent, current);
            current = parent;
            // 到达堆顶，结束循环
            if (current <= 0)
                break;
            parent = (current - 1) >> 1;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

堆排序代码

void heap_sort(int *arr, int len) {
    int current, idx, last;
    int left, right;
    // 构建最大堆
    build_heap(arr, len);
    for (int i = 0; i < len - 1; i++) {
        current = 0;
        // 最后一个节点
        last = len - i - 1;
        Swap(arr, 0, last);
        while (current * 2 + 1 < last) {
            // 左子节点，右子节点
            left = current * 2 + 1;
            right = left + 1;
            idx = left
            // 左右子节点都存在，需要交换的节点为左右子节点中值最大的那个节点
            if (right < last)
                idx = arr[right] > arr[left] ? right : left;
            // 如果当前节点小于需要交换的节点，则交换
            if (arr[current] < arr[idx])
                Swap(arr, current, idx);
            else
                break;
            current = idx;
        }
    }
}
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

堆排序的时间复杂度为O(NlgN)，空间复杂度为O(1)。

8. 桶排序

基本思想：

将数据按照某种映射(一般为线性映射)放入到多个桶中，然后对每个桶内进行排序，最后桶连起来，完成排序

具体过程如下：
原始数组

构建5个桶，每个桶存储的数据范围分别是[0~9]，[10-19]，[20-29]，[30-39]，[40-49]，以元素/10作为桶编号，所以桶编号越大，元素值越大；再对桶内元素进行排序后，将所有非空的桶按顺序合并就是有序数组了

对桶内元素排序可以采用很多方法，比如说快速排序等，这里采用插入排序作为算法实现

使用链表数据结构插入一个元素

// 链表节点定义
struct Node {
    Node() {
        v = 0;
        next = NULL;
    }
    int v;
    Node *next;
};

Node* insert(Node *head, int v) {
    // node待插入节点
    Node *node = (Node *)malloc(sizeof(Node));
    node->v = v;
    // 头结点为空或者头结点的值大于待插入节点
    if (head == NULL || head->v > node->v) {
        node->next = head;
        head = node;
    }
    else {
        Node *parent = (Node *)malloc(sizeof(Node));
        Node *current = (Node *)malloc(sizeof(Node));
        parent = head;
        current = parent;
        // 找到插入位置
        while (current != NULL && current->v < node->v) {
            parent = current;
            current = current->next;
        }
        parent->next = node;
        node->next = current;
    }
    return head;
}
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

桶排序算法

void bucket_sort(int *arr, int len, int buckets) {
    Node **p;
    // 初始化桶
    p = (Node **)malloc(sizeof(Node *) * buckets);
    for (int i = 0; i < buckets; i++)
        p[i] = NULL;
    Node *current;
    // 更新桶内链表
    for (int i = 0; i < len; i++) {
        // 元素/10作为桶编号
        p[arr[i] / 10] = insert(p[arr[i] / 10], arr[i]);
    }
    // 将桶合并
    for (int i = 0， k = 0; i < buckets; i++) {
        current = p[i];
        while (current != NULL) {
            arr[k++] = current->v;
            current = current->next;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

桶排序依靠数据的分布，数据的分布不同，桶的数量和映射关系会有所不同。

设M为桶的数量，则桶排序的时间复杂度为O(N+C)，其中C=N*(logN-logM)，空间复杂度为O(N+M)；桶排序是一种以空间换取时间的算法，桶的数量M够多时，其时间复杂度可以达到线性级别O(N)。

八大算法至此讲解完毕。

八大排序算法比较

排序算法是否稳定，由以下规则决定:

假设有Ai = Aj，且原数组中i < j，即Ai在Aj前面，如果排完序后，i 依然小于 j，则称排序算法是稳定的，否则是不稳定的

源代码请查看
https://github.com/gamersover/cplusplus_learn/tree/master/cplusplus_learn/sort_Algorithm