使用插入排序计算比较

Question

我的任务是在对数组进行排序时计算总比较数。给定整数数组 {8, 2, 1, 4, 3, 5}，我从左边第二个元素开始，将它与第一个元素进行比较，切换它们，然后将第三个元素与前两个元素进行比较，依此类推on，以确定每个元素的位置。

我总共计算了 15 次比较，但正确的比较次数是 10 次。我知道按选择排序对这个数组进行排序是 15 次比较，那么在这个例子中使用插入排序时比较计数有何不同？

Answer 1

你对插入排序工作原理的理解是错误的。

将此伪代码用于插入排序：

mark first element as sorted
for each unsorted element
  'extract' the element
  for i = lastSortedIndex to 0
    if currentSortedElement > extractedElement
      move sorted element to the right by 1
    else: insert extracted element

初始数组：[8, 2, 1, 4, 3, 5]

比较 1：2 < 8 数组：[2, 8, 1, 4, 3, 5]

比较 2：1 < 8 数组：[2, 1, 8, 4, 3, 5]

比较3：1 < 2数组：[1, 2, 8, 4, 3, 5]

比较 4：4 < 8 数组：[1, 2, 4, 8, 3, 5]

比较5：4 > 2数组：[1, 2, 4, 8, 3, 5]

比较 6：3 < 8 数组：[1, 2, 4, 3, 8, 5]

比较 7：3 < 4 数组：[1, 2, 3, 4, 8, 5]

比较 8：3 > 2 数组：[1, 2, 3, 4, 8, 5]

比较 9：5 < 8 数组：[1, 2, 3, 4, 5, 8]

比较 10：5 > 4 数组：[1, 2, 3, 4, 5, 8]

已排序！

使用插入排序计算比较

Counting Comparisons Using Insertion Sort

java

sorting

selection

insertion