如何以O(n)时间排序含最多√n个错位元素的几乎有序数组？

给定原本升序的数组，经过最多⌊√n/2⌋次交换后最多√n个元素错位，我们可以通过以下步骤实现O(n)时间排序：

完整算法实现 #

def LinearSort(A):
    n = len(A)
    misplaced_indices = set()

    # Step 1: 识别所有可能的错位元素索引（O(n) 时间）
    if n <= 1:
        return A
    for i in range(n):
        if i == 0:
            if A[i] > A[i+1]:
                misplaced_indices.add(i)
        elif i == n-1:
            if A[i] < A[i-1]:
                misplaced_indices.add(i)
        else:
            if A[i] < A[i-1] or A[i] > A[i+1]:
                misplaced_indices.add(i)
    
    # 将错位索引按升序排列（O(√n · log√n) 时间）
    misplaced_indices = sorted(misplaced_indices)

    # Step 2: 分离错位元素与正确元素
    misplaced_list = []
    remainder_list = []
    for i in range(n):
        if i in misplaced_indices:
            misplaced_list.append(A[i])
        else:
            remainder_list.append(A[i])
    
    # 排序错位元素（O(√n · log√n) 时间）
    misplaced_list.sort()

    # Step 3: 合并两个有序列表（O(n) 时间）
    result = []
    i = j = 0
    len_remain = len(remainder_list)
    len_mis = len(misplaced_list)
    while i < len_remain and j < len_mis:
        if remainder_list[i] <= misplaced_list[j]:
            result.append(remainder_list[i])
            i += 1
        else:
            result.append(misplaced_list[j])
            j += 1
    
    # 追加剩余元素
    result.extend(remainder_list[i:])
    result.extend(misplaced_list[j:])
    
    return result

关键步骤说明 #

1. 识别错位元素：
   遍历数组，标记所有破坏相邻升序关系的位置（首尾元素单独判断）。虽然可能误判少量正确元素，但由于错位元素最多√n个，标记出的候选集合大小仍为O(√n)，不影响时间复杂度。
2. 分离与排序：
   将候选位置的元素分离出来排序（仅O(√n)个元素，排序时间可忽略），剩余元素保持原升序状态。
3. 合并有序列表：
   合并两个升序列表的时间为O(n)，最终得到完整的升序数组。

时间复杂度分析 #

• 遍历识别错位元素：O(n)
• 排序错位索引与元素：O(√n log √n)（远小于O(n)，可忽略）
• 合并有序列表：O(n)
  总时间复杂度为O(n)，符合问题要求。

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