算法随笔 — 排序算法 — 基数/拓扑排序

末蓝、 2022-09-09 04:48 212阅读 0赞

## 基数排序原理 ##

假设现有一组待排序的数据

[13, 21, 11, 32, 31, 22, 21]

首先对这组数据的个位数进行计数

![基数排序个位数][01da6360406a42aaa00f5c55a964672e.png]

接着对原数组进行倒叙扫描，

首先是21, 21的个位数是1，因此21放在第4个“1”上；其次是22, 22的个位数是2，因此22放在第二个“2”上，后面的以此类推，最终结果如图所示：

![基数排序个位排序结果][91c2bbf4095342d9a0837fbf7b16f9ce.png]  
接下来，以个位数的排序结果为基础，重复上述步骤。

首先统计十位数的计数

然后对该结果进行前缀和的求和，得到的结果是 `[0, 2, 5, 7]`。这里的数字表示不同十位数计数的最后一个坐标加1，比如说按顺序排好的数组，十位数为1的数字排在前两个

接下来是对个位排序数组进行倒序扫描并插入到对应位置，得到的结果如下：  
![基数排序十位数结果][c38e9fdaa34d414fbadd872fb987005c.png]  
至此，该数据已经排序完毕

具体实现如下

function radixSort(data: number[], n: number) { 
      const counter = (new Array(65536) as any).fill(0),
            temp = (new Array(n) as any).fill(0)
      //* 低16位处理
      data.forEach(num => counter[num & 0xffff]++)
      for (let i = 1; i < 65536; i++) counter[i] += counter[i - 1]
      for (let i = n - 1; i >= 0; i--) temp[--counter[data[i] & 0xffff]] = data[i]
      //* 重置
      counter.fill(0)
      //* 高16位处理
      data.forEach(num => counter[(num & 0xffff0000) >> 16]++)
      for (let i = 1; i < 65536; i++) counter[i] += counter[i - 1]
      for (let i = n - 1; i >= 0; i--) data[--counter[(data[i] & 0xffff0000) >> 16]] = temp[i]
    }

在这里的实现中，低16位可以当作示例中的个位数，高16位可以当作示例中的十位数。

--------------------

## 基数排序习题 ##

> ### leetCode 164 最大间距 ###

![164题目][164]  
这道题要想在线性时间复杂度和空间复杂度的条件下解决此问题，用基数排序是最合适的

我们只要先排序然后遍历数组得到最大差值就行了

function radixSort(nums: number[]) { 
      const counter = new Array(65536).fill(0), temp = new Array(nums.length).fill(0)
      //* 低16位排序
      nums.forEach(num => counter[num & 0xffff]++)
      for (let i = 1; i < 65536; i++) counter[i] += counter[i - 1]
      for (let i = nums.length - 1; i >= 0; i--) temp[--counter[nums[i] & 0xffff]] = nums[i]
      //* 重置
      counter.fill(0)
      //* 高16位排序
      temp.forEach(num => counter[(num & 0xffff0000) >> 16]++)
      for (let i = 1; i < 65536; i++) counter[i] += counter[i - 1]
      for (let i = nums.length - 1; i >= 0; i--) nums[--counter[(temp[i] & 0xffff0000) >> 16]] = temp[i]
    }
    
    function maximumGap(nums: number[]): number { 
      let res = 0
      radixSort(nums)
      for (let i = 1; i < nums.length; i++) res = Math.max(nums[i] - nums[i - 1], res)
      return res
    }

![164结果][164 1]

> ### leetCode 274 H指数 ###

![274题目][274]  
这道题同样先遍历，然后从大到小遍历

![274结果][274 1]  
当然也有一种偷懒的方法，在最后计数的原理是一样的，就是排序的时候用原生的排序方法

function hIndex(citations: number[]): number { 
      let h = 1
      citations.sort((a, b) => b - a).every(num => { 
        if (num >= h) { 
          h++
          return true
        }
        return false
      })
      return h - 1
    }

> ### leetCode 1122 数组的相对排序 ###

![1122题目][1122]  
这道题用到了一部分基数排序中按位插入的道理

function relativeSortArray(arr1: number[], arr2: number[]): number[] { 
      const counter = new Array(1005).fill(0)
      let k = 0
      arr1.forEach(num => counter[num]++)
      arr2.forEach(num => { 
        while (counter[num]--) arr1[k++] = num
      })
      counter.forEach((cnt, num) => { 
        if (cnt <= 0) return
        while (cnt--) arr1[k++] = num
      })
      return arr1
    }

![1122结果][1122 1]

--------------------

## 拓扑排序原理 ##

![拓扑排序题目][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5pyA5byx55qE5pWZ5Li7_size_13_color_FFFFFF_t_70_g_se_x_16]  
在这个图中，可能的顺序有

A E B C F D
    E A C F B D
    ......

通过观察，我们可以用队列维护顺序，同时需要记录每个节点的入度(前置节点)，只有入度为0的节点才可将其入队，因此每出队一节点就将该节点的所有下一节点的入度减1，如果下一节点的入度为0就将该节点入队

--------------------

## 拓扑排序习题 ##

> ### leetCode 207 课程表 ###

![207题目][207]

function canFinish(numCourses: number, prerequisites: number[][]): boolean { 
      const indegrees = new Array(numCourses).fill(0),
        courseMap: { [key: number]: number[]} = { },
        q: number[] = []
      let courses = 0, // 能上的课
        course = -1
      prerequisites.forEach(([cur, pre]) => { 
        if (!courseMap[pre]) courseMap[pre] = []
        indegrees[cur]++
        courseMap[pre].push(cur)
      })
      indegrees.forEach((indegree, course) => !indegree && q.push(course))
      while (q.length) { 
        courses++
        course = q.shift() as number
        courseMap[course]?.forEach(c => { 
          if (!(--indegrees[c])) q.push(c)
        })
      }
      return courses === numCourses
    }

![207结果][207 1]

> ### leetCode 210 课程表II ###

![210题目][210]

function findOrder(numCourses: number, prerequisites: number[][]): number[] { 
      const indegrees = new Array(numCourses).fill(0), courseMap: { [key: number]: number[]} = { },
        ret: number[] = [], q: number[] = []
      let course = -1
      prerequisites.forEach(([cur, pre]) => { 
        if (!courseMap[pre]) courseMap[pre] = []
        indegrees[cur]++
        courseMap[pre].push(cur)
      })
      indegrees.forEach((indegree, course) => !indegree && q.push(course))
      while (q.length) { 
        course = q.shift() as number
        ret.push(course)
        courseMap[course]?.forEach(c => { 
          if (!(--indegrees[c])) q.push(c)
        })
      }
      return ret.length === numCourses ? ret : []
    }

![210结果][210 1]

[01da6360406a42aaa00f5c55a964672e.png]: /images/20220829/88e54fa31e46463db148784e0720211a.png
[91c2bbf4095342d9a0837fbf7b16f9ce.png]: /images/20220829/5f3cb490ff6040cca05fddd946f8e22a.png
[c38e9fdaa34d414fbadd872fb987005c.png]: /images/20220829/209a139ab450432fa9daff3c9e1817af.png
[164]: /images/20220829/f63007e6ccb84e8d9e5b251f7d0c9dab.png
[164 1]: /images/20220829/cdee0660106544d98d9ea98e19cd47cd.png
[274]: /images/20220829/ef69dfbab3794dd0845cecfb23314b3e.png
[274 1]: /images/20220829/fbbcc95f9c034dfcae50803bf892f12b.png
[1122]: /images/20220829/b4b5cd0685c04040bea3fa3d1708121f.png
[1122 1]: /images/20220829/bcc0b1bfb60842359c85ca3f12ec7987.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5pyA5byx55qE5pWZ5Li7_size_13_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/f7364c39b57c4bba84899f24dbb3ca8d.png
[207]: /images/20220829/f54181d485db4361b6512669b66bb0b5.png
[207 1]: /images/20220829/80ecba11df1f419891de286294095b71.png
[210]: /images/20220829/436a6780d6144a33aeda61d8a1e00d26.png
[210 1]: /images/20220829/48d03b3c662c473bbd72eeb3f802b6e4.png