如何返回排序索引以计数排序

Question

我想从下面的计数排序算法返回x数组的排序索引，这一定很简单，但是我不知道该怎么做！有人可以指导我如何在MATLAB或GOLANG或以下算法的任何IDOMIC 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

上面的代码返回sorted_x = [2 2 2 3 5 6]但是我想修改它，也返回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：软件包排序