如何return排序后的索引进行计数排序？

Question

我想 return 从下面的计数排序算法中为 x 数组排序索引，它一定很简单，但我不知道该怎么做！有人可以指导我如何在 Matlab 或 Golang 中或以下算法的任何 idomatic c 风格演示中做到这一点吗？非常感谢。

x=[6 2 5 3 2 2 ];
MAX=10;
n = length(x);
C = zeros(MAX,1); // intialize counting array 
for j = 1:n
    C(x(j)) = C(x(j)) + 1;
end

z=1;
sorted_x = zeros(n,1);  // empty array -container for sorted elements
for j = 1:n;
   while ( C(j) >0)
      sorted_x(z) = j;
      z=z+1;
      C(j) = C(j) - 1;
   end
end

上面的代码 returns sorted_x=[2 2 2 3 5 6] 但我想将其修改为 return sorted_indices=[2 5 6 4 3 1]

谢谢

Answer 1

您可以使用 map 来存储索引 -

package main
import "fmt"

func main(){
    nums := [6]int{6, 2, 5, 3, 2, 2}
    count := make(map[int][]int)
    for i, v := range nums {
        count[v] = append(count[v], i+1)
    }
    output := []int{}
    for i := 0; i < 10; i++ {
        output = append(output, count[i]...)
    }
    for i := 0; i < len(output); i++ {
        fmt.Printf("%d ", nums[output[i]-1])
    }
    fmt.Println()
    fmt.Println("The indices are:")
    fmt.Println(output)
}

输出 -

2 2 2 3 5 6 
The indices are:
[2 5 6 4 3 1]

Answer 2

在 matlab 中，sort 函数的第二个输出值是索引。简单地试试这个：

[sorted, s_ind] = sort(x);

Answer 3

例如，使用 Go sort 包，

package main

import (
    "fmt"
    "sort"
)

type AX struct{ A, X []int }

func (ax AX) Len() int {
    return len(ax.A)
}
func (ax AX) Swap(i, j int) {
    ax.A[i], ax.A[j] = ax.A[j], ax.A[i]
    ax.X[i], ax.X[j] = ax.X[j], ax.X[i]
}
func (ax AX) Less(i, j int) bool {
    return ax.A[i] < ax.A[j]
}

func sortAX(a []int) (x []int) {
    x = make([]int, len(a))
    for i := range x {
        x[i] = i
    }
    sort.Stable(AX{A: a, X: x})
    return x
}

func main() {
    a := []int{6, 2, 5, 3, 2, 2}
    fmt.Println("a:", a)
    x := sortAX(a)
    fmt.Println("a:", a)
    fmt.Println("x:", x)
}

输出（Go 索引从 0 开始）：

a: [6 2 5 3 2 2]
a: [2 2 2 3 5 6]
x: [1 4 5 3 2 0]

参考文献：

Go: Package sort

如何return排序后的索引进行计数排序？

How to return the sorted indices for Counting Sort?

sorting

algorithm

counting-sort