---
url: /notes/dev/20250519-1.md
---
\[\[toc]]

# 排序算法个人理解

## 1. 冒泡排序与选择排序

这里无需讲解, 代码如下:

```c
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx])
                min_idx = j;
        }

        int temp = arr[i];
        arr[i] = arr[min_idx];
        arr[min_idx] = temp;
    }
}

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换 arr[j] 和 arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
```

## 2. 插入排序

插入排序便是把前面作为`已排序部分`, 后面作为`未排序部分`, 每次从后面提取一个元素插入到`已排序部分`的正确位置.

遍历后, 整个数组就都是`已排序部分`了.

代码如下:

```c
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        
        // 将比key大的元素后移
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}
```

该排序在数据较少时十分迅速, 基本上是排序的首选方案.

## 3. 希尔排序

希尔排序是插入排序的升级版, 当数据量较大且基本无序时, 插入排序可能一次移动很多元素(如前面已经排好很多, 但我们读取到一个很小的元素, 我们就必须把前面所有的元素都后移).

希尔排序设计了一个`增量序列(gap)`, 作为移动到步长, 最初时`gap`较大, 元素将`大步移动`, 这样每次就不必再一个一个移动多个元素.

经过第一次排序后, 元素基本上已经拥有了顺序, 之后缩小`gap`, 再次移动, 这样元素顺序将更加精确.

重复上述步骤, 一直减小`gap`, 直到`gap = 1`时, 就成为了正常的希尔排序. 此时数据基本上已经排好, 一半只需要移动几个元素即可排序完成.

```c
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void shellSort(int arr[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2)
        for (int i = gap; i < n; i++)
            for (int j = i; j >= gap && arr[j] < arr[j - gap]; j -= gap)
                swap(&arr[j], &arr[j - gap]);
}
```

上述`gap`使用的是希尔原始提出的二分操作, `gap = N / 2, N / 4, ... , 1`, 简单但效率一般.

此外, 还有其他的增量序列, 如表所示:

| 序列名       | 序列                         | 特点                | 时间复杂度        |
|-----------|----------------------------|-------------------|--------------|
| Shell     | $N/2, N/4, \cdots, 1$      | 简单但效率一般           | $O(n^2)$     |
| Hibbard   | $1, 3, 7, \cdots, 2^k - 1$ | 相邻元素互质，减少重复比较     | $O(n^{3/2})$ |
| Sedgewick | $1, 5, 19, 41, \cdots$     | 混合了多种数学性质，实践中表现最优 | $O(n^{4/3})$ |
| Knuth     | $(3^k - 1) / 2$            | 基于数学分析得出的较优序列     | $O(n^{3/2})$ |

其中`Sedgewick`表现最优, 计算公式如下:

$$
gap = \begin{cases}
& 9 *(4^(i - 1) - 2* (2^(i - 1)) + 1 , & i \text{为奇数} \\
& 4^i - 3 \* 2^i + 1 , & i \text{为偶数}
\end{cases}
$$

## 4. 快速排序

快速排序的`原地排序`版本代码晦涩难懂, 这里先讲解`非原地排序`的代码.

```py
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr) // 2]
    left = [_ for _ in arr if _ < pivot]
    middle = [_ for _ in arr if _ == pivot]
    right = [_ for _ in arr if _ > pivot]
    
    return quick_sort(left) + middle + quick_sort(right)
```

该排序的这段代码很好理解, 首先找出一个`基准(这里是arr最中间的元素)`, 之后比`基准`小的添加到`left`数组中, 比`基准`大的添加到`right`数组中, 和`基准`相等的添加到`middle`数组中.

这样无论`left`和`right`顺序如何, `middle`的位置一定是正确的, 因为它前后就是这么多元素.

之后, 递归排序`left`和`right`, 直到子数组长度为`1`, 排序完成.

> 为什么要分成`left`, `middle`, `right`三个子数组, 而非`left`, `[pivot]`, `right`三个子数组或`left`, `mid_and_right`两个子数组呢?

> 因为最终我们是将三个数组合并, 而非原arr中提取. 如果单纯写成`left`, `[pivot]`, `right`合并, 这时要是存在多个和`基准值`相同的元素, 它们都会被丢失掉.
>  
> 此外, 如果分类时使用`left = [_ for _ in arr if _ < pivot]`, `mid_and_right = [_ for _ in arr if _ >= pivot]`, 这时如果出现相同元素, 那么`mid_and_right`数组会被相同元素占据, 无法细分, 导致死循环.

但是如果用c语言实现上述代码, 由于`left`, `middle`, `right`数组长度未知, 且合并数组很不方便, 还需要手动管理内存. 因此c语言有原地排序的方案.

```c
// 辅助函数swap, 交换两个变量的值
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 快速排序的分区函数
int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] <= pivot) {
            i ++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

// 快速排序主函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // pi 是分区索引, arr[pi]现在在正确的位置
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
```

上述函数使用了`partition`分区函数进行`分区`和`查找基准值`, 是`原地排序`的核心部分.

它的功能是将数组最右边值设为`基准值`, 之后对元素进行一次简单的分类, 最后返回`基准值位置`.

遍历数组, 当遍历到元素小于`基准值`时, 将该元素移动到数组前面, 并设置`基准值位置`为`移动到前面元素数 + 1`.

数组遍历完成后, 即可保证`基准值位置`前面的元素都小于`基准值`(同理此时`基准值位置`后面的元素也都大于等于`基准值`).

这时`partition`分区函数返回`基准值位置(pi)`, 然后递归排序`基准值位置`前面的元素(相当于`left`)和`基准值位置`后面的元素(相当于`right`和部分`middle`).

> `middle`哪去了?

> 上述写法类似于上面`Q&A`中`mid_and_right`的写法, 但是并不会导致死循环, 因为我们递归排序的是`基准值`两边都元素, 不包括`基准值`本身, 也就是即使存在相同元素, 因为每次排序都剔除了一个`基准值`, 下层递归长度会变小, 所以不会导致死循环.
>  
> 我们可以使用相同原理改写一下上面`Q&A`中的`mid_and_right`, 代码如下:

```py
def quick_sort(arr):
    if len(arr) < 1:
        return arr

    pivot = arr[len(arr) - 1]
    left = [_ for _ in arr[:-1] if _ < pivot]
    right = [_ for _ in arr[:-1] if _ >= pivot]

    return quick_sort(left) + [pivot] + quick_sort(right)
```

这里我们取数组最后一个元素为`基准值`(为了方便从`mid_and_right`中去除该元素), 之后我们在数组除去最后一个元素的范围内分出`left`和`right(mid_and_right)`, 最后合并`left`, `[pivot]`, `right`.

## 5. 归并排序

归并排序将数组分成两个子数组, 然后递归排序两个子数组, 最后将子数组合并成大数组返回.

由于递归排序后的子数组已经有序, 因此合并会很简单.

```py
def merge_sort(arr):
    if len(arr) <= 1:
        return arr;

    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    left = merge_sort(left)
    right = merge_sort(right)

    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    
    return result
```

该排序非常稳定, 最好, 最坏和平均情况下时间复杂度均为 $O(n \log n)$

## 6. 堆排序和桶排序

看不懂.

## 7. 混合排序

### 7.1 内省排序 Introsort

由`快速排序`, `堆排序`, `插入排序`组成, 数据量较少时, 直接使用插入排序; 数据量较大时, 先使用快速排序, 当递归次数过多, 切换到堆排序.

### 7.2 Timsort

由`归并排序`, `插入排序`组成.

太强了看不懂.

### 7.3 块排序 Blocksort

由`归并排序`, `插入排序`组成, 同时结合块操作. 当数据量较大时, 可先加载小块来排序, 之后归并各个块.