欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

快排实现仿order by多字段排序

程序员文章站 2023-03-31 22:17:45
```python class OrderBy(object): def __init__(self, sequence, condition, extra_condition): """ 排序初始化条件 condition为优先排序条件,序列内元素必须为字典类型 extra_condition为额 ......
class orderby(object):

    def __init__(self, sequence, *condition, **extra_condition):
        """
        排序初始化条件
        condition为优先排序条件,序列内元素必须为字典类型
        extra_condition为额外的条件因素,当condition不存在时,额外条件才会生效
        :param sequence:
        :param condition:
        :param extra_condition:
        """
        self.array = sequence
        self.condition = list(condition)
        self.extra_condition = extra_condition
        self.has_condition = bool(self.condition)

    def partition(self, left, right, key=none, desc=false):
        """
        将区间数据进行排序
        分区比较,选择一个基准,根据排序规则,正序:比基准大的放右边,比基准小的放左边
        :param left: 序列区间的开始位置
        :param right: 序列区间的结束位置
        :param key: 对于字典对象,如果指定key,则以key对象比较否则当none值处理
        :param desc: 比较规则为正序或倒序
        :return:
        """
        pivot = self.array[left]
        if isinstance(pivot, dict):
            if key is not none:
                pivot = pivot.get(key)
        low = left
        while low < right:
            while low < right:
                _left = self.array[low]
                _right = self.array[right]
                if isinstance(_left, dict):
                    _left = _left.get(key)
                if isinstance(_right, dict):
                    _right = _right.get(key)
                if desc:
                    # 倒序,右边值与基准值都不为空,且右边值小于基准值,左移
                    if _right and pivot and _right < pivot:
                        right -= 1
                    # 倒序,右边值为空,左移
                    elif not _right:
                        right -= 1
                    # 倒序,左边值与基准值都不为空,且左边值大于等于基准值,右移
                    elif _left and pivot and _left >= pivot:
                        low += 1
                    # 倒序,基准值为空,左边值不为空,右移
                    elif _left and not pivot:
                        low += 1
                    else:
                        break
                else:
                    # 正序,基准为空,右边值不为空,左移
                    if _right and not pivot:
                        right -= 1
                    # 正序,右边值与基准都不为空,且右边值大于基准值,左移
                    elif _right and pivot and _right > pivot:
                        right -= 1
                    # 正序,左边值与基准都不为空,且左边值小于等于基准值,右移
                    elif _left and pivot and _left <= pivot:
                        low += 1
                    # 正序,左边值为空,右移
                    elif not _left:
                        low += 1
                    else:
                        break
            if low < right:
                temp = self.array[low]
                self.array[low] = self.array[right]
                self.array[right] = temp
        self.array[left], self.array[low] = self.array[low], self.array[left]
        return low

    def quick_sort(self, left=0, right=none, key=none, desc=false):
        if right is none:
            right = len(self.array) - 1
        if left < right:
            pivot_position = self.partition(left, right, key, desc)
            self.quick_sort(left, pivot_position - 1, key, desc)
            self.quick_sort(pivot_position + 1, right, key, desc)

    def sort(self, **condition):
        if self.has_condition:
            if not self.condition:
                return
            _condition = self.condition.pop(0)
            if isinstance(_condition, dict):
                condition['key'] = _condition.get('key')
                condition['desc'] = _condition.get('desc', false)
        else:
            condition.update(**self.extra_condition)
        left = condition.get('left')
        right = condition.get('right')
        if not left:
            left = 0
            condition['left'] = left
        if not right:
            right = len(self.array) - 1
            condition['right'] = right
        self.quick_sort(**condition)
        self.sub_sort(left, right, condition.get('key'))

    def sub_sort(self, left, right, key=none, next_index=0):
        """
        标记当前位置begin,及下一个位置end
        当begin位置的元素与end位置元素不等时,当begin!=end - 1时,则进行区间排序
        :param left: 区间起始位置
        :param right: 区间结束位置
        :param key: 当前排序键名
        :param next_index: 下一个条件位置
        :return:
        """
        if not self.condition or len(self.condition) < next_index:
            return
        begin = left
        for end in range(left, right + 1):
            _left = self.array[begin]
            _right = self.array[end]
            if isinstance(_left, dict):
                _left = _left.get(key)
            if isinstance(_right, dict):
                _right = _right.get(key)
            if _left != _right:
                if begin != end - 1:
                    condition = self.condition[next_index]
                    key = condition.get('key')
                    desc = condition.get('desc')
                    self.quick_sort(begin, end - 1, key=key, desc=desc)
                    self.sub_sort(begin, end - 1, key, next_index + 1)
                begin = end


if __name__ == '__main__':
    a = [dict(age=18, money=200, name='z1'),
         dict(age=16, money=200, name='z2'),
         dict(age=16, money=200, name='z3'),
         dict(age=16, money=100, name='z4'),
         dict(age=16, money=200, name='z5')]
    order_by = orderby(a, dict(key='age', desc=false),
                       dict(key='money', desc=true),
                       dict(key='name', desc=true))
    print(a)
    order_by.sort()
    print(a)