python实现选择排序

川长思鸟来 2022-11-01 04:19 155阅读 0赞

**简单选择排序**  
基本思想：假设排序表为L\[1…n\]，第i趟排序即从L\[i…n\]中选择关键字最小的的元素与L\[i\]交换，每一趟排序可以确定一个元素的最终位置，则经过n-1趟排序可以使得整个排序表有序。  
![在这里插入图片描述][20210324140938178.gif_pic_center]

def SelectionSort(A):
        le=len(A)
        for i in range(le):#遍历次数
            for j in range(i+1,le):#查找待排序序列中的最小元素并交换
                if A[i]>A[j]:
                    A[i],A[j]=A[j],A[i]
        print(A)
    tes=[2,4,5,46,34,56,345,34,454]
    SelectionSort(tes)#[2, 4, 5, 34, 34, 46, 56, 345, 454]

空间效率：仅使用常数个辅助单元，因此空间效率为O(1)  
时间效率：O(n²)  
它是一个不稳定的排序算法。

**堆排序**  
堆排序是一种树形选择排序方法，在排序过程中，将L\[1…n\]看作一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大（或最小）的元素。  
堆的定义：  
n个关键字序列L\[1…n\]称为堆，当且仅当该序列满足：  
1）L\[i\]<=L\[2i\]且L\[i\]<=L\[2i+1\](小根堆）  
2) L\[i\]>=L\[2i\]且L\[i\]>=L\[2i+1\](大根堆）  
![在这里插入图片描述][20210323185528212.png]堆排序的关键是构造初始堆，对初始序列建堆，就是一个反复筛选的过程。n个结点的完全二叉树，最后一个结点是n//2个节点的孩子。对n//2个节点为根的子树筛选（对于大根堆，若根结点的关键字小鱼左右子女中关键字较大者，则交换），使该子树成为堆。之后向前依次对各节点（n//2~1）为根的子树进行筛选，看该结点是否大于其左右子节点的值，若不是，则将左右子结点中较大值与之交换，交换后可能会破坏下一级的堆，于是继续采用上述方法构造下一级的堆，直到以该结点为根的子树构成堆为止。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdWxhbmJh_size_16_color_FFFFFF_t_70]同时，堆也支持删除和插入操作。由于堆顶元素为最大值或者最小值，删除堆顶元素时，先将堆的最后一个元素与堆顶元素交换，由于此时堆得性质被破坏，需对此时的根结点进行向下调整操作。  
对堆进行插入操作时，先将新结点放在堆的末端，再对这个结点执行向上调整操作。

![在这里插入图片描述][20210323192750446.png]![在这里插入图片描述][20210324141158238.gif_pic_center]

# 实现一个最大堆
    class MaxHeap(object):
        """ 实现一个大顶堆 """
    
        def __init__(self):
            self.array = [] # 用一个数组存放堆中元素
    
        def heapify(self, array):
            """ 对传入的数组进行堆化 """
            for a in array:
                self.push(a)
            return self.array
    
        def get_size(self):
            """ 返回堆的大小 """
            return len(self.array)
    
        def _parent(self, index):
            """ 返回某个节点的父节点 """
            if index == 0:
                raise Exception('Index 0 has no parent')
            return int((index - 1) / 2)
    
        def _left_child(self, index):
            """ 返回左孩子节点的索引 """
            return index * 2 + 1
    
        def _right_child(self, index):
            """ 返回右边孩子节点的索引 """
            return index * 2 + 2
    
        def _shift_up(self, k):
            """ 节点上移动，将当前节点与其父亲节点比较大小，如果比父亲节点大， 则交换其位置，重复只执行上述过程，直到当前节点比父亲节点小。 """
            while k > 0 and self.array[self._parent(k)] < self.array[k]:
                # 交换节点与父节点的值
                self.array[self._parent(k)], self.array[k] = self.array[k], self.array[self._parent(k)]
                k = self._parent(k)
    
        def _shift_down(self, k):
            """ 节点下移动, 当前节点与它左右孩子中最大的节点交换位置 """
            while self._left_child(k) < self.get_size():
                choose_index = self._left_child(k)  # 左孩子的索引
                # 先比较左右孩子的大小，选择较大的那个孩子再与父亲节点进行比较
                if choose_index + 1 < self.get_size() and self.array[choose_index + 1] > self.array[choose_index]:
                    choose_index = self._right_child(k)
                if self.array[choose_index] <= self.array[k]:  # 如果最大的孩子比父亲节点小，退出循环
                    break
                # 否则父亲节点和最大的子节点交换位置
                self.array[choose_index], self.array[k] = self.array[k], self.array[choose_index]
                k = choose_index  # 进行下次循环
    
        def push(self, value):
            """ 添加一个元素后，需要对堆重新进行堆化，具体过程就是对堆尾元素执行上移操作； """
            self.array.append(value)
            self._shift_up(self.get_size() - 1)  # 相当于对堆进行重新堆化
    
        def pop(self):
            """ 返回堆顶元素，将堆顶元素和堆最后一个元素交换， 然后返回最后一个元素，最后对堆顶元素进行下沉操作（重新堆化） """
            ret = self.find_max()
            self.array[0], self.array[self.get_size() - 1] = self.array[self.get_size() - 1], self.array[0]
            self.array.pop(-1)  # 删除最后一个元素
            self._shift_down(0)
            return ret
    
        def find_max(self):
            """ 查看堆中的最大值 """
            if self.array:
                return self.array[0]
            else:
                raise Exception('Empty heap has no value')
    
    # 测试我们实现的大顶堆
    test = [12, 11, 10, 9, 6, 7, 8, 13]
    max_heap = MaxHeap()
    print(max_heap.heapify(test)) # 对一个数组执行堆化
    print(max_heap.pop()) # 弹出堆顶元素
    print(max_heap.array) 
    max_heap.push(14) # 推入一个元素
    print(max_heap.array)

空间效率：仅使用常数个辅助单元，因此空间效率为O(1)  
时间效率：O(nlog2 N)  
它是一种不稳定的排序算法

[20210324140938178.gif_pic_center]: /images/20221024/537f08177ed942eab52037e7ca20e7ec.png
[20210323185528212.png]: /images/20221024/6d9ebcbc121a4af0ba97db0862f39526.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdWxhbmJh_size_16_color_FFFFFF_t_70]: /images/20221024/6b1b922e876a433684de6c8768266401.png
[20210323192750446.png]: https://img-blog.csdnimg.cn/20210323192750446.png
[20210324141158238.gif_pic_center]: /images/20221024/b0fe20f80ffe43ccb95291ba768924fe.png