算法之排序

Echo in Baoji

2020-07-09

# 1 排序

插入排序、冒泡排序、归并排序、快速排序的特点及分析。

# 1.1 插入排序

插入排序的思想是通过构建有序序列，对未排序的序列，在已排序的序列中从后往前扫描，找到对应的位置并插入。

其实就像打扑克牌时理牌的过程，代码如下。

// ascending
void InsertionSort(int* data, int length)
{
    int temp, j;
    for(int i = 1; i < length; ++ i)
    {
        temp = data[i];
        j = i - 1;
        while(j >= 0 && data[j] > temp)
        {
            data[j + 1] = data[j];
            -- j;
        }
        data[j + 1] = temp;
    }
}

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

在最坏的情况下，当数组逆序时，总的比较次数为 1 + 2 + ... + (n - 1)，时间复杂度为 O(n^2)。

在最好的情况下，当数组有序时，只需要当前数和前一个数比较一次即可，一共比较 n - 1 次，时间复杂度为 O(n)。

平均来说，data[1...j - 1] 中的元素，一半小于 A[j]，一半大于 A[j]，而总的比较次数依旧是输入数组规模的二次函数，因此平均时间复杂度为 O(n^2)。

排序前后，两个顺序相同的数的相对顺序不会发生改变，即插入排序是稳定的。

# 1.2 冒泡排序

冒泡排序的基本思想是重复走访需要排序的数组，每次比较两个相邻元素，将他们的顺序调整正确，由于每次都会将一个未排序序列中的最大元素冒泡到序列尾部而得名。

代码如下

// ascending
void BubbleSort(int* data, int length)
{
    for(int i = 0; i < length; ++ i)
    {
        for(int j = 0; j < length - i - 1; ++ j)
        {
            if(data[j] > data[j + 1])
            {
                int temp = data[j];
                data[j] = data[j + 1];
                data[j + 1] = temp;
            }
        }
    }
}

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

可以看到，不论序列如何，需要比较的次数都是 n * (n - 1) / 2，时间复杂度为 O(n^2)。

不过当数组顺序时，不需要交换，而数组逆序时，需要交换 n * (n - 1) / 2 次，平均来说，交换的时间复杂度也为 O(n^2)。

# 1.3 归并排序

归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略（分治法将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

归并排序在分的时候通常采用二分，治的阶段采用辅助的临时数组，将数组按序合并。

代码如下：

// ascending
void MergeSort(int* data, int left, int right)
{
    if(left < right)
    {
        int mid = left + (right - left) / 2;
        MergeSort(data, left, mid);
        MergeSort(data, mid + 1, right);
        Merge(data, left, mid, right);
    }
}

void Merge(int* data, int left, int mid, int right)
{
    int index1 = left, index2 = mid + 1, k = 0;
    int tmp[right - left + 1];
    while(index1 <= mid && index2 <= right)
        tmp[k ++] = data[index1] < data[index2] ? 
                data[index1 ++]: data[index2 ++];

    while(index1 <= mid)
        tmp[k ++] = data[index1 ++];
    while(index2 <= right)
        tmp[k ++] = data[index2 ++];
    
    for(int i = 0; i < k; ++ i)
        data[left ++] = tmp[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

归并排序无论最好最坏还是平均，时间复杂度都是 O(nlogn)。

# 1.4 快速排序

快速排序使用分治法把一个数组分为两个子数组来递归处理，同时保证这两个子数组的其中一个数组的所有元素均大于基准元素，另一个均小于基准元素。

其与归并排序的分类似，而治有别。代码如下：

void QuickSort(int* data, int left, int right)
{
    if(left < right)
    {
        int partitionIndex = Partition(data, left, right);
        QuickSort(data, left, partitionIndex - 1);
        QuickSort(data, partitionIndex + 1, right);
    }
}

int Partition(int* data, int left, int right)
{
    int pivot = left;
    while(left < right)
    {
        while(right > left && !(data[right] < data[pivot]))
            -- right;
        while(right > left && !(data[left] > data[pivot]))
            ++ left;
        
        if(left < right)
            swap(data, left, right);
    }
    assert(left == right);
    swap(data, pivot, left);
    return left;
}

void swap(int* arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

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

快速排序的最坏运行情况是 O(n^2)，比如说顺序数列的快排。

但它的平均期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

# 1.5 排序算法对比

算法	最好时间复杂度	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性
插入排序	`O(n)`	`O(n^2)`	`O(n^2)`	`O(1)`	稳定
冒泡排序	`O(n^2)`	`O(n^2)`	`O(n^2)`	`O(1)`	比较操作包含等号则不稳定，否则稳定
归并排序	`O(nlogn)`	`O(nlogn)`	`O(nlogn)`	`O(n)`	稳定
快速排序	`O(nlogn)`	`O(nlogn)`	`O(n^2)`	`O(1)`	不稳定