跳至主要內容

Sort

Someone大约 6 分钟

Sort

GitHub Sort codeopen in new window

Abstract

Base Sort Function Py

在 Python 中，按照优先级进行排序可以使用 lis.sort(lombda x: (x[1], x[0])) 这样的方式。

举例来说，对于要排序的数组：[(2, 0), (3, 1), (3, 2), (4, 3), (3, 4)], 我们对其进行排序：

res.sort(key=lambda x: (-x[0], x[1]))
# [(4, 3), (3, 1), (3, 2), (3, 4), (2, 0)]

# example 2
# before [(3, 0), (3, 1), (3, 2), (3, 3), (3, 4)]
# after  [(3, 0), (3, 1), (3, 2), (3, 3), (3, 4)]

此时达到的效果是，第一个元素降序，第二个元素升序。

res.sort(key=lambda x: (x[0], x[1]))
# [(2, 0), (3, 1), (3, 2), (3, 4), (4, 3)]

此时达到的效果是，第一个元素升序，第二个元素升序。这个也是默认的情况。

剩下的可以直接研究，总结来说：sort 默认的是升序。

cmp_to_key

Python 自定义排序函数

值得一提的是，上述代码我们实现了一个自定义的比较函数，在 python 中自定义比较函数，首先需要对其进行定义，而后使用 key=cmp_to_key(compare) 来进行自定义比较，其中 cmp_to_key 需要导入：

from functools import cmp_to_key

对于这个比较函数，还可以再研究一下：

def compare_test(self, nums: List[int]) -> List[int]:
    def compare(x: int, y: int):
        return x - y

    nums = sorted(nums, key=cmp_to_key(compare))
    return nums

测试结果如下：

def test01(self):
    nums = [3, 30, 34, 5, 9]
    res = self.s.compare_test(nums)
    self.assertEqual(sorted(nums), res)
    print(res) # [3, 5, 9, 30, 34]

可以看到 x - y 比较的结果是使得其升序排列了。

还有一个 leetcode 的例子是 cmp_to_key 的应用，953. 验证外星语词典open in new window，具体可以参考后面的实例章节。

Sort

Insertion Sort

直接使用 bisect 模块，可以直接插入某个元素，返回排序好的元素：

import bisect
nums = [1, 3, 4]
bisect.insort(nums, 2)
print(nums)  # [1, 2, 3, 4]

Merge Sort

T(n)=O(nlog2n)T(n) = O(nlog_{2}n)

another example:

  • Counting Inversions

  • Matrix Multiplication:

    • Brute Force(暴力): O(n3)O(n^3) arithmetic operations

Quick Sort

  • Worst-case running time O(n2)O(n^2) :
    • input sorted or reverse sorted, partition around min or max element.
    • one side of partition has no elements.
    • T(n)=T(0)+T(n−1)+cnT(n) = T(0) + T(n-1) + cn
  • Expected running time O(nlgn)O(nlgn)
    • If we are really lucky, partition splits the array evenly 2n\frac{2}{n} : T(n)=2T(n/2)+Θ(n)=Θ(nlgn)T(n)=2T(n/2)+Θ(n)=Θ(nlgn)
def qsort(arr):
    if not arr:
        return []
    else:
        pivot = arr[0]
        l = [_ for _ in arr if _ < pivot]
        r = [_ for _ in arr[1:] if _ >= pivot]
        return qsort(l) + [pivot] + qsort(r)

Selection Sort

def selection_sort(arr):
​    for i in range(len(arr)):
​        minimum = i
​        for j in range(i+1, len(arr)):
​            if arr[j] < arr[minimum]:
​                minimum = j
​        arr[minimum], arr[i] = arr[i], arr[minimum]
​    return arr

Sort Template

C++ 使用模板降序排列：

struct greater
{
    template<class T>
    bool operator()(T const &a, T const &b) const { return a > b; }
};
std::sort(numbers.begin(), numbers.end(), greater());

Swap

  1. 基本实现：

    //引用实现
swap(int &x, int &y){
​    int temp;
​    temp = x;
​    x= y;
​    y =x;
}
swap(x, y);

//指针实现
swap(int *x, int *y){
​       int temp;
​       temp = *x;
​       *x = *y;
​       *y = temp;
}
swap(&x, &y);

  2. 异或实现：

    void swap(int &x, int &y){
​    x ^= y;
​    y ^= x;
​    x ^= y;
}
swap(x, y);

void swap(int *x, int *y){
​    *x ^= *y;
​    *y ^= *x;
​    *x ^= *y;
}
swap(&x, &y);

  3. 加减操作：

    void swap(int &x, int &y){
​    x = x + y;
​    y = x - y;
​    x = x - y;
}
swap(x, y);

void swap(int *x, int *y){
​    *x = *x + *y;
​    *y = *x - *y;
​    *x = *x - *y;
}
swap(&x, &y);

  4. 宏定义：

    #define swap(x, y) { x ^= y; y ^= x; x ^= y; }
#define swap(x, y) { x = x + y; y = x - y; x = x - y; }
swap(x, y);

Problems

LC179 最大数

Given a list of non negative integers, arrange them such that they form the largest number.

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

Input: [10,2]

Output: "210"

https://leetcode-cn.com/problems/largest-number/open in new window

对于这个题目，本质上是一个排序问题，要是不使用自带的排序方法，可以使用冒泡排序的方法。

10 和 2 的大小关系（或者说前后顺序），可以根据 10 + 2 = 102 和 2 + 10 = 210 的大小来判断。

冒泡排序 C 解法

这是百度百科冒泡排序算法的参考：

void bubbleSort(elemType arr[], int len)
{
    elemType temp;
    int i, j;
    for (i = 0; i < len - 1; i++)
        for (j = 0; j < len - 1 - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
}

一刷

该题目的解法如下：

def largestNumber(self, nums: List[int]) -> str:
    for i in range(len(nums) - 1):
        for j in range(len(nums) - i - 1):
            if int(str(nums[j]) + str(nums[j + 1])) < int(str(nums[j + 1]) + str(nums[j])):
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
    if set(nums) == {0}:
        return '0'
    res = ''.join([str(_) for _ in nums])
    i = 0
    while i < len(res) and res[i] == '0':
        i += 1
        res = res[1:]
    return res

附上 leetcode 大神的解法：

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        nums = list(map(str, nums))
        max_len = max(map(len, nums))
        nums.sort(key=lambda x: x*(max_len // len(x) + 1), reverse=True)
        return ''.join(nums) if nums[0] != '0' else '0'

主要到 lambda 表达式中出现了一个 +1, 是因为有时候会遇到奇数的情况，比如说：[121, 12] 这种情况，会得出商为 1, 从而产生错误的结果。

二刷

二刷于 2022年4月18日。

我们需要对这个题目进行更加深入的理解，举例来说：

  • [4,42]: 需要比较 442 和 424, 所以我们需要把 4 放在 42 的前面拼接成最大值 442, 此时我们可以知道，如果对 4 和 42 进行排序的话，那么必须满足：

    4>42 4 > 42

    在这个例子中，442 - 424 > 0

  • [4,45]: 需要比较 445 和 454, 我们需要把 45 放在 4 的前面拼接成最大值 454.

    在这个例子中，445 - 454 < 0

所以说，我们定义一个比较函数，这个比较函数实现上述比较关系的结果：

def compare(x, y): 
    return int(y+x) - int(x+y)

如何理解这个比较函数呢？我们举例，如果要降序排列的话，对应的比较函数如下：

def compare(x, y):
    return y - x

最终的实现如下：

from functools import cmp_to_key
from typing import List


class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        def compare(x: str, y: str):
            return int(y + x) - int(x + y)

        nums = sorted(map(str, nums), key=cmp_to_key(compare))
        return '0' if nums[0] == '0' else ''.join(nums)

LC953 验证外星语词典

953. 验证外星语词典open in new window

某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。

给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。

示例 1：

输入：words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"

输出：true

解释：在该语言的字母表中，'h' 位于 'l' 之前，所以单词序列是按字典序排列的。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/verifying-an-alien-dictionaryopen in new window
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我们使用 python 的 cmp_to_key 的解法如下：

class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        dic = {v: i for i, v in enumerate(order)}

        def cmp(s1, s2):
            i = 0
            while i < len(s1) and i < len(s2):
                if dic[s1[i]] > dic[s2[i]]:
                    return -1
                elif dic[s1[i]] < dic[s2[i]]:
                    return 1
                else:
                    i += 1

            return 1 if i < len(s1) else -1

        words_sorted = sorted(words, key=cmp_to_key(cmp))
        return words_sorted == words
2017-2023
Copyright © 2024 Someone