第 3 遍结束时的排序算法输出

Question

给定以下最初未排序的列表：

[77, 101, 40, 43, 81, 129, 85, 144]

哪种排序算法在第 3 遍末尾生成以下列表？是气泡、插入还是选择？

[40, 43, 77, 81, 85, 101, 129, 144]

谁能告诉我如何解决这个问题。

Answer 1

插入排序会在 3 遍中更改最多 3 个项目的相对顺序，导致前 3 个项目按顺序排列，其余项目不变。选择排序只会影响前 3 个项目和 3 个最小（或最大）项目的位置。只有冒泡排序会交换其他项目。 40 和 129 的移动是指向冒泡排序的明显标志。

请注意，这可能是一个棘手的问题，因为所有需要移动的数字最多相差 2 个位置，除了其中 2 个（101 和 129，它们是第二大和第三大的，将结束2 次传球后回到正确的位置）。正确实施的冒泡排序不会进入第三遍。所以答案可能是“none of them”

Answer 2

插入排序：

def insertion_sort(array):
    for i in range(1, len(array)):
        key_item = array[i]
        j = i - 1
        while j >= 0 and array[j] > key_item:
            array[j + 1] = array[j]
            j -= 1
        array[j + 1] = key_item
        print("Step",i,":",array)
    return array

data=[77, 101, 40, 43, 81, 129, 85, 144]
insertion_sort(data)

输出：

Step 1 : [77, 101, 40, 43, 81, 129, 85, 144]
Step 2 : [40, 77, 101, 43, 81, 129, 85, 144]
Step 3 : [40, 43, 77, 101, 81, 129, 85, 144]
Step 4 : [40, 43, 77, 81, 101, 129, 85, 144]
Step 5 : [40, 43, 77, 81, 101, 129, 85, 144]
Step 6 : [40, 43, 77, 81, 85, 101, 129, 144]
Step 7 : [40, 43, 77, 81, 85, 101, 129, 144]

冒泡排序：

def bubble_sort(array):
    n = len(array)
    for i in range(n):
        already_sorted = True
        for j in range(n - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]
                already_sorted = False
        if already_sorted:
            break
        print("Step:",n-j-1)
        print(array)
    return array

data = [77, 101, 40, 43, 81, 129, 85, 144]
bubble_sort(data)

输出：

Step: 1
[77, 40, 43, 81, 101, 85, 129, 144]
Step: 2
[40, 43, 77, 81, 85, 101, 129, 144]

选择排序：

def selectionSort(array, size):
    for step in range(size):
        min_idx = step

        for i in range(step + 1, size):
            if array[i] < array[min_idx]:
                min_idx = i
        (array[step], array[min_idx]) = (array[min_idx], array[step])
        print("step",step+1,":",end="")

        print(array)

data = [77, 101, 40, 43, 81, 129, 85, 144]
size = len(data)
selectionSort(data, size)

输出：

step 1 :[40, 101, 77, 43, 81, 129, 85, 144]
step 2 :[40, 43, 77, 101, 81, 129, 85, 144]
step 3 :[40, 43, 77, 101, 81, 129, 85, 144]
step 4 :[40, 43, 77, 81, 101, 129, 85, 144]
step 5 :[40, 43, 77, 81, 85, 129, 101, 144]
step 6 :[40, 43, 77, 81, 85, 101, 129, 144]
step 7 :[40, 43, 77, 81, 85, 101, 129, 144]
step 8 :[40, 43, 77, 81, 85, 101, 129, 144]

您还可以从下面的 link 如何运行算法中获得更多指南： https://realpython.com/sorting-algorithms-python/

第 3 遍结束时的排序算法输出

Sorting Algorithm output at end of pass 3

python

sorting

bubble-sort

insertion-sort