高朗升序

I have a Go Language question here, is there any much better way to answer the answer in coding Golang compare to mine below?

Mangkuk is a list consisting of maximal size Sudu. Sudu is a permutation of consecutive integers, possibly with repeated items.

A Cawan is a Mangkuk where each Sudu is sorted in the ascending order. Write a function, MakeCawan(→Mangkuk), to sort the given Mangkuk into a Cawan.

For example,
MakeCawan([21, 20, 18, 20, 18, 20, 19]),
MakeCawan([21, 2000000, 18, 20, 18, 20, 19]),
MakeCawan([21, 20, 18, 20, 18, 20, 1900000])
should produce, respectively,
[18, 18, 19, 20, 20, 20, 21],
[21, 2000000, 18, 18, 19, 20, 20],
[20, 21, 18, 20, 18, 20, 1900000].

package main

    import (
        "fmt"
        "sort"
    )

    func main() {
        sl := []string{"MakeCawan"}
        sort.Sort(sort.StringSlice(sl))
        fmt.Println(sl)
        
        sl1 := []string{"MakeCawan"}
        sort.Sort(sort.StringSlice(sl1))
        fmt.Println(sl1)
        
        sl2 := []string{"MakeCawan"}
        sort.Sort(sort.StringSlice(sl2))
        fmt.Println(sl2)
        
        intSlice := []int{21,20,18,20,18,20,19}
        sort.Sort(sort.IntSlice(intSlice))
        fmt.Println(intSlice)

    }

The Output:

https://play.golang.org/p/tsE0BtMRos_9

</div>

The problem is a little bit tricky: It does not ask you to sort the whole slice (or mangkuk in its own term); it asks you to first recognize all successive intervals (with possible repeated elements) which is called sudu, and then sort each sudu.

func makeCawan(mangkuk []int) []int {
    for now, n := 0, len(mangkuk); now < n; {
        min := mangkuk[now]
        max := min
        head := now
    loop:
        for now++; now < n; now++ {
            switch x := mangkuk[now]; {
            case x < min-1 || x > max+1:
                sort(mangkuk[head:now], min, max)
                break loop
            case x == min-1:
                min = x
            case x == max+1:
                max = x
            }
        }
        if now >= n {
            sort(mangkuk[head:now], min, max)
        }
    }

    return mangkuk
}

Playground: https://play.golang.org/p/z3TGWnWnrVY

Answering this question assuming you want to sort a slice of int which are consecutive and repetitive.

Simply sorting the slice is a readable solution but would take O(nlgn) using a comparsion based sorting algorithm for a slice of length n.

We can use a better performin algorithm with O(n) auxillary space. Algorithm:
1. Iterate over array A and find min and max in.
2. Create an array B with length max-min+1.
3. Iterate over A and store count of each element in B i.e B[A[i] - min]++ .
4. Now iterate over B and print i + min, B[i] times.

Time Complexity - O(n)

https://play.golang.org/p/rptgMpWdKCX

Note that this loop is also O(n) where n is length of actual input array.

for i:=0;i<len(b);i++{
        for b[i] != 0{
            fmt.Printf("%v ", i + min)
            b[i]--
        }
    }