python实现简单选择排序以及堆排序

# coding: utf-8

"""
@File    : select_sort.py
@Time    : 2022/5/10 18:21
@Author  : liuwangwang
@Software: PyCharm
"""


class Sort:
    def __init__(self):
        pass

    def select_sort(self, arr):
        """

        选择排序，假设前面的i-1个元素已经有序，处理第i个元素：与后面的元素比较，记录最小元素的位置，与位置i元素交换
        共进行n-1趟
        原地排序，不需要额外的空间
        可以优化的点在于：for循环语句中，两两比较的结果，有些可以复用 ====
        :param arr:
        :return:
        """
        num = len(arr)
        for i in range(num - 1):
            index = i
            for j in range(i + 1, num):
                if arr[j] < arr[index]:
                    # 循环结束之后，记录的最小元素位置
                    index = j
            # 元素交换
            tmp_arr = arr[i]
            arr[i] = arr[index]
            arr[index] = tmp_arr
        return arr

    def shiftup(self, arr, index):
        """
        插入新的元素，向上调整，保持堆的特性
        :param arr:
        :return:
        """
        # 当前节点是index
        # 父节点是（index - 1）//2  索引从0开始
        while index > 0:
            parent_id = (index - 1) // 2
            if arr[parent_id] > arr[index]:
                arr[parent_id], arr[index] = arr[index], arr[parent_id]
                index = parent_id
            else:
                break

    # def shiftdown_ori(self, arr, index):
    #     """
    #     从根节点开始，向下调整，保持堆的特性
    #     （堆排序中，删除根节点，将最后一个未排序的元素放到根节点，然后向下调整，保持堆的特性）
    #     :param arr:
    #     :param index:
    #     :return:
    #     """
    #     # 用递归函数，还是用while循环
    # 
    #     num = len(arr)
    #     left = 2 * index + 1
    #     right = 2 * index + 2
    #     while 0 < left < num and 0 < right < num:
    # 
    #         # 父节点的左孩子是2*index + 1，右孩子是2*index + 2 （假如索引从0开始）
    #         if arr[index] < arr[left] and arr[index] < arr[right]:
    #             break
    #         if arr[left] <= arr[right]:
    #             idx = left
    #         else:
    #             idx = right
    # 
    #         tmp = arr[idx]
    #         arr[idx] = arr[index]
    #         arr[index] = tmp
    #         index = idx
    #         left = 2 * index + 1
    #         right = 2 * index + 2

    def shiftdown(self, arr, num, index):
        """
         向下调整，保持堆的特性
        :param arr:
        :param num:
        :param index:
        :return:
        """

        # 用递归函数，还是用while循环
        left = 2 * index + 1
        right = 2 * index + 2
        while 0 < left < num or 0 < right < num:

            # 父节点的左孩子是2*index + 1，右孩子是2*index + 2 （假如索引从0开始）
            # if arr[index] < arr[left] and arr[index] < arr[right]:
            #     break
            lowest = index

            if 0 < left < num and arr[left] < arr[lowest]:
                lowest = left

            if 0 < right < num and arr[right] < arr[lowest]:
                lowest = right

            if lowest != index:
                arr[lowest], arr[index] = arr[index], arr[lowest]  # 交换
                index = lowest
                left = 2 * index + 1
                right = 2 * index + 2
            else:
                break

    def heapify(self, arr, n, i):
        largest = i
        l = 2 * i + 1  # left = 2*i + 1
        r = 2 * i + 2  # right = 2*i + 2

        if l < n and arr[i] < arr[l]:
            largest = l

        if r < n and arr[largest] < arr[r]:
            largest = r

        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]  # 交换

            self.heapify(arr, n, largest)

    def heap_sort(self, arr):
        num = len(arr)
        # 1.逐步插入元素，调整，建堆
        for i in range(1, num):
            # 每插入一个元素保持堆的特性
            self.shiftup(arr, i)

        # for i in range(num - 1, -1, -1):
        #     # 每插入一个元素保持堆的特性
        #     self.shiftdown(arr, num, i)
        # 构建堆时，可以是向上调整也可以是向下调整
        # 当构建的堆和列表元素不一样的时候，更适合用向上调整（向上调整也更好理解）

        print(arr)

        # 2.拿出根节点元素，保持堆的的特性
        for i in range(num):
            arr[0], arr[num - i - 1] = arr[num - i - 1], arr[0]
            # # 已排序好的部分不做处理
            # new_arr = arr[:num - i - 1]
            self.shiftdown(arr, num - i - 1, 0)
            print(arr)

        return arr


obj = Sort()
arr = [49, 38, 65, 97, 76, 13, 27, 49]
res = obj.select_sort(arr)
print(res)

arr = [49, 38, 65, 97, 76, 13, 27, 49]
res = obj.heap_sort(arr)
print(res)