如何根据元素对二维数组进行字母排序，且不使用内置排序函数？（python）

Question

我在这个问题上卡了很久，能有人帮我一下吗？

假设我有一个数组：

[[231,cow,234334,2231319,323242],[3,alien,2,2312,3212],[9,box,234,2319,3242]]

有人能帮我写一个排序函数吗？这个函数需要根据每个小数组的第二个元素来对大数组进行字母排序，最后的结果应该像这样：

[[3,alien,2,2312,3212],[9,box,234,2319,3242],[231,cow,234334,2231319,323242]]

Answer 1

归并排序（Mergesort）很容易实现。它是一种“分而治之”的算法，意思是把一个大问题拆分成几个小问题（先排序左边一半，再排序右边一半，最后把它们合并起来）。

a = [[231,'cow',234334,2231319,323242],[3,'alien',2,2312,3212],[9,'box',234,2319,3242]]

def merge_sort(a):
    # copy the original array so it's unaffected
    b = a[:]
    # if there are 2 or fewer elements, just compare and return in the right order
    if len(b) < 2:
        return b
    elif len(b) == 2:
        x,y = b
        if x[1] <= y[1]:
            return b
        else:
            return [y,x]
    # if there are more than 2, break it to 2 sub-arrays and recursively sort both
    else:
        m = int(len(b)/2)
        p1 = merge_sort(b[:m])
        p2 = merge_sort(b[m:])
        rs = []
        # then combine them by repeatedly popping the smaller one
        while len(p1) > 0 or len(p2) > 0:
            if len(p1) == 0:
                rs.append(p2.pop(0))
            elif len(p2) == 0:
                rs.append(p1.pop(0))
            elif p1[0][1] <= p2[0][1]:
                rs.append(p1.pop(0))
            else:
                rs.append(p2.pop(0))
        return rs

print merge_sort(a)

Answer 2

sort(array, key=lambda x: x[1])

如果你不想使用内置的排序功能，那就自己写一个带键的排序函数，然后像上面那样调用它就可以了。

Answer 3

这里有一个简单的冒泡排序，它是最容易理解的排序方法之一（看起来像是作业）。我认为关键在于，老师想让你考虑二维的方面，这里意味着你需要在比较时关注第二列的第二个元素。我对比较的部分做了一些修改。我刚刚测试过，你需要在字符串元素周围加上引号。

   def bubblesort( A ):
     for i in range( len( A ) ):
       for k in range( len( A ) - 1, i, -1 ):
         if ( A[k][1] < A[k - 1][1] ):
           swap( A, k, k - 1 )

   def swap( A, x, y ):
     tmp = A[x]
     A[x] = A[y]
     A[y] = tmp

   A=[[231,'cow',234334,2231319,323242],[3,'alien',2,2312,3212],[9,'box',234,2319,3242]]
   print A
   bubblesort(A)
   print A