（八大）排序（python语言）

梦里梦外; 2022-05-23 08:47 103阅读 0赞

*  插入排序

![这里写图片描述][70]

> 思想：将一组数组分为有序组和待插入组两组，将待插入组的元素依次与有序组元素比较找到合适的位置插入。

# -*- coding: UTF-8 -*-
    
    
    def main():
        list_1 = [4, 6, 8, 4, 6, 1, 6, 8, 7, 4]
        for i in range(len(list_1)):
            for j in range(len(list_1) - i - 1):
                if list_1[i] > list_1[i + 1]:
                    list_1[i], list_1[i + 1] = list_1[i + 1], list_1[i]
        print(list_1)
    
    
    main()

*  希尔排序

![这里写图片描述][70 1]

> 思想：

这里写代码片

*  选择排序

![这里写图片描述][70 2]

> 思想：每次选择第n次大的数交换到序列的尾端，有n个元素进行排序就重复n次。

这里写代码片

*  冒泡排序

![这里写图片描述][70 3]

> 思想：比较相邻两个元素的大小，将大的交换到右边，有n个元素进行排序就重复n次。

这里写代码片

*  归并排序

![这里写图片描述][70 4]

这里写代码片

*  快速排序

![这里写图片描述][70 5]

这里写代码片

*  堆排序

![这里写图片描述][70 6]

# -*- coding: UTF-8 -*-
    
    
    class PrioQueue:  # 优先队列类
        def __init__(self, elist=[]):  # 新建
            self._elems = list(elist)
            if elist:
                self.buildheap()  # 新建堆
    
        def is_empty(self):  # 判空
            return not self._elems
    
        def peek(self):  # 查看
            if self.is_empty():
                raise PrioQueueError('in peek')  # 为空时返回错误
            return self._elems[0]  #
    
        def enqueue(self, e):  # 入队
            self._elems.append(None)  # 添加一个元素
            self.siftup(e, len(self._elems) - 1)  # 审查
    
        def siftup(self, e, last):  # 筛分
            elems, i, j = self._elems, last, (last - 1) // 2
            while i > 0 and e < elems[j]:
                elems[i] = elems[j]
                i, j = j, (j - 1) // 2
            elems[i] = e
    
        def dequue(self):  # 出队
            if self.is_empty():
                raise PrioQueueError('in peek')  # 为空时返回错误
            elems = self._elems
            e0 = elems[0]
            e = elems.pop()
            if len(elems):  # 审查
                self.siftdown(e, 0, len(elems))
            return e0
    
        def siftdown(self, e, begin, end):  # 筛分
            elems, i, j = self._elems, begin, begin * 2 + 1
            while j < end:
                if j + 1 < end and elems[j + 1] < elems[j]:
                    j += 1  # elems[j]不大于其兄弟节点的数据
                if e < elems[j]:  # e在三者中最小，已经找到其位置
                    break
                elems[i] = elems[j]  # elems[j]在三者中最小，上移
                i, j = j, 2 * j + 1
            elems[i] = e
    
        def buildheap(self):  # 建堆
            end = len(self._elems)
            for i in range(end // 2, -1, -1):
                self.siftdown(self._elems[i], i, end)
    
        def heap_sort(elems):  # 堆排序
            def siftdown(elem, e, begin, end):  # 审查
                i, j = begin, begin * 2 + 1
                while j < end:
                    if j + 1 < end and elems[j + 1] < elems[j]:
                        j += 1  # elems[j]不大于其兄弟节点的数据
                    if e < elems[j]:  # e在三者中最小，已经找到其位置
                        break
                    elems[i] = elems[j]  # elems[j]在三者中最小，上移
                    i, j = j, 2 * j + 1
                elems[i] = e
    
            end = len(elems)
            for i in range(end // 2, -1, -1):  # 建堆，从i开始以end为建堆范围的边界
                siftdown(elems, elems[i], i, end)
            for i in range((end - 1), 0, -1):  # 逐个取出最小元素，将其积累到标的最后，放一个退一步
                e = elems[i]
                elems[i] = elems[0]
                siftdown(elems, e, 0, i)

*  基数排序

这里写代码片

![这里写图片描述][70 7]

[70]: /images/20220523/32002c80cb85412da120547d2a49b99f.png
[70 1]: /images/20220523/b2274fbe50564ce7ad639bf8bf88592b.png
[70 2]: /images/20220523/9c1c7f734bde453da3817d4dae6e4894.png
[70 3]: /images/20220523/3bb5f20393c54efd9e62a0e63fa5d5d5.png
[70 4]: /images/20220523/74cc97b39078481d81ca52a6d46e1ad2.png
[70 5]: /images/20220523/ef165d4efd9f49eca74419f83e0f6126.png
[70 6]: /images/20220523/a1e04df2c4cb4c51b2a19d6934249591.png
[70 7]: /images/20220523/120adc157dac46fa9a0dd9343c84365d.png