将冒泡排序更改为插入排序,对迭代进行少量更改
Changing Bubble Sort to Insertion Sort with Small change to Iteration
我相信以下伪代码对于冒泡排序算法是正确的:
L = [8, 6, 7, 1, 5, 9, 4, 3, 10, 2] // 10 items
FOR I = 1 TO 9
FOR J = 1 TO 10 - I
IF L[J] > L[J + 1] THEN
TEMP = L[J]
L[J] = L[J + 1]
L[J + 1] = TEMP
ENDIF
ENDFOR J
ENDFOR I
OUTPUT L
如果我改变了 I 和 J 的迭代模式,如下例所示,我是否已将算法转换为插入排序?我想是的,但我很惊讶它会如此简单,而且我看到的各种实现往往差异更大。
L = [8, 6, 7, 1, 5, 9, 4, 3, 10, 2] // 10 items
FOR I = 1 TO 9
FOR J = 9 TO I STEP -1
IF L[J] > L[J + 1] THEN
TEMP = L[J]
L[J] = L[J + 1]
L[J + 1] = TEMP
ENDIF
ENDFOR J
ENDFOR I
OUTPUT L
第二种算法是冒泡排序的另一个版本。它不是在每次传递时将最大值移向数组的末尾,而是将最小值移向数组的开头。在下图中,第一行是未排序的数组,随后的每一行是执行一次内循环后数组的状态。冒泡排序的两个值得注意的特征:
- 行左侧的项目处于最终位置。
- 右边的项目也重新排列,但不一定到它们的最终位置。例如,在第三行,2 被从数组的末尾移到了中间。那时算法找到了 1。所以它将 2 留在后面并开始移动 1。
下图显示了插入排序的操作。同样有两个值得注意的特征:
- 左边的数组已排序,但元素不在最终位置。
- 右边的项目完全没有动过。
插入排序的一般概念是算法(在概念上)将数组分为两部分:开头的已排序部分和结尾的未排序部分。在每次执行内部循环时,它都会获取未排序部分的第一个元素,并将其向左移动,直到它正确定位在数组的已排序部分中。
我相信以下伪代码对于冒泡排序算法是正确的:
L = [8, 6, 7, 1, 5, 9, 4, 3, 10, 2] // 10 items
FOR I = 1 TO 9
FOR J = 1 TO 10 - I
IF L[J] > L[J + 1] THEN
TEMP = L[J]
L[J] = L[J + 1]
L[J + 1] = TEMP
ENDIF
ENDFOR J
ENDFOR I
OUTPUT L
如果我改变了 I 和 J 的迭代模式,如下例所示,我是否已将算法转换为插入排序?我想是的,但我很惊讶它会如此简单,而且我看到的各种实现往往差异更大。
L = [8, 6, 7, 1, 5, 9, 4, 3, 10, 2] // 10 items
FOR I = 1 TO 9
FOR J = 9 TO I STEP -1
IF L[J] > L[J + 1] THEN
TEMP = L[J]
L[J] = L[J + 1]
L[J + 1] = TEMP
ENDIF
ENDFOR J
ENDFOR I
OUTPUT L
第二种算法是冒泡排序的另一个版本。它不是在每次传递时将最大值移向数组的末尾,而是将最小值移向数组的开头。在下图中,第一行是未排序的数组,随后的每一行是执行一次内循环后数组的状态。冒泡排序的两个值得注意的特征:
- 行左侧的项目处于最终位置。
- 右边的项目也重新排列,但不一定到它们的最终位置。例如,在第三行,2 被从数组的末尾移到了中间。那时算法找到了 1。所以它将 2 留在后面并开始移动 1。
下图显示了插入排序的操作。同样有两个值得注意的特征:
- 左边的数组已排序,但元素不在最终位置。
- 右边的项目完全没有动过。
插入排序的一般概念是算法(在概念上)将数组分为两部分:开头的已排序部分和结尾的未排序部分。在每次执行内部循环时,它都会获取未排序部分的第一个元素,并将其向左移动,直到它正确定位在数组的已排序部分中。