排序算法

Twisuki2025/5/19约 2093 字大约 7 分钟

排序算法个人理解

1. 冒泡排序与选择排序

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

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. 插入排序

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

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

代码如下:

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时, 就成为了正常的希尔排序. 此时数据基本上已经排好, 一半只需要移动几个元素即可排序完成.

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

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

g a p = {9 * (4^{(} i - 1) - 2 * (2^{(} i - 1)) + 1, 4^{i} - 3 * 2^{i} + 1, i 为奇数 i 为偶数

4. 快速排序

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

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语言有原地排序的方案.

// 辅助函数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, 代码如下:

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. 归并排序

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

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

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 lo g n)$

6. 堆排序和桶排序

看不懂.

7. 混合排序

7.1 内省排序 Introsort

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

7.2 Timsort

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

太强了看不懂.

7.3 块排序 Blocksort

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