快排实现仿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)
下一篇: 中国历史:后燕与西燕,西燕为何大败?