查询满足紧凑内存上界且最坏时间复杂度低于O(n²)的排序算法

问题解答 #

存在完全满足这三个特性的排序算法，最典型的代表是堆排序、原地归并排序，经过尾递归优化的原地快速排序也符合要求：

• 堆排序：
  • 支持任意包含N个元素的数组排序，无特殊前置条件
  • 额外空间复杂度为O(1)，仅需要常数级临时变量用于元素交换，完全满足M远小于N的要求
  • 最坏情况时间复杂度稳定为O(nlogn)，远小于O(n²)
• 原地归并排序：
  • 适配普通数组排序场景，不需要开辟和原数组等长的辅助空间
  • 递归实现的版本额外空间复杂度为O(logn)（仅递归栈占用空间），非递归实现可以做到O(1)额外空间
  • 最坏情况时间复杂度稳定为O(nlogn)，符合小于O(n²)的要求

注意：常规非原地归并排序需要O(n)额外空间不符合要求，但原地改造后的版本可以完全匹配所有限制条件。

你可以参考如下堆排序的核心实现验证特性，整个过程没有开辟和N相关的额外存储空间：

// 堆排序C语言核心实现
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;
    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
    for (int i = n - 1; i >= 0; i--) {
        swap(&arr[0], &arr[i]);
        heapify(arr, i, 0);
    }
}

内容的提问来源于stack exchange，提问作者Vladimir Ignatev