十大经典排序算法
Cleo Lv2
 2021-04-20 23:32:20    

1. 冒泡排序

思路

冒泡排序是一种比较排序，且会交换元素位置。以从小到大排序为例，每轮排序过程会比较相邻两数大小，如果大数在前，则交换相邻两束位置，因此每轮将得到剩余元素中的最大值。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void bubble_sort(int arr[], int len)
{
    bool did_swap;
    int temp;
    for (int i = 0; i < len - 1; ++i)
    {
        did_swap = false;
        for (int j = 0; j < len - i - 1; ++j)
        {
            if (arr[j] > arr[j + 1])
            {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                did_swap = true;
            }
        }
        if (did_swap == false)
            break;
    }
}

复杂度分析

最好情况下，数组已经排好序，仍需进行1轮的比较，时间复杂度为$O\left(n\right)$。最坏情况下，数组为倒序，总共需要$n^2$次比较，因此最坏时间复杂度为$O\left(n^2\right)$；平均时间复杂度为$O\left(n^2\right)$。

由于使用原数组进行元素交换排序，借用一个临时变量，因此时间复杂度为$O\left(1\right)$。

稳定性

使用交换元素进行排序，如果数相同，不会进行交换位置，因此冒泡排序为稳定排序。

2.选择排序

思路

选择排序是一种简单直观的排序算法，它的工作原理是首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void selection_sort(int arr[], int len)
{
    int min_index, temp;
    for (int i = 0; i < len - 1; ++i)
    {
        min_index = i;
        for (int j = i + 1; j < len; ++j)
        {
            if (arr[min_index] > arr[j])
                min_index = j;
        }
        temp = arr[i];
        arr[i] = arr[min_index];
        arr[min_index] = temp;
    }
}

复杂度分析

无论什么数据进去，都会进行进行$\frac{n\left(n-1\right)}{2}$次比较，因此时间复杂度无论最好最坏还是平均，都是$O\left(n^2\right)$。

由于只是借用临时变量来存储最小值索引和交换时所用的临时变量，因此空间复杂度为$O\left(1\right)$。

稳定性

选择排序是不稳定排序，例如5、8、5、2、9这个序列，第一次将第一个5和2交换，第一个5到了第二个5的后面。

3.插入排序

思路

插入排序的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增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
void insert_sort(int arr[], int len)
{
    int temp;
    for (int i = 1; i < len; ++i)
    {
        temp = arr[i]; // 注意下标
        for (int j = i; j > 0 && arr[j - 1] > temp; --j)
        {
            arr[j] = arr[j - 1];
        }
        arr[j] = temp;
    }
}

void insert_sort(int arr[], int len)
{
    int temp, pre;
    for (int i = 1; i < len; ++i)
    {
        temp = arr[i];
        pre = i - 1; // 注意下标
        while (pre >= 0 && arr[pre] > temp)
        {
            arr[pre + 1] = arr[pre];
            --pre;
        }
        arr[pre + 1] = temp;
    }
}

复杂度分析

最坏情况下数组逆序，需要比较$\frac{n\left(n - 1\right)}{2}$次，时间复杂度为$O\left(n^2\right)$。最好情况下，数组有序，只需要跟前一个元素比较一次，共$n-1$次，时间复杂度为$O\left(n\right)$。平均时间复杂度为$O\left(n^2\right)$。

空间复杂度为$O\left(1\right)$。

稳定性

由于比较用的是arr[pre] > temp，因此不会向左查询位置时，不会越过与自身相同的值，为稳定排序。

4. 希尔排序

思路

希尔排序可以说是对插入排序的一种改进，通过设置增量将序列分组进行插入排序。随着增量逐渐减少，每组包含的数越来越多，当增量减为1时，整个序列恰好被分成一组，算法便终止。增量为几，序列就被分成几组。下面来看一个具体的排序案例：

假设序列长度为len，我们设置增量gap的初值为len / 2，并以gap /= 2的方式减少增量形成一个增量序列：$\left(\frac{1}{2}len，\frac{1}{4}len，…，1\right)$。这里的除法为整除，舍弃余数部分。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。下面是整个过程：

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void shell_sort(int arr[], int len)
{
    for (int gap = len / 2; gap > 0; gap /= 2)
    {
        /* 分组插入排序 */
        for (int i = gap; i < len; ++i)
        {
            int temp = arr[i];
            int j = i;
            while (j - gap >= 0 && arr[j - gap] > arr[j])
            {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
}

上述代码实现时，内部for循环i的初值设置为gap，是因为下标为gap的元素即第一组的第二个元素，插入排序一般从第二个元素开始。

复杂度分析

希尔排序最好情况下时间复杂度为$O\left(n\right)$，最坏情况下时间复杂度为$O\left(n^2\right)$。平均时间复杂度为$O\left(n^{1.3}\right)$。这里说的应该不一定指的是使用上述的增量序列的时间复杂度。

由于只是借助几个临时变量，且是在原数组上进行操作的，并未有额外的内存开销，因此空间复杂度为$O\left(1\right)$。

稳定性

由于通过增量进行分组并分别在组内排序，希尔排序为不稳定排序。

5. 归并排序

思路

归并排序采用分治法，将序列分成两份，对两个子序列分别排完序后进行归并。而子序列的排序采用同样的策略，直到子序列的长度为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
void merge(int arr[], int bak[], int start, int end)
{
    if (start >= end)
        return;
    
    int mid = (end - start) >> 1 + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    
    merge(arr, bak, start, mid);
    merge(arr, bak, mid + 1, end);
    
    /* 归并 */
    int k = start;
    while (start1 <= end1 && start <= end2)
        bak[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        bak[k++] = arr[start1++];
    while (start2 <= end2)
        bak[k++] = arr[start2++];
    
    for (int i = start; i <= end; ++i)
        arr[i] = bak[i];
}

void merge_sort(int arr[], int len)
{
    int *backup = new int[len];
    merge(arr, backup, 0, len - 1);
    delete[] backup;
}

复杂度分析

归并排序的时间复杂度无论是最好还是最坏情况下都是$O\left(nlogn\right)$。

由于需要借助额外的空间来存储中间过程，空间复杂度为$O\left(n\right)$。

稳定性

归并排序是稳定的。

未完待续….