归并排序

经典排序算法之一,分冶思想

from unittest import (
        main,
        TestCase,
        )
from random import Random


def merge(lst):
    if len(lst) <= 1:
        return lst

    def _merge(left, right):
        result = []
        while left and right:
            if left[0] <= right[0]:
                result.append(left.pop(0))
            else:
                result.append(right.pop(0))
        result.extend(right if right else left)
        return result

    left = merge(lst[:len(lst)//2])
    right = merge(lst[len(lst)//2:])
    return _merge(left, right)


class MergeTestCase(TestCase):
    def setUp(self):
        self.data = list(
                Random().sample(range(10000), 100)
                for i in range(100)
                )

    def testMerge(self):
        for _data in self.data:
            print _data
            self.assertEqual(
                    merge(_data),
                    sorted(_data),
                    )


if __name__ == '__main__':
    main()
Advertisements
此条目发表在Python分类目录。将固定链接加入收藏夹。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s