python实现耐心排序算法

红太狼 2022-05-11 01:42 177阅读 0赞

前面我们讲解了[耐心排序算法][Link 1]，今天我们来看一下代码的实现，直接上代码

#!/usr/bin/python
    # -*- coding: utf-8 -*-
    #耐心排序
    def _patience_sort(the_list):
        the_list_len = len(the_list)
        if the_list_len <2:#0和1
            print "无需排序"
            return the_list
        else:
            new_list = []
            #第一部分：数据入桶
            for key, value in enumerate(the_list):
                bucket_list = []
                if key == 0:#第一次肯定放到第一个桶中
                    bucket_list.append(value)
                    new_list.append(bucket_list)
                else:
                    is_ok = False
                    for a_key, a_value in enumerate(new_list):#遍历新序列的桶
                        if value <= a_value[0]:#如果取得的元素小于等于桶中第一个元素，则这个元素放到这个桶的最上面
                            a_value = [value]+a_value
                            new_list[a_key] = a_value
                            is_ok = True
                            break
                    # 如果没有则开个新桶
                    if not is_ok:
                        bucket_list.append(value)
                        new_list.append(bucket_list)
                print new_list
    
            #第二部分：从桶中依次取出，这样虽然还是乱的，但是乱的没那么多，数据量大的时候效率就上来了
            ok_list = []
            for o in new_list:
                for k in o:
                    ok_list.append(k)
            print ok_list
            #第三部分：插入排序
            for i in range(len(ok_list)):
                tmp = ok_list[i]
                l = range(0, i)[::-1]
                for m in l:
                    if ok_list[m] > tmp:
                        ok_list[m + 1] = ok_list[m]
                        ok_list[m] = tmp
                        m -= 1
                        continue
            print "最终结果是"+str(ok_list)
    the_list = [6, 4, 5, 1, 8, 7, 2, 3]
    _patience_sort(the_list)

运行结果如下

[[6]]
    [[4, 6]]
    [[4, 6], [5]]
    [[1, 4, 6], [5]]
    [[1, 4, 6], [5], [8]]
    [[1, 4, 6], [5], [7, 8]]
    [[1, 4, 6], [2, 5], [7, 8]]
    [[1, 4, 6], [2, 5], [3, 7, 8]]
    [1, 4, 6, 2, 5, 3, 7, 8]
    最终结果是[1, 2, 3, 4, 5, 6, 7, 8]

符合预期

[Link 1]: https://blog.csdn.net/stronglyh/article/details/82765994