计数排序的进阶应用：对多维整数数组按指定维度排序
字数 3463 2025-12-08 02:39:11

计数排序的进阶应用：对多维整数数组按指定维度排序

问题描述

我们有一个二维整数数组 arr，其中包含 n 个元素，每个元素是一个一维数组（我们称其为“元组”），长度为 m（即 arr 是一个 n x m 的矩阵）。我们的目标是按照其中某一列（称为关键列 keyIndex，0 <= keyIndex < m）的值，对整个二维数组进行稳定排序。所谓的稳定排序，是指如果两个元组在关键列上的值相同，那么它们在排序后输出中的相对顺序应与输入中的相对顺序保持一致。同时，要求算法的时间复杂度为 O(n + k)，其中 k 是关键列中可能取值的范围（最大值与最小值之差加1），且空间复杂度在可接受的范围内。

示例：
输入：
arr = [[2, 5, 1], [1, 3, 9], [2, 3, 8], [1, 4, 7]]
keyIndex = 0 （即按第一列排序）

输出（稳定排序后）：
[[1, 3, 9], [1, 4, 7], [2, 5, 1], [2, 3, 8]]

解释：
首先按第一列的值排序。第一列的值有 1 和 2。
所有第一列为 1 的元组 ([1,3,9] 和 [1,4,7]) 保持原有顺序排在前。
所有第一列为 2 的元组 ([2,5,1] 和 [2,3,8]) 保持原有顺序排在后。

解题过程

步骤1：理解核心挑战与计数排序的特性

此题的关键在于，我们不仅要排序，还要保持稳定排序的特性，并且要利用计数排序线性时间复杂度的优势。标准的一维计数排序可以做到稳定排序，其稳定性的实现通常依赖于一个反向遍历和位置计数数组。现在我们需要将这种能力扩展到对二维数组的某一列进行排序，同时移动整个元组。

步骤2：确定关键列的取值范围

计数排序要求知道排序键（即关键列的值）的范围。首先，我们需要遍历所有元组的 keyIndex 列，找到其中的最小值 minVal 和最大值 maxVal。
对于示例：
关键列索引 keyIndex = 0。
遍历 arr 的第一列：值有 2, 1, 2, 1。
所以，minVal = 1, maxVal = 2。
值的范围 rangeVal = maxVal - minVal + 1 = 2 - 1 + 1 = 2。这个 rangeVal 就是计数数组的长度 k。

步骤3：构建计数数组并统计频率

创建一个长度为 rangeVal 的计数数组 count，所有元素初始化为0。然后，再次遍历 arr 的每个元组，对于每个元组，计算其关键列的值 val，然后通过 val - minVal 映射到 count 数组的索引，并将该索引位置的计数值加1。
对于示例：
minVal = 1。
遍历：

  • [2,5,1]: val = 2, index = 2-1=1, count[1]++ -> count = [0, 1]
  • [1,3,9]: val = 1, index = 1-1=0, count[0]++ -> count = [1, 1]
  • [2,3,8]: val = 2, index = 1, count[1]++ -> count = [1, 2]
  • [1,4,7]: val = 1, index = 0, count[0]++ -> count = [2, 2]
    最终 count = [2, 2]，表示关键列值为 1（映射到索引0）的元组有2个，值为 2（映射到索引1）的元组有2个。

步骤4：将计数数组转换为位置索引数组（前缀和）

为了使排序稳定，我们需要知道每个值（或值范围）的元组在输出数组中的正确起始位置。我们将 count 数组转换为前缀和数组，count[i] 将表示关键列值小于等于 (i + minVal) 的元组的数量（更准确地说，是最后一个这样的元素在输出数组中的下一个位置的索引）。
转换方法：从第二个元素开始（索引1），将当前元素的值加上前一个元素的值。
对于示例：
初始 count = [2, 2]。
第一步：count[1] = count[1] + count[0] = 2 + 2 = 4。此时 count = [2, 4]。
解释：count[0]=2 表示值小于等于 1 的元组有2个。count[1]=4 表示值小于等于 2 的元组总共有4个（即所有元组）。

步骤5：反向遍历原数组，放置元组到输出数组

这是保证稳定性的关键步骤。我们创建一个和输入数组 arr 大小相同的输出数组 output（也是一个二维数组）。
然后，我们从后向前遍历原始数组 arr。对于遍历到的每个元组：

  1. 获取其关键列的值 val。
  2. 计算其在计数数组中的索引 idx = val - minVal。
  3. 此时 count[idx] 的值表示：下一个关键列值等于 val 的元组应该放置在输出数组中的位置（索引）。由于我们从后向前遍历，可以保证相同关键列值的元组，后出现的会放在更靠后的位置（即 count[idx] - 1），从而保持了原有顺序。
  4. 将当前元组复制到 output[count[idx] - 1]。
  5. 将 count[idx] 的值减1，为下一个具有相同关键列值的元组腾出位置。

对于示例：
初始化 output 为大小为4的空数组。
count 当前为 [2, 4]。
从后向前遍历 arr：

  1. 最后一个元组 [1,4,7]：val=1, idx=0。count[0]=2。所以放置位置是 output[2-1] = output[1]。放置后，count[0] 减1变为 1。output 现在：[空, [1,4,7], 空, 空]。
  2. 倒数第二个元组 [2,3,8]：val=2, idx=1。count[1]=4。放置到 output[4-1]=output[3]。count[1] 减1变为 3。output：[空, [1,4,7], 空, [2,3,8]]。
  3. 倒数第三个元组 [1,3,9]：val=1, idx=0。count[0]=1。放置到 output[1-1]=output[0]。count[0] 减1变为 0。output：[[1,3,9], [1,4,7], 空, [2,3,8]]。
  4. 倒数第四个元组 [2,5,1]：val=2, idx=1。count[1]=3。放置到 output[3-1]=output[2]。count[1] 减1变为 2。output：[[1,3,9], [1,4,7], [2,5,1], [2,3,8]]。

遍历结束，output 即为最终排序结果。可见，对于关键列值相同的元组（如两个 1 和两个 2），它们的相对顺序得到了保持。

步骤6：返回结果（或原地修改）

根据题目要求，我们可以返回新的 output 数组。如果要求原地排序，则需要将 output 的内容逐个复制回原数组 arr。在本问题的设定中，我们通常返回新的已排序数组。

算法分析

  • 时间复杂度：O(n + m + k)。其中 n 是元组数量，m 是每个元组的长度（在遍历关键列和复制元组时涉及），k 是关键列值的范围 (maxVal-minVal+1)。由于我们通常认为 m 是常数（或与 n 无关），所以主要复杂度为 O(n + k)。
  • 空间复杂度：O(n + k)。需要额外的 output 数组（O(n)）和 count 数组（O(k)）。
  • 稳定性：通过反向遍历和使用前缀和计数数组，算法是稳定的。

总结与拓展

这个方法本质上是将一维计数排序直接应用于一个“投影”出来的关键列，并通过在移动数据时移动整个元组，从而实现对多维数组按列排序。它高效且稳定。如果需要对多个列进行排序（例如，先按第一列，第一列相同再按第二列），则可以结合基数排序的思想，从最不重要的列到最重要的列，多次调用这个稳定的计数排序过程。

计数排序的进阶应用：对多维整数数组按指定维度排序 问题描述 我们有一个二维整数数组 arr ，其中包含 n 个元素，每个元素是一个一维数组（我们称其为“元组”），长度为 m （即 arr 是一个 n x m 的矩阵）。我们的目标是按照其中某一列（称为关键列 keyIndex ， 0 <= keyIndex < m ）的值，对整个二维数组进行 稳定排序 。所谓的稳定排序，是指如果两个元组在关键列上的值相同，那么它们在排序后输出中的相对顺序应与输入中的相对顺序保持一致。同时，要求算法的时间复杂度为 O(n + k)，其中 k 是关键列中可能取值的范围（最大值与最小值之差加1），且空间复杂度在可接受的范围内。 示例： 输入： arr = [[2, 5, 1], [1, 3, 9], [2, 3, 8], [1, 4, 7]] keyIndex = 0 （即按第一列排序） 输出（稳定排序后）： [[1, 3, 9], [1, 4, 7], [2, 5, 1], [2, 3, 8]] 解释： 首先按第一列的值排序。第一列的值有 1 和 2 。 所有第一列为 1 的元组 ( [1,3,9] 和 [1,4,7] ) 保持原有顺序排在前。 所有第一列为 2 的元组 ( [2,5,1] 和 [2,3,8] ) 保持原有顺序排在后。 解题过程 步骤1：理解核心挑战与计数排序的特性 此题的关键在于，我们不仅要排序，还要保持稳定排序的特性，并且要利用计数排序线性时间复杂度的优势。标准的一维计数排序可以做到稳定排序，其稳定性的实现通常依赖于一个反向遍历和位置计数数组。现在我们需要将这种能力扩展到对二维数组的某一列进行排序，同时移动整个元组。 步骤2：确定关键列的取值范围 计数排序要求知道排序键（即关键列的值）的范围。首先，我们需要遍历所有元组的 keyIndex 列，找到其中的最小值 minVal 和最大值 maxVal 。 对于示例： 关键列索引 keyIndex = 0 。 遍历 arr 的第一列：值有 2, 1, 2, 1 。 所以， minVal = 1 , maxVal = 2 。 值的范围 rangeVal = maxVal - minVal + 1 = 2 - 1 + 1 = 2 。这个 rangeVal 就是计数数组的长度 k 。 步骤3：构建计数数组并统计频率 创建一个长度为 rangeVal 的计数数组 count ，所有元素初始化为0。然后，再次遍历 arr 的每个元组，对于每个元组，计算其关键列的值 val ，然后通过 val - minVal 映射到 count 数组的索引，并将该索引位置的计数值加1。 对于示例： minVal = 1 。 遍历： [2,5,1] : val = 2 , index = 2-1=1 , count[1]++ -> count = [0, 1] [1,3,9] : val = 1 , index = 1-1=0 , count[0]++ -> count = [1, 1] [2,3,8] : val = 2 , index = 1 , count[1]++ -> count = [1, 2] [1,4,7] : val = 1 , index = 0 , count[0]++ -> count = [2, 2] 最终 count = [2, 2] ，表示关键列值为 1 （映射到索引0）的元组有2个，值为 2 （映射到索引1）的元组有2个。 步骤4：将计数数组转换为位置索引数组（前缀和） 为了使排序稳定，我们需要知道每个值（或值范围）的元组在输出数组中的正确起始位置。我们将 count 数组转换为前缀和数组， count[i] 将表示关键列值小于等于 (i + minVal) 的元组的数量（更准确地说，是最后一个这样的元素在输出数组中的下一个位置的索引）。 转换方法：从第二个元素开始（索引1），将当前元素的值加上前一个元素的值。 对于示例： 初始 count = [2, 2] 。 第一步： count[1] = count[1] + count[0] = 2 + 2 = 4 。此时 count = [2, 4] 。 解释： count[0]=2 表示值小于等于 1 的元组有2个。 count[1]=4 表示值小于等于 2 的元组总共有4个（即所有元组）。 步骤5：反向遍历原数组，放置元组到输出数组 这是保证稳定性的关键步骤。我们创建一个和输入数组 arr 大小相同的输出数组 output （也是一个二维数组）。 然后，我们 从后向前 遍历原始数组 arr 。对于遍历到的每个元组： 获取其关键列的值 val 。 计算其在计数数组中的索引 idx = val - minVal 。 此时 count[idx] 的值表示：下一个关键列值等于 val 的元组应该放置在输出数组中的位置（索引）。由于我们从后向前遍历，可以保证相同关键列值的元组，后出现的会放在更靠后的位置（即 count[idx] - 1 ），从而保持了原有顺序。 将当前元组复制到 output[count[idx] - 1] 。 将 count[idx] 的值减1，为下一个具有相同关键列值的元组腾出位置。 对于示例： 初始化 output 为大小为4的空数组。 count 当前为 [2, 4] 。 从后向前遍历 arr ： 最后一个元组 [1,4,7] ： val=1 , idx=0 。 count[0]=2 。所以放置位置是 output[2-1] = output[1] 。放置后， count[0] 减1变为 1 。 output 现在： [空, [1,4,7], 空, 空] 。 倒数第二个元组 [2,3,8] ： val=2 , idx=1 。 count[1]=4 。放置到 output[4-1]=output[3] 。 count[1] 减1变为 3 。 output ： [空, [1,4,7], 空, [2,3,8]] 。 倒数第三个元组 [1,3,9] ： val=1 , idx=0 。 count[0]=1 。放置到 output[1-1]=output[0] 。 count[0] 减1变为 0 。 output ： [[1,3,9], [1,4,7], 空, [2,3,8]] 。 倒数第四个元组 [2,5,1] ： val=2 , idx=1 。 count[1]=3 。放置到 output[3-1]=output[2] 。 count[1] 减1变为 2 。 output ： [[1,3,9], [1,4,7], [2,5,1], [2,3,8]] 。 遍历结束， output 即为最终排序结果。可见，对于关键列值相同的元组（如两个 1 和两个 2 ），它们的相对顺序得到了保持。 步骤6：返回结果（或原地修改） 根据题目要求，我们可以返回新的 output 数组。如果要求原地排序，则需要将 output 的内容逐个复制回原数组 arr 。在本问题的设定中，我们通常返回新的已排序数组。 算法分析 时间复杂度 ：O(n + m + k)。其中 n 是元组数量，m 是每个元组的长度（在遍历关键列和复制元组时涉及），k 是关键列值的范围 ( maxVal-minVal+1 )。由于我们通常认为 m 是常数（或与 n 无关），所以主要复杂度为 O(n + k)。 空间复杂度 ：O(n + k)。需要额外的 output 数组（O(n)）和 count 数组（O(k)）。 稳定性 ：通过反向遍历和使用前缀和计数数组，算法是稳定的。 总结与拓展 这个方法本质上是将一维计数排序直接应用于一个“投影”出来的关键列，并通过在移动数据时移动整个元组，从而实现对多维数组按列排序。它高效且稳定。如果需要对多个列进行排序（例如，先按第一列，第一列相同再按第二列），则可以结合基数排序的思想，从最不重要的列到最重要的列，多次调用这个稳定的计数排序过程。