一道阿里的多级排序算法题

刚刚做了阿里的模拟笔试题，算法题是一道多级排序的问题。这题其实以前就做过，之前测评的时候也是同一道题目。

这题的意思就是给条码排序，条码分三部分，主要根据第一部分从小到大排序，第一部分相同的情况下按第二部分从后往前排序，第二部分相同的情况下按第三部分从大到小排序。

举个例子，比如有下面这样五个条形码：

123AB456
123BA444
222BA444
222BA555
196AA321

按照排序规则，最后排序之后应该是像下面这样：

123BA444
123AB456
196AA321
222BA555
222BA444

一开始我想这怎么排序，如果一部分一部分排的话，那第一部分排完之后，再排第二部分，之前排的不是乱掉了么。。

后来突然想到，其实这三部分的重要程度是递减的，最主要是根据第一部分来排的，所以可以换个角度思考，先从最不重要的第三部分开始排，然后排第二部分，最后排第一部分。这里面最关键的就是前面已经排好的怎么能保持顺序，这时候我们就应该要想到排序算法所谓的“稳定排序”的特性，即排序前后，两个相同元素的相对位置不会发生变化，这就是我们需要的。

所以我们可以使用冒泡排序这种稳定排序算法来对这三部分进行排序，并且从最不重要的第三部分开始排序。

以下就是最终的算法：

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys


def bubble_sort(array, index, reversed=False):
    """
    冒泡排序
    index 表示排序依据的是哪个部分
    reversed=False 表示从小到大排序，反之相反
    """
    for i in range(len(array)):
        swaped = False
        if reversed:
            # 从后往前冒泡，大的元素浮到前面
            for j in range(len(array) - 1, i, -1):
                if array[j][index] > array[j - 1][index]:
                    array[j - 1], array[j] = array[j], array[j - 1]
                    swaped = True
        else:
            # 从后往前冒泡，小的元素浮到前面
            for j in range(len(array) - 1, i, -1):
                if array[j][index] < array[j - 1][index]:
                    array[j - 1], array[j] = array[j], array[j - 1]
                    swaped = True
        if swaped is False:  # 最后一趟没有交换任何元素，则表明数组已经有序
            break


if __name__ == '__main__':

    codes = []  # 分段存储条形码

    n = int(sys.stdin.readline().strip())  # 输入条形码数量
    # 依次输入条形码
    for i in range(n):
        code = sys.stdin.readline().strip()
        codes.append((code[0:3], code[3:5], code[5:8]))  # 将原条形码拆分成三部分组成元组之后添加到数组中

    # 使用冒泡排序这个“稳定“排序算法来进行多级排序，并且从最次要的部分开始排
    bubble_sort(codes, 2, reversed=True)
    bubble_sort(codes, 1, reversed=True)
    bubble_sort(codes, 0)

    # 拼接分段
    new_codes = []
    for item in codes:
        code = item[0] + item[1] + item[2]
        new_codes.append(code)

    # 输出结果
    print new_codes

测试一下：