# Sorting

## 综述

### 问题

假设要将一个大小为 $$N$$ 的从小到大排序。

### 思路

#### 1. 每次将一个元素移动到最终位置

一些排序算法，如选择排序 (selection sort)，冒泡排序 (bubble sort) 以及堆排序 (heap sort)，每次将一个元素移动到最终位置，这样就能将大小为 $$N$$ 的问题转化成大小为 $$N-1$$ 的问题。

#### 2. 每次将每个元素放到更接近最终位置的地方

一些排序算法，如插入排序 (insertion sort)，快速排序 (quick sort)，计数排序 (counting sort) 以及基数排序 (radix sort)，每次将每个元素放到更接近最终位置的地方，使得整体序列的逆序数量逐渐变少，并最终达到排序目的。

#### 3. 分治

如归并排序 (merge sort)

### 复杂度和运行时

* 排序至少要遍历一遍待排序列，因此排序算法的复杂度为 $$O(n)$$ 
* 影响复杂度的因素包括：
  * 算法本身的流程复杂程度及启动开销：简单的算法虽然复杂度常为 $$O(n^2)$$ ，但它的其它开销（常数项）可能很小，因此面对长度较小（如 < 10）的序列常常有更快的性能。因此实际运用中，常常会通过判断序列大小来选择所使用的排序算法
  * 多余的空间，如变量及递归的栈空间
  * 缓存：算法运行过程中的大部分比较操作如果都是发生在相邻元素之间，就容易利用数据的空间分布特点，获得更高的缓存命中率以及数据预取
  * 各种类型的输入考量：乱序、已经排好序、倒着排好序、接近排好序等
* 基于比较的排序算法对待排序列没有任何假设，理想情况下，在任何输入面前都能够做到 $$\theta(nlogn)$$ 的算法复杂度，如堆排序、归并排序等。
* 如果我们可以对数据做一些额外的假设，就可能获得比 $$\theta(nlogn)$$ 更好的算法复杂度，如在计数排序中，我们假设数据分布在一定范围内。

## 排序算法集锦

### 冒泡排序（Bubble Sort）

#### 复杂度小结

| Case    | Time Complexity | Space Complexity |
| ------- | --------------- | ---------------- |
| Best    | $$O(n)$$        | $$O(1)$$         |
| Worst   | $$O(n^2)$$      | $$O(1)$$         |
| Average | $$O(n^2)$$      | $$O(1)$$         |

#### 思路

从左往右冒泡，每次比较左右两个元素，如果前者大于后者，则交换位置，一共循环 $$N-1$$ 次，第 i 次循环结束时，第 i 大的元素都会移动到正确的位置上。

{% code title="bubble.py" %}

```python
def bubble(A):
    L = len(A)
    for i in range(L-1):
        flag = True
        for j in range(L-i-1):
            if A[j] > A[j+1]:
                A[j], A[j+1] = A[j+1], A[j]
                flag = False
        if flag:
            break
```

{% endcode %}

### 选择排序（Selection Sort）

#### 复杂度小结

| Case | Time Complexity | Space Complexity |
| ---- | --------------- | ---------------- |
| All  | $$O(n^2)$$      | $$O(1)$$         |

#### 思路

选择排序是所有排序中最直观的排序，从左开始，每次从剩余元素中选择最大（小）的元素，放到剩余序列的最右（左）边。

{% code title="selection.py" %}

```python
def selection(A):
    L = len(A)
    for i in range(L-1):
        mi = 0
        for j in range(1, L-i):
            if A[j] > A[mi]:
                mi = j
        A[mi], A[L-i-1] = A[L-i-1], A[mi]
```

{% endcode %}

### 插入排序（Insertion Sort）

#### 复杂度小结

| Case    | Time Complexity | Space Complexity |
| ------- | --------------- | ---------------- |
| Best    | $$O(n)$$        | $$O(1)$$         |
| Worst   | $$O(n^2)$$      | $$O(1)$$         |
| Average | $$O(n^2)$$      | $$O(1)$$         |

#### 思路

插入排序与打扑克时整理牌的方法类似，从左向右开始，第 i 轮结束保证前 i 个元素已经排好序。

{% code title="insertion.py" %}

```python
def insertion(A):
    for i in range(1, len(A)):
        for j in range(i, 0, -1):
            if A[j] < A[j-1]:
                A[j], A[j-1] = A[j-1], A[j]
            else:
                break
```

{% endcode %}

### 快速排序（Quick Sort）

#### 复杂度小结

| Case    | Time Complexity | Space Complexity |
| ------- | --------------- | ---------------- |
| Best    | $$O(nlogn)$$    | $$O(1)$$         |
| Worst   | $$O(n^2)$$      | $$O(1)$$         |
| Average | $$O(nlogn)$$    | $$O(1)$$         |

#### 思路

有点像二分，每次选取一个 pivot，将所有小于 pivot 的数和所有大于 pivot 的数，分别作为两个子序列，递归地排序。其中 pivot 的选择决定了最终排序的复杂度。

```python
def quicksort(A):
    _quicksort(A, 0, len(A))

def _quicksort(A, l, h):
    if l < h:
        pi = _partition(A, l, h)
        _quicksort(A, l, pi)
        _quicksort(A, pi+1, h)

def _partition(A, l, h):
    # 任何 pivot 选择策略都可以，这里选择最后一个
    pi = h-1
    # 将 pivot 交换到最后
    A[pi], A[h-1] = A[h-1], A[pi]
    pi, p = h-1, p[h-1]
    
    i = l-1
    for j in range(l, h-1):
        if A[j] < p:
            i += 1
            A[i], A[j] = A[j], A[i]
    i += 1
    A[h-1], A[i] = A[i], A[h-1]
    return i
```

快速排序快的原因在于：

1. pivot 选择得好时，能够获得 $$\theta(nlogn)$$ 的时间复杂度
2. 它利用了 **spatial locality**，总是比较相邻的元素，因此很好地利用 cache

### 堆排序（Heap Sort）

#### 复杂度小结

| Case | Time Complexity | Space Complexity |
| ---- | --------------- | ---------------- |
| All  | $$O(nlogn)$$    | $$O(1)$$         |

使用堆（具体参考 Priority Queue Interface & Implementation 一节），先对原序列建堆（原地建堆可以获得 $$O(1)$$ 的空间复杂度），后每次从堆中 pop 出最大值，放到序列末尾即可。

### 归并排序（Merge Sort）

#### 复杂度小结

| Case | Time Complexity | Space Complexity |
| ---- | --------------- | ---------------- |
| All  | $$O(nlogn)$$    | $$O(n)$$         |

#### 思路

每次将序列二等分，各部分排好序后，再合并。

{% tabs %}
{% tab title="merge\_recursive.py" %}

```python
def mergesort(A):
    _mergesort(A, 0, len(A))

def _mergesort(A, l, h):
    # 区间内只有小于 2 个元素，直接返回，无需排序
    if l+1 >= h:
        return
    m = (l+h)//2
    _mergesort(A, l, m)
    _mergesort(A, m, h)
    _merge(A, l, m, h)

def _merge(A, l, m, h):
    tmp = []
    i, j = l, m
    while i < m and j < h:
        if A[i] < A[j]:
            tmp.append(A[i])
            i += 1
        elif A[i] > A[j]:
            tmp.append(A[j])
            j += 1
        else:
            tmp.append(A[i])
            tmp.append(A[j])
            i += 1
            j += 1
    while i < m:
        tmp.append(A[i])
        i += 1
    while j < h:
        tmp.append(A[j])
        j += 1
    A[l:h] = tmp
```

{% endtab %}

{% tab title="merge\_iterative.py" %}

```python
def mergesort(A):
    step = 1
    ll = len(A)
    while step <= ll:
        h = 0
        for h in range(0, ll, step*2):
            l, m, r = h, h+step, min(ll, h+2*step)
            p, q = l, m
            while p < m and q < r:
                if A[p] < A[q]:
                    p += 1
                else:
                    tmp = A[q]
                    A[p+1: q+1] = A[p:q]
                    A[p] = tmp
                    p, m, q = p+1, m+1, q+1
        step *= 2
    return A
```

{% endtab %}
{% endtabs %}

### 计数排序（Counting Sort）

#### 复杂度小结

| Case | Time Complexity | Space Complexity |
| ---- | --------------- | ---------------- |
| All  | $$O(n)$$        | $$O(k)$$         |

其中 n 表述序列大小，k 表示元素的范围大小

#### 思路

统计元素所处范围内中每个元素的数量，然后从小到大遍历生成新序列即可

{% code title="counting.py" %}

```python
def counting_sort(A, k, fn=lambda ele: ele):
    ll = len(A)
    
    counting_table = [0]*k
    for ele in A:
        counting_table[fn(ele)] += 1
    
    position_table = counting_table
    count = ll
    for i in reversed(range(len(position_table))):
        count -= position_table[i]
        position_table[i] = count
    ret = [0]*ll    
    for i, ele in enumerate(A):
        key = fn(ele)
        ret[position_table[key]] = ele
        position_table[key] = position_table[key] + 1
    return ret
```

{% endcode %}

### 基数排序（Radix Sort）

#### 复杂度小结

| Case | Time Complexity | Space Complexity |
| ---- | --------------- | ---------------- |
| All  | $$O(d\*(n+k))$$ | $$O(k)$$         |

其中，d 表示最大数的位数，k 表示元素基数大小（如二进制，k = 2；十进制，k = 10）

#### 思路

从最小的位数开始，如十进制中的个位，每轮对所有元素的该位数进行一次计数排序。

{% code title="radix\_sort.py" %}

```python
def radix_sort(A, d, k):
    def ele_to_key_gen(pos):
        def ele_to_key(ele):
            count = d - pos - 1
            while count > 0:
                ele = ele // k
                count -= 1
            return ele % k
        return ele_to_key
    
    for pos in reversed(range(d)):
        ele_to_key = ele_to_key_gen(pos)
        A = counting_sort(A, k, ele_to_key)
    return A
```

{% endcode %}

## 现实中的排序算法

### TimSort

#### 复杂度小结

| Case | Time Complexity | Space Complexity |
| ---- | --------------- | ---------------- |
| All  | $$O(nlogn)$$    | $$O(n)$$         |

#### 思路

当序列较小时，使用插入排序；当序列较大时，先将序列分成多组，每组先使用插入排序，后对不同组递归地使用归并排序中的归并步骤。

{% code title="timsort.py" %}

```python
def insertion_sort(A):
    for i in range(1, len(A)):
        for j in range(i, 0, -1):
            if A[j] < A[j-1]:
                A[j], A[j-1] = A[j-1], A[j]
            else:
                break
    return A

def merge(A, B):
    li, lj = len(A), len(B)

    R = []

    i, j = 0, 0
    while i < li and j < lj:
        if A[i] < B[j]:
            R.append(A[i])
            i += 1
        elif A[i] > B[j]:
            R.append(B[j])
            j += 1
        else:
            R.append(A[i])
            R.append(B[j])
            i += 1
            j += 1

    while i < li:
        R.append(A[i])
        i += 1
    while j < lj:
        R.append(B[j])
        j += 1
    return R


def timsort(A):
    ll = len(A)

    RUN = 32
    for i in range(0, ll, RUN):
        A[i:i+RUN] = insertion_sort(A[i:i+RUN])

    RUNinc = RUN
    while RUNinc < ll:
        for i in range(0, ll, 2*RUNinc):
            A[i:i+2*RUNinc] = merge(A[i:i+RUNinc],
                                    A[i+RUNinc:i+2*RUNinc])
        RUNinc *= 2
    return A
```

{% endcode %}

### 外排序算法

TODO

参考 <https://github.com/melvilgit/external-Merge-Sort>

## 参考

* [Sorting Algorithms Better Explained](https://betterexplained.com/articles/sorting-algorithms/)
* [Graphoarty: TimSort](https://github.com/graphoarty/scripts/blob/master/Sorting%20Algorithms/tim_sort.py)