vlambda博客
学习文章列表

简单选择排序

基本思想：

• 从未排序部分反复寻找最小元素(考虑升序)，并将其放在数组的开头。该算法在给定数组中维护两个子数组。
• 1)已经排序的子数组。
• 2)剩余未排序的子数组。
• 在选择排序的每次迭代中，从未排序的子数组中选取最小元素(考虑升序)并移动到已排序的子数组中。

简单理解：

• 找到全元素的最小值，将其与第一个元素交换；找到剩余元素的最小值，与第二个元素交换....,循环n次

def selectSort(lst):
    n = len(lst)
    print(lst)
    # Traverse through all array elements
    for i in range(n):
        # Find the minimum element in remaining
        # unsorted array
        min_idx = i
        for j in range(i + 1, n):
            if lst[min_idx] > lst[j]:
                min_idx = j  # 比较一遍，记录索引不交换
        # Swap the found minimum element with
        # the first element
        lst[i], lst[min_idx] = lst[min_idx], lst[i]  # 按索引交换
        print(lst)
    return lst


lst = input('输入数字：').split(' ')
lst = [eval(x) for x in lst]
selectSort(lst)


# -------------------------------------------------------------
def selectSort(lst):
    for i in range(len(lst)):
        min_value = min(lst[i:])
        min_idx = lst.index(min_value)
        lst[min_idx], lst[i] = lst[i], lst[min_idx]
    return lst


# -------------------------------------------------------------
def selectSort(lst):
    lst_sort = []
    while len(lst) > 0:
        min_value = min(lst)
        lst_sort.append(min_value)
        lst.remove(min_value)
    return lst_sort

堆排序

• 堆排序是一种基于二进制堆数据结构的基于比较的排序技术。
• 它类似于选择排序，我们首先找到最大的元素，然后把最大的元素放在最后。
• 我们对剩下的元素重复同样的过程。

def heapSort(lst):
    def heapify(lst, n, i):
        """to heapify subtree rooted at index i;
        n is the size of heap"""
        largest = i  # initialize largest as root
        left = 2 * i + 1  # left = 2*i + 1
        right = 2 * i + 2  # right = 2*i + 2

        # See if left child of root exists and is
        # greater than root
        if left < n and lst[largest] < lst[left]:
            largest = left

        # See if right child of root exists and is
        # greater than root
        if right < n and lst[largest] < lst[right]:
            largest = right

        # Change root, if needed
        if largest != i:
            lst[i], lst[largest] = lst[largest], lst[i]  # 子节点上移

            # Heapify the root.
            heapify(lst, n, largest)  # 继续向下比较

    def sort(lst):
        # The main function to sort an array of given size
        n = len(lst)

        # Build a maxheap.
        # Since last parent will be at ((n//2)-1) we can start at that location.
        # 非叶子节点的数量(n//2)，从0开始计数，则有n//2-1个
        for i in range(n // 2 - 1, -1, -1):  # 从最后一个非叶子结点开始
            heapify(lst, n, i)

        # One by one extract elements
        for length in range(n - 1, 0, -1):
            lst[i], lst[0] = lst[0], lst[i]  # swap 将大顶堆堆顶数放到最后
            heapify(lst, length, 0)  # 调整剩余数组成的堆，这里i表示元素个数，0表示

    sort(lst)
    return lst


lst = input('输入数字：').split(' ')
lst = [eval(x) for x in lst]
heapSort(lst)