[数据结构][Python]鸡尾酒排序、桶排序

忘是亡心i 2022-01-20 23:51 235阅读 0赞

鸡尾酒排序:

#!/usr/bin/python
    def _cocktail_sort(the_list):
        the_len = len(the_list)
        if the_len <2:#0和1
            print("无需排序")
            return the_list
        else:
            while 1:
                flag = False
                for i in range(the_len-1):
                    if the_list[i] > the_list[i+1]:
                        the_list[i], the_list[i+1] = the_list[i+1], the_list[i]
                    print(the_list)
                j = the_len-1
                while j > 0:
                    if the_list[j-1] > the_list[j]:
                        the_list[j], the_list[j-1] = the_list[j-1], the_list[j]
                        flag = True
                    j -= 1
                    print(the_list)
                if flag == False:
                    break
            return the_list
    if __name__ == '__main__':
        the_list = [6, 4, 5, 1, 8, 7, 2, 3]
        print("原始的列表是:" + str(the_list))
        print("鸡尾酒排序之后的列表是:" + str(_cocktail_sort(the_list)))

原始的列表是:
    [6, 4, 5, 1, 8, 7, 2, 3]
    [4, 6, 5, 1, 8, 7, 2, 3]
    [4, 5, 6, 1, 8, 7, 2, 3]
    [4, 5, 1, 6, 8, 7, 2, 3]
    [4, 5, 1, 6, 8, 7, 2, 3]
    [4, 5, 1, 6, 7, 8, 2, 3]
    [4, 5, 1, 6, 7, 2, 8, 3]
    [4, 5, 1, 6, 7, 2, 3, 8]
    [4, 5, 1, 6, 7, 2, 3, 8]
    [4, 5, 1, 6, 7, 2, 3, 8]
    [4, 5, 1, 6, 2, 7, 3, 8]
    [4, 5, 1, 2, 6, 7, 3, 8]
    [4, 5, 1, 2, 6, 7, 3, 8]
    [4, 1, 5, 2, 6, 7, 3, 8]
    [1, 4, 5, 2, 6, 7, 3, 8]
    [1, 4, 5, 2, 6, 7, 3, 8]
    [1, 4, 5, 2, 6, 7, 3, 8]
    [1, 4, 2, 5, 6, 7, 3, 8]
    [1, 4, 2, 5, 6, 7, 3, 8]
    [1, 4, 2, 5, 6, 7, 3, 8]
    [1, 4, 2, 5, 6, 3, 7, 8]
    [1, 4, 2, 5, 6, 3, 7, 8]
    [1, 4, 2, 5, 6, 3, 7, 8]
    [1, 4, 2, 5, 6, 3, 7, 8]
    [1, 4, 2, 5, 3, 6, 7, 8]
    [1, 4, 2, 3, 5, 6, 7, 8]
    [1, 4, 2, 3, 5, 6, 7, 8]
    [1, 2, 4, 3, 5, 6, 7, 8]
    [1, 2, 4, 3, 5, 6, 7, 8]
    [1, 2, 4, 3, 5, 6, 7, 8]
    [1, 2, 4, 3, 5, 6, 7, 8]
    [1, 2, 3, 4, 5, 6, 7, 8]
    [1, 2, 3, 4, 5, 6, 7, 8]
    [1, 2, 3, 4, 5, 6, 7, 8]
    [1, 2, 3, 4, 5, 6, 7, 8]
    [1, 2, 3, 4, 5, 6, 7, 8]
    [1, 2, 3, 4, 5, 6, 7, 8]
    [1, 2, 3, 4, 5, 6, 7, 8]
    [1, 2, 3, 4, 5, 6, 7, 8]
    [1, 2, 3, 4, 5, 6, 7, 8]
    [1, 2, 3, 4, 5, 6, 7, 8]
    [1, 2, 3, 4, 5, 6, 7, 8]
    [1, 2, 3, 4, 5, 6, 7, 8]
    鸡尾酒排序之后的列表是:
    [1, 2, 3, 4, 5, 6, 7, 8]

桶排序:

如果有一个数组A，包含N个整数，值从1到M，我们可以得到一种非常快速的排序，桶排序（bucket sort）。留置一个数组S，里面含有M个桶，初始化为0。然后遍历数组A，读入Ai时，S\[Ai\]增一。所有输入被读进后，扫描数组S得出排好序的表。该算法时间花费O(M+N)，空间上不能原地排序。  
桶排序原理：

桶排序也叫计数排序，简单来说，就是将数据集里面所有元素按顺序列举出来，然后统计元素出现的次数。最后按顺序输出数据集里面的元素。

排序过程如下：

一、初始化桶的大小

把数据集里面每一个元素当作一个桶，由上面问题看出，原始数据范围在0–9之间，因此我就需要有10个桶，如下图

![在这里插入图片描述][20190616185521297.png]

第一行为初始化计数为0，第二行为各个元素。

二、计数

接下来读入第一原始数据为6,则在下标为6的桶中增加1,如下图：

![在这里插入图片描述][20190616185534512.png]

再读入下一个原始数据为8,则在下标为8的桶中增加1,如下图：

![在这里插入图片描述][20190616185541936.png]

以此类推，最后遍历完所有原始数据时，10个桶的计数如下图：

![在这里插入图片描述][20190616185550257.png]

三、输出数据

在完成原始数据的遍历计数后，接下来遍历各个桶，输出数据：

元素0计数为1,则输出0,

元素1计数为2,则输出1 1,

元素2计数为1,则输出2,

元素3计数为1,则输出3,

元素4计数为1,则输出4,

元素5计数为1,则输出5,

元素6计数为1,则输出6,

元素7计数为0,则不输出元素,

元素8计数为1,则输出8,

元素9计数为1,则输出9,

最后结果输出为：0, 1, 1, 2, 3, 4, 5, 6, 8, 9

#!/usr/bin/env python
    #-*- coding:utf8 -*-
    
    class BucketSort(object):
        '''
        self.datas:       要排序的数据列表
        self.bucketSize:  水桶的大小(数据集的范围，如bucketSize=10,
                          则表示数据集的范围为0-9)
        self.result:      保存排序后的结果
        self.bucket:      代表水桶，指数据集内的所有元素
        _sort():          排序函数
        show():           输出结果的函数
    
        用法：
        BucketSort(datas, size)   或者BucketSort(datas)，size的默认值为100
    
        BucketSort(datas)._sort() 这样就是开始排序
        BucketSort(datas).show()  这样就可以把排序后的结果输出
        '''
        def __init__(self, datas, size=100):
            self.datas = datas
            self.bucketSize = size
            self.result = [0 for i in range(len(datas))]
            self.bucket = [0 for i in range(self.bucketSize)]
    
        def _sort(self):
            # 读入各个元素，并在对应的位置统计，当bucket里的元素不为0
            # 就保存到result里面
            for num in self.datas:
                self.bucket[num] += 1
            j = 0
            for i in range(self.bucketSize):
                while(self.bucket[i]):
                    self.result[j] = i
                    self.bucket[i] -= 1
                    j += 1
    
        def show(self):
            print "Resutl is:",
            for i in self.result:
                print i,
            print ''
    
    
    if __name__ == '__main__':
        try:
            size = raw_input("Please input size(default=100):")
            if size:
                size = int(size)
            datas = raw_input('Please input some number:')
            datas = datas.split()
            datas = [int(datas[i]) for i in range(len(datas))]
        except Exception:
            pass
        if size:
            bks = BucketSort(datas, size)
        else:
            bks = BucketSort(datas)
        bks._sort()
        bks.show()

[![知识共享许可协议][88x31.png]][88x31.png 1]  
本作品采用[知识共享署名-相同方式共享 4.0 国际许可协议][88x31.png 1]进行许可。

[20190616185521297.png]: /images/20220121/b0ee3f4a92024fccbfb93fde187ea2a2.png
[20190616185534512.png]: /images/20220121/e2d3e798a17b4f5fb33cfca301a3fa72.png
[20190616185541936.png]: /images/20220121/d0953c12150841bebfc052adc69e026d.png
[20190616185550257.png]: /images/20220121/74b1f52213464e728ce367ee02a4f537.png
[88x31.png]: https://i.creativecommons.org/l/by-sa/4.0/88x31.png
[88x31.png 1]: http://creativecommons.org/licenses/by-sa/4.0/