你好，我尝试解决下面这个问题已经 5 个小时了，但还是没找到答案。这个问题的标题是“线性排序”，所以我假设最优答案的时间复杂度应该是 O(n)。问题如下。
=======================================================
假设你有一个包含 n 个整数的数组，最初按升序排列。但是，数组中元素对之间最多进行了⌊√n/2⌋次任意交换。因此，最多有 √n 个元素可能偏离了正确的位置。你必须使用时间复杂度尽可能低的算法将此数组重新排序为升序。
=======================================================
目前我发现，如果能在 O(n) 的时间复杂度内找出哪些元素位置不对，那么排序本身也应该花费 O(n)。不过我现在也不知道该怎么办了 :(
算法线性排序(A):
n ← length(A)
misplacedIndices ← empty set
// Step 1: Identify indices of potentially misplaced elements
misplacedIndices.add(i) // Do this somehow(!!!!)
// sort indices in ascending order -> takes O(√n · log(√n))
misplacedIndices ← sorted(misplacedIndices)
// Step 2: Separate misplaced elements from correctly placed ones
misplacedList ← empty list
remainderList ← empty list
for i ← 0 to n - 1 do:
if i ∈ misplacedIndices then:
misplacedList.append(A[i])
else:
remainderList.append(A[i])
end for
// Sort the misplaced elements (only up to O(√n) elements)
sort(misplacedList) // Time complexity: O(√n · log√n)
// Step 3: Merge the two sorted lists (remainderList and misplacedList)
result ← empty list
i ← 0, j ← 0
while i < length(remainderList) and j < length(misplacedList) do:
if remainderList[i] ≤ misplacedList[j] then:
result.append(remainderList[i])
i ← i + 1
else:
result.append(misplacedList[j])
j ← j + 1
end while
// Append any remaining elements from either list
while i < length(remainderList) do:
result.append(remainderList[i])
i ← i + 1
end while
while j < length(misplacedList) do:
result.append(misplacedList[j])
j ← j + 1
end while
return result