时间戳

首页 > 解决方案 > 使用快速排序按频率对元素进行排序：如何按大小对相同频率的元素进行排序？

python - 使用快速排序按频率对元素进行排序：如何按大小对相同频率的元素进行排序？

问题描述

我正在尝试使用快速排序在 Python 中解决这个问题：

给定一个整数数组 A[]，根据元素的频率对数组进行排序。那就是频率较高的元素首先出现。如果两个元素的频率相同，则较小的数字先出现。

我创建了一个数组来存储 A[] 中每个整数的出现次数，如下所示：

def find_count(arr, n):
    count = [0]*(max(arr)+1)
    for i in arr:
        count[i] += 1
    return count

接下来，我使用快速排序来按出现次数的降序对元素进行排序：

def quicksort(arr, low, high, count):
    if(low < high):
        i = low
        j = high
        pivot = low
        while(i < j):
            while(i < high and count[arr[i]] >= count[arr[pivot]]):
                i += 1
            while(count[arr[j]] < count[arr[pivot]]):
                j -= 1
            if(i < j):
                arr[i], arr[j] = arr[j], arr[i]
        arr[pivot], arr[j] = arr[j], arr[pivot]
        quicksort(arr, low, j-1, count)
        quicksort(arr, j+1, high, count)

此方法用于按频率降序对元素进行排序。但是，具有相同频率的元素会以不可预知的顺序出现（不是按要求按大小递增的顺序）：

For Input:
[5, 5, 4, 6, 4]
your output is: 
[5, 4, 4, 5, 6]
required output:
[4, 4, 5, 5, 6]

如何实现条件以按大小递增的顺序对具有相同频率的元素进行排序？

标签： pythonarrayssorting

解决方案

您修改快速排序，使其使用键功能

  • 类似于 Python 排序函数如何使用键函数
  • 更通用的解决方案，因为可以通过使用不同的键功能按其他标准排序

修改后的代码

def find_count(arr, n):
    count = [0]*(max(arr)+1)
    for i in arr:
        count[i] += 1
    return count

def quicksort(arr, low, high, keyfunc):
    if(low < high):
        i = low
        j = high
        pivot = low
        while i < j:
            while i < high and keyfunc(arr[i]) >= keyfunc(arr[pivot]):
                i += 1
            while keyfunc(arr[j]) < keyfunc(arr[pivot]):
                j -= 1
            if i < j:
                arr[i], arr[j] = arr[j], arr[i]
        arr[pivot], arr[j] = arr[j], arr[pivot]
        quicksort(arr, low, j-1, keyfunc)
        quicksort(arr, j+1, high, keyfunc)

测试

a = [5, 5, 4, 6, 4]
count = find_count(a, len(a))

# Use key function based upon tuple of count and value (use -v since want lower values first)
quicksort(a, 0, len(a)-1, lambda v: (count[v], -v)) 
# new a: [5, 5, 4, 6, 4]

# Change key function to sort strings
a = ['to', 'be', 'or', 'not', 'to', 'be', 'a', 'fool']
quicksort(a, 0, len(a)-1, lambda v: (-len(v), v))
# new a: ['a', 'to', 'to', 'or', 'be', 'be', 'not', 'fool']

推荐阅读