基础排序算法总结：从逆序对的角度

从逆序对inversion的角度，重新审视基础排序算法，选择、插入、冒泡、希尔，他们到底什么关系？

首先证明：

在数组中交换一个逆序对，一定会使总的逆序对减小

Given an array of N keys, let a[i] and a[j] be an inversion (i < j but a[i] > a[j]). Prove or disprove: swapping a[i] and a[j] strictly decreases the number of inversions

处在i，j两侧的数不会因为这次交换产生逆序对的变动，只需要考虑nums[i+1:j]中的数，自然地，把这个区间的数根据nums[i], nums[j]分成三堆（忽略相等的情况，对逆序对没有影响），分别统计这三堆因为这次交换产生的逆序对变动就可以。

ZZgjoR.png

可以看到，交换一个inversion，至少减少一个inversion。当j-i=1，交换相邻的inversion，确定地减少一个inversion。交换不相邻的inversion，inversion的总数有可能减少得更快。

选择排序

思路：选择最小元素，放入有序数组的空位。

选择方法：n次比较+1次交换。

特点：过程中没有利用计算产生的新信息，即有序数组。

性能：固定的$N^2/2$次比较和$N$次交换

稳定：否

使用场景：交换操作非常昂贵，逆序对比较多

1
2
3
4
5
6
7
8
def selection(nums):
    N = len(nums)
    for i in range(N):
        m, v = i, nums[v]
        for j in range(i+1, N):
            if nums[j] < v:
                m = j
        nums[i], nums[m] = nums[m], nums[i]

插入排序

思路：将一个新元素，插入进一个有序数组，原数组中所有元素插入完毕，排序结束。

插入方法： 比较+交换 or 比较+移动 or 二分+移动

特点：过程中利用了计算产生的新信息，即有序数组

性能：见下列代码中的讨论。实际上移动本质也是交换，而且也是相邻inversion的交换，所以总的交换(移动)次数等于总的逆序对个数。

稳定：是

使用场景：小规模数组，流式输入数据，逆序对较少，比如：

  • 数组中每个元素离他的最终位置都不远
  • 一个有序的大数组接一个小数组
  • 数组中只有几个元素位置不正确
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
def insertion(nums):
    """
    交换的次数就是逆序对的个数，设为V
    如果内循环是break跳出的，那么比较次数=交换次数+1
    如果内循环是range跳出的，那么比较次数=交换次数。比如nums[j]比nums[:i]都小
    看最外层循环，最多有range(1, N)个break的机会
    所以比较的次数C有V <= C <= V + len(nums)-1
    """
    N = len(nums)
    for i in range(1, N):
        for j in range(i-1, -1, -1):  # 询问左侧每个位置，要不要交换
            if nums[j] > nums[j+1]:
                nums[j+1], nums[j] = nums[j], nums[j+1]
            else:
                break


def insertion_no_exchange(nums):
    """
    把交换操作变为移动，也就是把一个数字往后移动一格。数组访问的次数由4变为2
    数组比较次数没有变
    减少控制流比较的方式是使用flag, Algo4给出方案(练习)的是使用哨兵。
    """
    N = len(nums)
    for i in range(1, N):
        v = nums[i]
        use_break = False
        for j in range(i-1, -1, -1):  # 询问每个左侧每个位置，要不要移动
            if nums[j] > v:
                nums[j+1] = nums[j]
            else:
                use_break = True
                break
        if use_break:       # nums[j] <= v, nums[j+1] 是为 v 空出来的格子
            nums[j+1] = v
        else:               # 每个位置都要求交换, nums[0] 就是为 v 空出来的格子
            nums[0] = v


def insertion_binary(nums):
    """
    同样数组的移动次数等于逆序对个数
    比较次数由平均n/2减少到logn，所以O(n^2)的常数因子会变得更小一些
    整个过程还是由移动dominant
    """
    N = len(nums)
    for i in range(1, N):
        v = nums[i]
        lo, hi = 0, i-1
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] > v:
                hi = mid - 1
            else:
                lo = mid + 1

        for j in range(i-1, lo-1, -1):
            nums[j+1] = nums[j]
        nums[lo] = v

冒泡排序

思路：结构上同选择排序，选择最大元素，放入有序数组空位。

选择方法： 比较+交换

特点：过程中利用了计算产生的新信息，但没有利用有序数组，利用的剩下的、经过交换的部分有序数组

性能：在比较中使用了交换，所以最终总的交换(移动)次数等于总的逆序对个数。但是比较仍然和选择相同，$N^2/2$。不过可以通过加入一个flag，标记本轮没有发生交换后提早退出。

稳定：是

所以冒泡排序实际上处于一个很尴尬的位置。交换虽然没有多做，但是有很多无意义的比较，因为要从部分有序数组里面寻找逆序对，会比较很多已经有序的数对。尽管设置flag可以减少很多，但是在最后一轮中，如果逆序对出现在靠后的位置，前面还是做了一些多余的比较，依然达不到插入那样节省。

1
2
3
4
5
6
7
8
9
10
def bubble(nums):
    N = len(nums)
    for i in range(N-1, 0, -1):  # 总共填充N-1个位置，剩余一个自然有序
        changed = False
        for j in range(0, i):  # 从开始处冒泡
            if nums[j] > nums[j+1]:
                nums[j+1], nums[j] = nums[j], nums[j+1]
                changed = True
        if not changed:    # 逆序对为0，全部有序
            break

希尔排序

思路：利用插入排序，在更大跨度上做排序，最后使用跨度为1的插入排序保证全部有序。

基础方法：生成递增序列+插入排序

特点 & 性能：希尔排序就是插入排序的直接拓展，由inversion的证明可知，希尔排序通过大跨度扫描，交换inversion，可以更快地减少总的inversion，为接下来的小跨度扫瞄交换创造有利条件。和归并、快排的性能差距在常数级别

稳定：否

除了上述的原理，还有实现上有两个地方注意：

  1. 实现数组h-有序时，相当于需要对h个子数组进行排序。与其事先计算出每个子数组的index，不如扫描所有未排定的数，也就是从index=h的开始，根据它的index倒推回去，index=h表示它属于h%h=0号子数组，index=h+1的表示它属于1号子数组，依次类推，各自在自己的子数组里比较、插入
  2. 使用binary-search优化时，mid的计算涉及到等差数列的上下中位数的计算，因为还有其他题目涉及，我总结到这篇笔记里
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
def sort_h(nums, h=1):
    """
    利用插入排序，将nums变为h-有序的
    对于每个数，通过插入排序，和自己同组元素比较、移动
    每个数安排完，就可以了
    >>> a = [7, 6, 2, 4, 9, 8, 1]
    >>> a1, a2, a3 = a[:], a[:], a[:]
    >>> sort_h(a1, h=1)
    >>> sort_h(a2, h=2) # [1,x,2,x,7,x,9] + [x,4,x,6,x,8]
    >>> sort_h(a3, h=3) # [1,x,x,4,x,x,7] + [x,6,x,x,9,x,x] + [x,x,2,x,x,8,x]
    >>> a1
    [1, 2, 4, 6, 7, 8, 9]
    >>> a2
    [1, 4, 2, 6, 7, 8, 9]
    >>> a3
    [1, 6, 2, 4, 9, 8, 7]
    """
    N = len(nums)
    for i in range(h, N):  # [0:h]是各组数第一个，跳过它
        v = nums[i]
        use_break = False
        for j in range(i-h, -1, -h):  # 询问每个左侧每个同组的位置，要不要移动
            if nums[j] > v:
                nums[j+h] = nums[j]
            else:
                use_break = True
                break
        if use_break:       # nums[j] <= v, nums[j+h]是为 v空出来的格子
            nums[j+h] = v
        else:               # 每个位置都要求交换, 同组的第一个就是空出来的位置
            nums[i%h] = v


def sort_binary_h(nums, h=1):    
    N = len(nums)
    for i in range(h, N):
        v = nums[i]
        lo, hi = i%h, i-h
        while lo <= hi:
            mid = int((hi - lo) / h / 2)
            mid = lo + mid*h
            if nums[mid] > v:
                hi = mid - h
            else:
                lo = mid + h
        for j in range(i-h, lo-1, -h):
            nums[j+h] = nums[j]
        nums[lo] = v


def gen_seq(N):
    h = 1
    while h < N // 3:
        h = 3*h + 1
    while h >= 1:
        yield h
        h = h // 3


def shell(nums):
    for h in gen_seq(len(nums)):
        sort_h(nums, h)


def shell_binary(nums):
    for h in gen_seq(len(nums)):
        sort_binary_h(nums, h)

总结

插入排序还是本体，无论从思想上还是实现上，其他方法都可借鉴、对比

基础排序实现时，关注点不妨放在“位置上”，一个萝卜一个坑，思路会更清晰一点。