arrays - 比较排序是否必须比较所有相邻的单元格？

Question

比较排序是不是要比较A[i]的最大值和A[i+1]的最大值？我认为任何比较排序都必须，但我不确定。我已经检查了合并排序、插入排序和快速排序，并且在它们中的每一个中都必须比较 A[i] 最大值和 A[i+1] 最大值。

Answer 1

每个正确的算法都必须比较相邻的单元格，除非它们相等。证明:否则假设。最终数组中的 A[i] 和 A[i+1] 尚未进行比较 (A[i] < A[i+1)。如果它们在原始数组中的位置交换了会发生什么？该算法所做的所有比较都给出与原始运行 (*) 相同的结果，因此它执行相同的排列，因此它们的最终位置被交换，因此它使算法不正确。

(*) 这是因为 A[i] 和 A[j] 是相邻的。