>

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

- 编辑:澳门博发娱乐官网 -

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

class OrderBy:    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, func=None):        """        将区间数据进行排序        分区比较,选择一个基准,根据排序规则,正序:比基准大的放右边,比基准小的放左边        :param left: 序列区间的开始位置        :param right: 序列区间的结束位置        :param key: 对于字典对象,如果指定key,则以key对象比较否则当None值处理        :param desc: 比较规则为正序或倒序        :param func: 对值进行处理特殊处理的函数        :return:        """        pivot = self.array[left]        if isinstance(pivot, dict):            if key is not None:                pivot = pivot.get        if callable:            pivot = func        low = left        while low < right:            while low < right:                _left = self.array[low]                _right = self.array[right]                if isinstance(_left, dict):                    _left = _left.get                if isinstance(_right, dict):                    _right = _right.get                if callable:                    _left = func                    _right = func                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, func=None):        """        快速排序算法        :param left: 区间起始位置        :param right: 区间结束位置        :param key: 字典元素使用指定键名值排序        :param desc: 是否倒序        :param func: 对于排序值,支持使用函数处理        :return:        """        if right is None:            right = len(self.array) - 1        if left < right:            pivot_position = self.partition(left, right, key, desc, func)            self.quick_sort(left, pivot_position - 1, key, desc, func)            self.quick_sort(pivot_position + 1, right, key, desc, func)    def sort(self, **condition):        if self.has_condition:            if not self.condition:                return            _condition = self.condition.pop            if isinstance(_condition, dict):                condition['key'] = _condition.get                condition['desc'] = _condition.get('desc', False)        else:            condition.update(**self.extra_condition)        left = condition.get        right = condition.get        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    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:        """        condition_size = len(self.condition)        if not condition_size > 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            if isinstance(_right, dict):                _right = _right.get            # 当上一个值与当前值不相等,则进入二次排序            # 当上一个值与当前值相等,且当前位置等于边界位置,且还有下一个排序条件,则进入二次排序            if _left != _right or (                    end == right and condition_size >= next_index + 1):                condition = self.condition[next_index]                _key = condition.get                desc = condition.get                func = condition.get                if end == right:                    _end = end                else:                    _end = end - 1                self.quick_sort(begin, _end, _key, desc, func)                self.sub_sort(begin, end, _key, next_index + 1)                begin = endif __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    order_by.sort()    print

本文由胜博发-编程发布,转载请注明来源:快排实现仿order by多字段排序