0交换排序 Google笔试题

题目:

长度为n的数组乱序存放着0至n-1，现在只能进行0与其他数的交换，请排序这个数组

package main

import "fmt"

func main() {
    s := []int{3, 5, 4, 0, 1, 2, 6}
    for _, v := range s {
        fmt.Printf("%d ", v)
    }
    fmt.Printf("\nafter:\n")

    var i int
    // 先找到 0 并把它放掉第一个位置
    for s[i] != 0 {
        i++
    }
    s[0], s[i] = s[i], s[0]

    i = 1

    for {
        // 从下标为 1 的数字开始，通过与 0 交换将 s[i] 的数字 x 放到 s[x] 处
        for s[i] != i {
            s[s[i]], s[0] = s[0], s[s[i]]
            s[i], s[s[i]] = s[s[i]], s[i]
            // 每次记得把 0 换回原位
            s[i], s[0] = s[0], s[i]
        }
        if i == len(s)-1 {
            break
        }
        // s[i] 排好之后就排 s[i+1]
        i++
    }

    for _, v := range s {
        fmt.Printf("%d ", v)
    }
}

在线运行代码