跳至主要內容

0912. 排序数组

ITCharge大约 21 分钟

0912. 排序数组open in new window

  • 标签:数组、分治、桶排序、计数排序、基数排序、排序、堆(优先队列)、归并排序
  • 难度:中等

题目链接

题目大意

描述:给定一个整数数组 numsnums

要求:将该数组升序排列。

说明

  • 1nums.length51041 \le nums.length \le 5 * 10^4
  • 5104nums[i]5104-5 * 10^4 \le nums[i] \le 5 * 10^4

示例

  • 示例 1:
输入:nums = [5,2,3,1]
输出:[1,2,3,5]
  • 示例 2:
输入:nums = [5,1,1,2,0,0]
输出:[0,0,1,1,2,5]

解题思路

这道题是一道用来复习排序算法,测试算法时间复杂度的好题。我试过了十种排序算法。得到了如下结论:

  • 超时算法(时间复杂度为 O(n2)O(n^2)):冒泡排序、选择排序、插入排序。
  • 通过算法(时间复杂度为 O(n×logn)O(n \times \log n)):希尔排序、归并排序、快速排序、堆排序。
  • 通过算法(时间复杂度为 O(n)O(n)):计数排序、桶排序。
  • 解答错误算法(普通基数排序只适合非负数):基数排序。

思路 1:冒泡排序(超时)

冒泡排序(Bubble Sort)基本思想:经过多次迭代,通过相邻元素之间的比较与交换,使值较小的元素逐步从后面移到前面,值较大的元素从前面移到后面。

假设数组的元素个数为 nn 个,则冒泡排序的算法步骤如下:

  1. 11 趟「冒泡」:对前 nn 个元素执行「冒泡」,从而使第 11 个值最大的元素放置在正确位置上。
    1. 先将序列中第 11 个元素与第 22 个元素进行比较,如果前者大于后者,则两者交换位置,否则不交换。
    2. 然后将第 22 个元素与第 33 个元素比较,如果前者大于后者,则两者交换位置,否则不交换。
    3. 依次类推,直到第 n1n - 1 个元素与第 nn 个元素比较(或交换)为止。
    4. 经过第 11 趟排序,使得 nn 个元素中第 ii 个值最大元素被安置在第 nn 个位置上。
  2. 22 趟「冒泡」:对前 n1n - 1 个元素执行「冒泡」,从而使第 22 个值最大的元素放置在正确位置上。
    1. 先将序列中第 11 个元素与第 22 个元素进行比较,若前者大于后者,则两者交换位置,否则不交换。
    2. 然后将第 22 个元素与第 33 个元素比较,若前者大于后者,则两者交换位置,否则不交换。
    3. 依次类推,直到第 n2n - 2 个元素与第 n1n - 1 个元素比较(或交换)为止。
    4. 经过第 22 趟排序,使得数组中第 22 个值最大元素被安置在第 nn 个位置上。
  3. 依次类推,重复上述「冒泡」过程,直到某一趟排序过程中不出现元素交换位置的动作,则排序结束。

思路 1:代码

class Solution:
    def bubbleSort(self, nums: [int]) -> [int]:
        # 第 i 趟「冒泡」
        for i in range(len(nums) - 1):
            flag = False    # 是否发生交换的标志位
            # 对数组未排序区间 [0, n - i - 1] 的元素执行「冒泡」
            for j in range(len(nums) - i - 1):
                # 相邻两个元素进行比较,如果前者大于后者,则交换位置
                if nums[j] > nums[j + 1]:
                    nums[j], nums[j + 1] = nums[j + 1], nums[j]
                    flag = True
            if not flag:    # 此趟遍历未交换任何元素,直接跳出
                break
        
        return nums
    
    def sortArray(self, nums: [int]) -> [int]:
        return self.bubbleSort(nums)

思路 1:复杂度分析

  • 时间复杂度O(n2)O(n^2)
  • 空间复杂度O(1)O(1)

思路 2:选择排序(超时)

选择排序(Selection Sort)基本思想:将数组分为两个区间,左侧为已排序区间,右侧为未排序区间。每趟从未排序区间中选择一个值最小的元素,放到已排序区间的末尾,从而将该元素划分到已排序区间。

假设数组的元素个数为 nn 个,则选择排序的算法步骤如下:

  1. 初始状态下,无已排序区间,未排序区间为 [0,n1][0, n - 1]
  2. 11 趟选择:
    1. 遍历未排序区间 [0,n1][0, n - 1],使用变量 minimin\underline{}i 记录区间中值最小的元素位置。
    2. minimin\underline{}i 与下标为 00 处的元素交换位置。如果下标为 00 处元素就是值最小的元素位置,则不用交换。
    3. 此时,[0,0][0, 0] 为已排序区间,[1,n1][1, n - 1](总共 n1n - 1 个元素)为未排序区间。
  3. 22 趟选择:
    1. 遍历未排序区间 [1,n1][1, n - 1],使用变量 minimin\underline{}i 记录区间中值最小的元素位置。
    2. minimin\underline{}i 与下标为 11 处的元素交换位置。如果下标为 11 处元素就是值最小的元素位置,则不用交换。
    3. 此时,[0,1][0, 1] 为已排序区间,[2,n1][2, n - 1](总共 n2n - 2 个元素)为未排序区间。
  4. 依次类推,对剩余未排序区间重复上述选择过程,直到所有元素都划分到已排序区间,排序结束。

思路 2:代码

class Solution:
    def selectionSort(self, nums: [int]) -> [int]:
        for i in range(len(nums) - 1):
            # 记录未排序区间中最小值的位置
            min_i = i
            for j in range(i + 1, len(nums)):
                if nums[j] < nums[min_i]:
                    min_i = j
            # 如果找到最小值的位置,将 i 位置上元素与最小值位置上的元素进行交换
            if i != min_i:
                nums[i], nums[min_i] = nums[min_i], nums[i]
        return nums

    def sortArray(self, nums: [int]) -> [int]:
        return self.selectionSort(nums)

思路 2:复杂度分析

  • 时间复杂度O(n2)O(n^2)
  • 空间复杂度O(1)O(1)

思路 3:插入排序(超时)

插入排序(Insertion Sort)基本思想:将数组分为两个区间,左侧为有序区间,右侧为无序区间。每趟从无序区间取出一个元素,然后将其插入到有序区间的适当位置。

假设数组的元素个数为 nn 个,则插入排序的算法步骤如下:

  1. 初始状态下,有序区间为 [0,0][0, 0],无序区间为 [1,n1][1, n - 1]
  2. 11 趟插入:
    1. 取出无序区间 [1,n1][1, n - 1] 中的第 11 个元素,即 nums[1]nums[1]
    2. 从右到左遍历有序区间中的元素,将比 nums[1]nums[1] 小的元素向后移动 11 位。
    3. 如果遇到大于或等于 nums[1]nums[1] 的元素时,说明找到了插入位置,将 nums[1]nums[1] 插入到该位置。
    4. 插入元素后有序区间变为 [0,1][0, 1],无序区间变为 [2,n1][2, n - 1]
  3. 22 趟插入:
    1. 取出无序区间 [2,n1][2, n - 1] 中的第 11 个元素,即 nums[2]nums[2]
    2. 从右到左遍历有序区间中的元素,将比 nums[2]nums[2] 小的元素向后移动 11 位。
    3. 如果遇到大于或等于 nums[2]nums[2] 的元素时,说明找到了插入位置,将 nums[2]nums[2] 插入到该位置。
    4. 插入元素后有序区间变为 [0,2][0, 2],无序区间变为 [3,n1][3, n - 1]
  4. 依次类推,对剩余无序区间中的元素重复上述插入过程,直到所有元素都插入到有序区间中,排序结束。

思路 3:代码

class Solution:
    def insertionSort(self, nums: [int]) -> [int]:
        # 遍历无序区间
        for i in range(1, len(nums)):
            temp = nums[i]
            j = i
            # 从右至左遍历有序区间
            while j > 0 and nums[j - 1] > temp:
                # 将有序区间中插入位置右侧的所有元素依次右移一位
                nums[j] = nums[j - 1]
                j -= 1
            # 将该元素插入到适当位置
            nums[j] = temp

        return nums

    def sortArray(self, nums: [int]) -> [int]:
        return self.insertionSort(nums)

思路 3:复杂度分析

  • 时间复杂度O(n2)O(n^2)
  • 空间复杂度O(1)O(1)

思路 4:希尔排序(通过)

希尔排序(Shell Sort)基本思想:将整个数组切按照一定的间隔取值划分为若干个子数组,每个子数组分别进行插入排序。然后逐渐缩小间隔进行下一轮划分子数组和对子数组进行插入排序。直至最后一轮排序间隔为 11,对整个数组进行插入排序。

假设数组的元素个数为 nn 个,则希尔排序的算法步骤如下:

  1. 确定一个元素间隔数 gapgap
  2. 将参加排序的数组按此间隔数从第 11 个元素开始一次分成若干个子数组,即分别将所有位置相隔为 gapgap 的元素视为一个子数组。
  3. 在各个子数组中采用某种排序算法(例如插入排序算法)进行排序。
  4. 减少间隔数,并重新将整个数组按新的间隔数分成若干个子数组,再分别对各个子数组进行排序。
  5. 依次类推,直到间隔数 gapgap 值为 11,最后进行一次排序,排序结束。

思路 4:代码

class Solution:
    def shellSort(self, nums: [int]) -> [int]:
        size = len(nums)
        gap = size // 2
        # 按照 gap 分组
        while gap > 0:
            # 对每组元素进行插入排序
            for i in range(gap, size):
                # temp 为每组中无序数组第 1 个元素
                temp = nums[i]
                j = i
                # 从右至左遍历每组中的有序数组元素
                while j >= gap and nums[j - gap] > temp:
                    # 将每组有序数组中插入位置右侧的元素依次在组中右移一位
                    nums[j] = nums[j - gap]
                    j -= gap
                # 将该元素插入到适当位置
                nums[j] = temp
            # 缩小 gap 间隔
            gap = gap // 2
        return nums

    def sortArray(self, nums: [int]) -> [int]:
        return self.shellSort(nums)

思路 4:复杂度分析

  • 时间复杂度:介于 O(n×logn)O(n \times \log n)O(n2)O(n^2) 之间。
  • 空间复杂度O(1)O(1)

思路 5:归并排序(通过)

归并排序(Merge Sort)基本思想:采用经典的分治策略,先递归地将当前数组平均分成两半,然后将有序数组两两合并,最终合并成一个有序数组。

假设数组的元素个数为 nn 个,则归并排序的算法步骤如下:

  1. 分解过程:先递归地将当前数组平均分成两半,直到子数组长度为 11
    1. 找到数组中心位置 midmid,从中心位置将数组分成左右两个子数组 leftnumsleft\underline{}numsrightnumsright\underline{}nums
    2. 对左右两个子数组 leftnumsleft\underline{}numsrightnumsright\underline{}nums 分别进行递归分解。
    3. 最终将数组分解为 nn 个长度均为 11 的有序子数组。
  2. 归并过程:从长度为 11 的有序子数组开始,依次将有序数组两两合并,直到合并成一个长度为 nn 的有序数组。
    1. 使用数组变量 numsnums 存放合并后的有序数组。
    2. 使用两个指针 leftileft\underline{}irightiright\underline{}i 分别指向两个有序子数组 leftnumsleft\underline{}numsrightnumsright\underline{}nums 的开始位置。
    3. 比较两个指针指向的元素,将两个有序子数组中较小元素依次存入到结果数组 numsnums 中,并将指针移动到下一位置。
    4. 重复步骤 33,直到某一指针到达子数组末尾。
    5. 将另一个子数组中的剩余元素存入到结果数组 numsnums 中。
    6. 返回合并后的有序数组 numsnums

思路 5:代码

class Solution:
    # 合并过程
    def merge(self, left_nums: [int], right_nums: [int]):
        nums = []
        left_i, right_i = 0, 0
        while left_i < len(left_nums) and right_i < len(right_nums):
            # 将两个有序子数组中较小元素依次插入到结果数组中
            if left_nums[left_i] < right_nums[right_i]:
                nums.append(left_nums[left_i])
                left_i += 1
            else:
                nums.append(right_nums[right_i])
                right_i += 1
        
        # 如果左子数组有剩余元素,则将其插入到结果数组中
        while left_i < len(left_nums):
            nums.append(left_nums[left_i])
            left_i += 1
        
        # 如果右子数组有剩余元素,则将其插入到结果数组中
        while right_i < len(right_nums):
            nums.append(right_nums[right_i])
            right_i += 1
        
        # 返回合并后的结果数组
        return nums

    # 分解过程
    def mergeSort(self, nums: [int]) -> [int]:
        # 数组元素个数小于等于 1 时,直接返回原数组
        if len(nums) <= 1:
            return nums
        
        mid = len(nums) // 2                        # 将数组从中间位置分为左右两个数组
        left_nums = self.mergeSort(nums[0: mid])    # 递归将左子数组进行分解和排序
        right_nums =  self.mergeSort(nums[mid:])    # 递归将右子数组进行分解和排序
        return self.merge(left_nums, right_nums)    # 把当前数组组中有序子数组逐层向上,进行两两合并

    def sortArray(self, nums: [int]) -> [int]:
        return self.mergeSort(nums)

思路 5:复杂度分析

  • 时间复杂度O(n×logn)O(n \times \log n)
  • 空间复杂度O(n)O(n)

思路 6:快速排序(通过)

快速排序(Quick Sort)基本思想:采用经典的分治策略,选择数组中某个元素作为基准数,通过一趟排序将数组分为独立的两个子数组,一个子数组中所有元素值都比基准数小,另一个子数组中所有元素值都比基准数大。然后再按照同样的方式递归的对两个子数组分别进行快速排序,以达到整个数组有序。

假设数组的元素个数为 nn 个,则快速排序的算法步骤如下:

  1. 哨兵划分:选取一个基准数,将数组中比基准数大的元素移动到基准数右侧,比他小的元素移动到基准数左侧。
    1. 从当前数组中找到一个基准数 pivotpivot(这里以当前数组第 11 个元素作为基准数,即 pivot=nums[low]pivot = nums[low])。
    2. 使用指针 ii 指向数组开始位置,指针 jj 指向数组末尾位置。
    3. 从右向左移动指针 jj,找到第 11 个小于基准值的元素。
    4. 从左向右移动指针 ii,找到第 11 个大于基准数的元素。
    5. 交换指针 ii、指针 jj 指向的两个元素位置。
    6. 重复第 353 \sim 5 步,直到指针 ii 和指针 jj 相遇时停止,最后将基准数放到两个子数组交界的位置上。
  2. 递归分解:完成哨兵划分之后,对划分好的左右子数组分别进行递归排序。
    1. 按照基准数的位置将数组拆分为左右两个子数组。
    2. 对每个子数组分别重复「哨兵划分」和「递归分解」,直到各个子数组只有 11 个元素,排序结束。

思路 6:代码

import random

class Solution:
    # 随机哨兵划分:从 nums[low: high + 1] 中随机挑选一个基准数,并进行移位排序
    def randomPartition(self, nums: [int], low: int, high: int) -> int:
        # 随机挑选一个基准数
        i = random.randint(low, high)
        # 将基准数与最低位互换
        nums[i], nums[low] = nums[low], nums[i]
        # 以最低位为基准数,然后将数组中比基准数大的元素移动到基准数右侧,比他小的元素移动到基准数左侧。最后将基准数放到正确位置上
        return self.partition(nums, low, high)
    
    # 哨兵划分:以第 1 位元素 nums[low] 为基准数,然后将比基准数小的元素移动到基准数左侧,将比基准数大的元素移动到基准数右侧,最后将基准数放到正确位置上
    def partition(self, nums: [int], low: int, high: int) -> int:        
        # 以第 1 位元素为基准数
        pivot = nums[low]
        
        i, j = low, high
        while i < j:
            # 从右向左找到第 1 个小于基准数的元素
            while i < j and nums[j] >= pivot:
                j -= 1
            # 从左向右找到第 1 个大于基准数的元素
            while i < j and nums[i] <= pivot:
                i += 1
            # 交换元素
            nums[i], nums[j] = nums[j], nums[i]
        
        # 将基准数放到正确位置上
        nums[j], nums[low] = nums[low], nums[j]
        return j

    def quickSort(self, nums: [int], low: int, high: int) -> [int]:
        if low < high:
            # 按照基准数的位置,将数组划分为左右两个子数组
            pivot_i = self.partition(nums, low, high)
            # 对左右两个子数组分别进行递归快速排序
            self.quickSort(nums, low, pivot_i - 1)
            self.quickSort(nums, pivot_i + 1, high)

        return nums

    def sortArray(self, nums: [int]) -> [int]:
        return self.quickSort(nums, 0, len(nums) - 1)

思路 6:复杂度分析

  • 时间复杂度O(n×logn)O(n \times \log n)
  • 空间复杂度O(n)O(n)

思路 7:堆排序(通过)

堆排序(Heap sort)基本思想:借用「堆结构」所设计的排序算法。将数组转化为大顶堆,重复从大顶堆中取出数值最大的节点,并让剩余的堆结构继续维持大顶堆性质。

假设数组的元素个数为 nn 个,则堆排序的算法步骤如下:

  1. 构建初始大顶堆

    1. 定义一个数组实现的堆结构,将原始数组的元素依次存入堆结构的数组中(初始顺序不变)。
    2. 从数组的中间位置开始,从右至左,依次通过「下移调整」将数组转换为一个大顶堆。
  2. 交换元素,调整堆

    1. 交换堆顶元素(第 11 个元素)与末尾(最后 11 个元素)的位置,交换完成后,堆的长度减 11
    2. 交换元素之后,由于堆顶元素发生了改变,需要从根节点开始,对当前堆进行「下移调整」,使其保持堆的特性。
  3. 重复交换和调整堆

    1. 重复第 22 步,直到堆的大小为 11 时,此时大顶堆的数组已经完全有序。

思路 7:代码

class Solution:
    # 调整为大顶堆
    def heapify(self, arr, index, end):
        left = index * 2 + 1
        right = left + 1
        while left <= end:
            # 当前节点为非叶子节点
            max_index = index
            if arr[left] > arr[max_index]:
                max_index = left
            if right <= end and arr[right] > arr[max_index]:
                max_index = right
            if index == max_index:
                # 如果不用交换,则说明已经交换结束
                break
            arr[index], arr[max_index] = arr[max_index], arr[index]
            # 继续调整子树
            index = max_index
            left = index * 2 + 1
            right = left + 1

    # 初始化大顶堆
    def buildMaxHeap(self, arr):
        size = len(arr)
        # (size-2) // 2 是最后一个非叶节点,叶节点不用调整
        for i in range((size - 2) // 2, -1, -1):
            self.heapify(arr, i, size - 1)
        return arr

    # 升序堆排序,思路如下:
    # 1. 先建立大顶堆
    # 2. 让堆顶最大元素与最后一个交换,然后调整第一个元素到倒数第二个元素,这一步获取最大值
    # 3. 再交换堆顶元素与倒数第二个元素,然后调整第一个元素到倒数第三个元素,这一步获取第二大值
    # 4. 以此类推,直到最后一个元素交换之后完毕。
    def maxHeapSort(self, arr):
        self.buildMaxHeap(arr)
        size = len(arr)
        for i in range(size):
            arr[0], arr[size-i-1] = arr[size-i-1], arr[0]
            self.heapify(arr, 0, size-i-2)
        return arr

    def sortArray(self, nums: List[int]) -> List[int]:
        return self.maxHeapSort(nums)

思路 7:复杂度分析

  • 时间复杂度O(n×logn)O(n \times \log n)
  • 空间复杂度O(1)O(1)

思路 8:计数排序(通过)

计数排序(Counting Sort)基本思想:通过统计数组中每个元素在数组中出现的次数,根据这些统计信息将数组元素有序的放置到正确位置,从而达到排序的目的。

假设数组的元素个数为 nn 个,则计数排序的算法步骤如下:

  1. 计算排序范围:遍历数组,找出待排序序列中最大值元素 numsmaxnums\underline{}max 和最小值元素 numsminnums\underline{}min,计算出排序范围为 numsmaxnumsmin+1nums\underline{}max - nums\underline{}min + 1

  2. 定义计数数组:定义一个大小为排序范围的计数数组 countscounts,用于统计每个元素的出现次数。其中:

    1. 数组的索引值 numnumsminnum - nums\underline{}min 表示元素的值为 numnum
    2. 数组的值 counts[numnumsmin]counts[num - nums\underline{}min] 表示元素 numnum 的出现次数。
  3. 对数组元素进行计数统计:遍历待排序数组 numsnums,对每个元素在计数数组中进行计数,即将待排序数组中「每个元素值减去最小值」作为索引,将「对计数数组中的值」加 11,即令 counts[numnumsmin]counts[num - nums\underline{}min]11

  4. 生成累积计数数组:从 countscounts 中的第 11 个元素开始,每一项累家前一项和。此时 counts[numnumsmin]counts[num - nums\underline{}min] 表示值为 numnum 的元素在排序数组中最后一次出现的位置。

  5. 逆序填充目标数组:逆序遍历数组 numsnums,将每个元素 numnum 填入正确位置。

  6. 将其填充到结果数组 resres 的索引 counts[numnumsmin]counts[num - nums\underline{}min] 处。

  7. 放入后,令累积计数数组中对应索引减 11,从而得到下个元素 numnum 的放置位置。

思路 8:代码

class Solution:
    def countingSort(self, nums: [int]) -> [int]:
        # 计算待排序数组中最大值元素 nums_max 和最小值元素 nums_min
        nums_min, nums_max = min(nums), max(nums)
        # 定义计数数组 counts,大小为 最大值元素 - 最小值元素 + 1
        size = nums_max - nums_min + 1
        counts = [0 for _ in range(size)]
        
        # 统计值为 num 的元素出现的次数
        for num in nums:
            counts[num - nums_min] += 1
        
        # 生成累积计数数组
        for i in range(1, size):
            counts[i] += counts[i - 1]

        # 反向填充目标数组
        res = [0 for _ in range(len(nums))]
        for i in range(len(nums) - 1, -1, -1):
            num = nums[i]
            # 根据累积计数数组,将 num 放在数组对应位置
            res[counts[num - nums_min] - 1] = num
            # 将 num 的对应放置位置减 1,从而得到下个元素 num 的放置位置
            counts[nums[i] - nums_min] -= 1

        return res

    def sortArray(self, nums: [int]) -> [int]:
        return self.countingSort(nums)

思路 8:复杂度分析

  • 时间复杂度O(n+k)O(n + k)。其中 kk 代表待排序序列的值域。
  • 空间复杂度O(k)O(k)。其中 kk 代表待排序序列的值域。

思路 9:桶排序(通过)

桶排序(Bucket Sort)基本思想:将待排序数组中的元素分散到若干个「桶」中,然后对每个桶中的元素再进行单独排序。

假设数组的元素个数为 nn 个,则桶排序的算法步骤如下:

  1. 确定桶的数量:根据待排序数组的值域范围,将数组划分为 kk 个桶,每个桶可以看做是一个范围区间。
  2. 分配元素:遍历待排序数组元素,将每个元素根据大小分配到对应的桶中。
  3. 对每个桶进行排序:对每个非空桶内的元素单独排序(使用插入排序、归并排序、快排排序等算法)。
  4. 合并桶内元素:将排好序的各个桶中的元素按照区间顺序依次合并起来,形成一个完整的有序数组。

思路 9:代码

class Solution:
    def insertionSort(self, nums: [int]) -> [int]:
        # 遍历无序区间
        for i in range(1, len(nums)):
            temp = nums[i]
            j = i
            # 从右至左遍历有序区间
            while j > 0 and nums[j - 1] > temp:
                # 将有序区间中插入位置右侧的元素依次右移一位
                nums[j] = nums[j - 1]
                j -= 1
            # 将该元素插入到适当位置
            nums[j] = temp
            
        return nums

    def bucketSort(self,  nums: [int], bucket_size=5) -> [int]:
        # 计算待排序序列中最大值元素 nums_max、最小值元素 nums_min
        nums_min, nums_max = min(nums), max(nums)
        # 定义桶的个数为 (最大值元素 - 最小值元素) // 每个桶的大小 + 1
        bucket_count = (nums_max - nums_min) // bucket_size + 1
        # 定义桶数组 buckets
        buckets = [[] for _ in range(bucket_count)]

        # 遍历待排序数组元素,将每个元素根据大小分配到对应的桶中
        for num in nums:
            buckets[(num - nums_min) // bucket_size].append(num)

        # 对每个非空桶内的元素单独排序,排序之后,按照区间顺序依次合并到 res 数组中
        res = []
        for bucket in buckets:
            self.insertionSort(bucket)
            res.extend(bucket)
        
        # 返回结果数组
        return res

    def sortArray(self, nums: [int]) -> [int]:
        return self.bucketSort(nums)

思路 9:复杂度分析

  • 时间复杂度O(n)O(n)
  • 空间复杂度O(n+m)O(n + m)mm 为桶的个数。

思路 10:基数排序(提交解答错误,普通基数排序只适合非负数)

基数排序(Radix Sort)基本思想:将整数按位数切割成不同的数字,然后从低位开始,依次到高位,逐位进行排序,从而达到排序的目的。

我们以最低位优先法为例,讲解一下基数排序的算法步骤。

  1. 确定排序的最大位数:遍历数组元素,获取数组最大值元素,并取得对应位数。
  2. 从最低位(个位)开始,到最高位为止,逐位对每一位进行排序
    1. 定义一个长度为 1010 的桶数组 bucketsbuckets,每个桶分别代表 090 \sim 9 中的 11 个数字。
    2. 按照每个元素当前位上的数字,将元素放入对应数字的桶中。
    3. 清空原始数组,然后按照桶的顺序依次取出对应元素,重新加入到原始数组中。

思路 10:代码

class Solution:
    def radixSort(self, nums: [int]) -> [int]:
        # 桶的大小为所有元素的最大位数
        size = len(str(max(nums)))
        
        # 从最低位(个位)开始,逐位遍历每一位
        for i in range(size):
            # 定义长度为 10 的桶数组 buckets,每个桶分别代表 0 ~ 9 中的 1 个数字。
            buckets = [[] for _ in range(10)]
            # 遍历数组元素,按照每个元素当前位上的数字,将元素放入对应数字的桶中。
            for num in nums:
                buckets[num // (10 ** i) % 10].append(num)
            # 清空原始数组
            nums.clear()
            # 按照桶的顺序依次取出对应元素,重新加入到原始数组中。
            for bucket in buckets:
                for num in bucket:
                    nums.append(num)
                    
        # 完成排序,返回结果数组
        return nums
    
    def sortArray(self, nums: [int]) -> [int]:
        return self.radixSort(nums)

思路 10:复杂度分析

  • 时间复杂度O(n×k)O(n \times k)。其中 nn 是待排序元素的个数,kk 是数字位数。kk 的大小取决于数字位的选择(十进制位、二进制位)和待排序元素所属数据类型全集的大小。
  • 空间复杂度O(n+k)O(n + k)