在没有排序功能的情况下按某个元素对嵌套列表进行排序. [英] Sorting a nested list by a certain element without the sorting function.

问题描述

如果我有一个这样的嵌套列表:

L = [['James', '1', '2'], ['Alan', '1', '1'], ['Henry', '1', '5']]

如何在不使用排序或排序功能的情况下，根据每个子列表中的最后一个数字从高到低排序?

输出:

final = [['Henry', '1', '5'], ['James', '1', '2'], ['Alan', '1', '1']]

我知道怎么做的唯一方法是使用排序功能，但我想知道没有它怎么做.

解决方案

您可以编写自己的quicksort 函数.您几乎可以切换一些符号来反转输出:

def 快速排序(arr):如果 len(arr) <= 1:返回 arr枢轴 = arr[len(arr)/2]left = [x for x in arr if x >枢]中间 = [x for x in arr if x == pivot]right = [x for x in arr if x <枢]返回快速排序(左)+ 中间 + 快速排序(右)

下一步是确保您提取了正确的数字，并确保您可以将这些数字映射回父列表，以便您可以再次将它们放入正确的位置 — Allen 的回答 有一个很好的方法:

L = [['James', '1', '2'], ['Alan', '1', '1'], ['Henry', '1', '5']]keys = [(int(v[-1]),k) for k,v in enumerate(L)] # 这一行在这里

该行基本上创建了一个元组列表，用于存储我们想要排序的数字，以及该数字的父列表在总体列表上的索引.所以基本上，对于 L，keys = [(2, 0), (1, 1), (5, 2)].

因此，您可以通过创建可递归使用的子函数来更改 quicksort 函数以解决所有这些问题:

def 快速排序(arr):# 把实际的排序函数放到一个可以递归调用的子函数中定义子排序(arr2):如果 len(arr2) <= 1:返回 arr2枢轴 = arr2[len(arr2)/2]left = [x for x in arr2 if x >枢]中间 = [x for x in arr2 if x == pivot]right = [x for x in arr2 if x <枢]返回子排序(左)+中间+子排序(右)# 获取值键对并对其进行排序键 = [(int(v[-1]),k) for k,v in enumerate(L)]键 = 子排序(键)# 映射回馈入主函数的原始数组最终 = []对于键中的 i:final.append(arr[i[1]])返回决赛

然后:

<预><代码>>>>L = [['詹姆斯', '1', '2'], ['艾伦', '1', '1'], ['亨利', '1', '5']]>>>快速排序(L)[['亨利', '1', '5'], ['詹姆斯', '1', '2'], ['艾伦', '1', '1']]

注意:如果在最后一个位置有两个具有相同编号的项目，它们将获得它们在原始列表中的原始相对位置(彼此之间)还原.有关元组比较的更多详细信息，请参阅此答案，并注意我们按降序 在这里订购(否则，他们只会保持彼此的原始位置).所以:

<预><代码>>>>L = [['西蒙', '1', '2'], ['亨利', '1', '5'], ['芬恩', '1', '2']>>>快速排序(L)[['亨利', '1', '5'], ['芬恩', '1', '2'], ['西蒙', '1', '2']]

If I have a nested list like this:

L = [['James', '1', '2'], ['Alan', '1', '1'], ['Henry', '1', '5']]

How can I sort it from highest to lowest based on the last number in each of the sub lists without using the sorting or sorted function?

Output:

final = [['Henry', '1', '5'], ['James', '1', '2'], ['Alan', '1', '1']]

The only way I know how to do it is with the sorting function, but I would like to know how to do it without that.

解决方案

You can write your own quicksort function. You can pretty much switch some signs to reverse the output:

def quicksort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr)/2]

    left = [x for x in arr if x > pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x < pivot]

    return quicksort(left) + middle + quicksort(right)

The next step would be to make sure you're extracting the proper numbers, and make sure you can map those back to the parent list so you can drop those into the right place again — Allen's answer has a good approach:

L = [['James', '1', '2'], ['Alan', '1', '1'], ['Henry', '1', '5']]

keys = [(int(v[-1]),k) for k,v in enumerate(L)] # This line here

That line basically creates a list of tuples that store the numbers we wanna sort by, and the index of that number's parent list on the overarching list. So basically, for L, keys = [(2, 0), (1, 1), (5, 2)].

So you'd alter the quicksort function to account for all this, by creating a subfunction that can be used recursively:

def quicksort(arr):
    # Put the actual sorting function into a subfunction that can be called recursively
    def subsort(arr2):
        if len(arr2) <= 1:
            return arr2
        pivot = arr2[len(arr2)/2]
        left = [x for x in arr2 if x > pivot]
        middle = [x for x in arr2 if x == pivot]
        right = [x for x in arr2 if x < pivot]
        return subsort(left) + middle + subsort(right)

    # Get the value-key pairs and sort them
    keys = [(int(v[-1]),k) for k,v in enumerate(L)]
    keys = subsort(keys)

    # Do the mapping back to the original array fed into the main function
    final = []
    for i in keys:
        final.append(arr[i[1]])

    return final

And with that:

>>> L = [['James', '1', '2'], ['Alan', '1', '1'], ['Henry', '1', '5']]
>>> quicksort(L)
[['Henry', '1', '5'], ['James', '1', '2'], ['Alan', '1', '1']]

Note: If there are two items with the same number in the last position those are gonna get their original relative position (to one another) in the original list reverted. See this answer for more details on tuple comparison, and note that we're sorting stuff in descending order here (otherwise, they'd just keep their original position relative to one another). So:

>>> L = [['Simon', '1', '2'], ['Henry', '1', '5'], ['Finn', '1', '2']
>>> quicksort(L)
[['Henry', '1', '5'], ['Finn', '1', '2'], ['Simon', '1', '2']]

这篇关于在没有排序功能的情况下按某个元素对嵌套列表进行排序.的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！