????????排序操作和字符串格式化一樣是很多程序經常使用的操作。盡管一個最短的快排程序只要15 行就可以搞定，但是一個健壯的實現(xiàn)需要更多的代碼，并且我們不希望每次我們需要的時候 都重寫或者拷貝這些代碼。

????????幸運的是，sort包內置的提供了根據(jù)一些排序函數(shù)來對任何序列排序的功能。它的設計非常獨 到。在很多語言中，排序算法都是和序列數(shù)據(jù)類型關聯(lián)，同時排序函數(shù)和具體類型元素關 聯(lián)。相比之下，Go語言的sort.Sort函數(shù)不會對具體的序列和它的元素做任何假設。相反，它 使用了一個接口類型sort.Interface來指定通用的排序算法和可能被排序到的序列類型之間的約 定。這個接口的實現(xiàn)由序列的具體表示和它希望排序的元素決定，序列的表示經常是一個切 片。

????????一個內置的排序算法需要知道三個東西：序列的長度，表示兩個元素比較的結果，一種交換 兩個元素的方式；這就是sort.Interface的三個方法：

package sorttype Interface interface {Len() intLess(i, j int) bool // i, j are indices of sequence elementsSwap(i, j int)
}

?????????為了對序列進行排序，我們需要定義一個實現(xiàn)了這三個方法的類型，然后對這個類型的一個 實例應用sort.Sort函數(shù)。思考對一個字符串切片進行排序，這可能是最簡單的例子了。下面是 這個新的類型StringSlice和它的Len，Less和Swap方法

type StringSlice []string
func (p StringSlice) Len() int { return len(p) }
func (p StringSlice) Less(i, j int) bool { return p[i] < p[j] }
func (p StringSlice) Swap(i, j int) { p[i], p[j] = p[j], p[i] }

????????現(xiàn)在我們可以通過像下面這樣將一個切片轉換為一個StringSlice類型來進行排序：

sort.Sort(StringSlice(names))

????????這個轉換得到一個相同長度，容量，和基于names數(shù)組的切片值；并且這個切片值的類型有 三個排序需要的方法。

????????對字符串切片的排序是很常用的需要，所以sort包提供了StringSlice類型，也提供了Strings函 數(shù)能讓上面這些調用簡化成sort.Strings(names)。

????????這里用到的技術很容易適用到其它排序序列中，例如我們可以忽略大些或者含有特殊的字 符。（本書使用Go程序對索引詞和頁碼進行排序也用到了這個技術，對羅馬數(shù)字做了額外邏 輯處理。）對于更復雜的排序，我們使用相同的方法，但是會用更復雜的數(shù)據(jù)結構和更復雜 地實現(xiàn)sort.Interface的方法。

????????我們會運行上面的例子來對一個表格中的音樂播放列表進行排序。每個track都是單獨的一 行，每一列都是這個track的屬性像藝術家，標題，和運行時間。想象一個圖形用戶界面來呈 現(xiàn)這個表格，并且點擊一個屬性的頂部會使這個列表按照這個屬性進行排序；再一次點擊相 同屬性的頂部會進行逆向排序。讓我們看下每個點擊會發(fā)生什么響應。

????????下面的變量tracks包好了一個播放列表。（One of the authors apologizes for the other author’s musical tastes.）每個元素都不是Track本身而是指向它的指針。盡管我們在下面的代 碼中直接存儲Tracks也可以工作，sort函數(shù)會交換很多對元素，所以如果每個元素都是指針會 更快而不是全部Track類型，指針是一個機器字碼長度而Track類型可能是八個或更多。

type Track struct {Title stringArtist stringAlbum stringYear intLength time.Duration
}var tracks = []*Track{{"Go", "Delilah", "From the Roots Up", 2012, length("3m38s")},{"Go", "Moby", "Moby", 1992, length("3m37s")},{"Go Ahead", "Alicia Keys", "As I Am", 2007, length("4m36s")},{"Ready 2 Go", "Martin Solveig", "Smash", 2011, length("4m24s")},
}func length(s string) time.Duration {d, err := time.ParseDuration(s)if err != nil {panic(s)}return d
}

?????????printTracks函數(shù)將播放列表打印成一個表格。一個圖形化的展示可能會更好點，但是這個小程 序使用text/tabwriter包來生成一個列是整齊對齊和隔開的表格，像下面展示的這樣。注意到 *tabwriter.Writer是滿足io.Writer接口的。它會收集每一片寫向它的數(shù)據(jù)；它的Flush方法會格 式化整個表格并且將它寫向os.Stdout（標準輸出）。

func printTracks(tracks []*Track) {const format = "%v\t%v\t%v\t%v\t%v\t\n"tw := new(tabwriter.Writer).Init(os.Stdout, 0, 8, 2, ' ', 0)fmt.Fprintf(tw, format, "Title", "Artist", "Album", "Year", "Length")fmt.Fprintf(tw, format, "-----", "------", "-----", "----", "------")for _, t := range tracks {fmt.Fprintf(tw, format, t.Title, t.Artist, t.Album, t.Year, t.Length)}tw.Flush() // calculate column widths and print table
}

????????為了能按照Artist字段對播放列表進行排序，我們會像對StringSlice那樣定義一個新的帶有必 須Len，Less和Swap方法的切片類型。

type byArtist []*Track
func (x byArtist) Len() int { return len(x) }
func (x byArtist) Less(i, j int) bool { return x[i].Artist < x[j].Artist }
func (x byArtist) Swap(i, j int) { x[i], x[j] = x[j], x[i] }

????????為了調用通用的排序程序，我們必須先將tracks轉換為新的byArtist類型，它定義了具體的排 序：

sort.Sort(byArtist(tracks))

????????在按照artist對這個切片進行排序后，printTrack的輸出如下

Title Artist Album Year Length
----- ------ ----- ---- ------
Go Ahead Alicia Keys As I Am 2007 4m36s
Go Delilah From the Roots Up 2012 3m38s
Ready 2 Go Martin Solveig Smash 2011 4m24s
Go Moby Moby 1992 3m37s

????????對于我們需要的每個切片元素類型和每個排序函數(shù)，我們需要定義一個新的sort.Interface實 現(xiàn)。如你所見，Len和Swap方法對于所有的切片類型都有相同的定義。下個例子，具體的類 型customSort會將一個切片和函數(shù)結合，使我們只需要寫比較函數(shù)就可以定義一個新的排 Go語言圣經 sort.Interface接口 252 序。順便說下，實現(xiàn)了sort.Interface的具體類型不一定是切片類型；customSort是一個結構體類型。

type customSort struct {t []*Trackless func(x, y *Track) bool
}
func (x customSort) Len() int
func (x customSort) Less(i, j int) bool { return x.less(x.t[i], x.t[j]) }
func (x customSort) Swap(i, j int) { x.t[i], x.t[j] = x.t[j], x.t[i] }

????????讓我們定義一個多層的排序函數(shù)，它主要的排序鍵是標題，第二個鍵是年，第三個鍵是運行 時間Length。下面是該排序的調用，其中這個排序使用了匿名排序函數(shù)：

sort.Sort(customSort{tracks, func(x, y *Track) bool {if x.Title != y.Title {return x.Title < y.Title}if x.Year != y.Year {return x.Year < y.Year}if x.Length != y.Length {return x.Length < y.Length}return false
}})

????????這下面是排序的結果。注意到兩個標題是“Go”的track按照標題排序是相同的順序，但是在按 照year排序上更久的那個track優(yōu)先。

Title Artist Album Year Length
----- ------ ----- ---- ------
Go Moby Moby 1992 3m37s
Go Delilah From the Roots Up 2012 3m38s
Go Ahead Alicia Keys As I Am 2007 4m36s
Ready 2 Go Martin Solveig Smash 2011 4m24s

????????盡管對長度為n的序列排序需要 O(n log n)次比較操作，檢查一個序列是否已經有序至少需要n ?1次比較。sort包中的IsSorted函數(shù)幫我們做這樣的檢查。像sort.Sort一樣，它也使用 sort.Interface對這個序列和它的排序函數(shù)進行抽象，但是它從不會調用Swap方法：這段代碼 示范了IntsAreSorted和Ints函數(shù)和IntSlice類型的使用：

values := []int{3, 1, 4, 1}
fmt.Println(sort.IntsAreSorted(values)) // "false"
sort.Ints(values)
fmt.Println(values) // "[1 1 3 4]"
fmt.Println(sort.IntsAreSorted(values)) // "true"
sort.Sort(sort.Reverse(sort.IntSlice(values)))
fmt.Println(values) // "[4 3 1 1]"
fmt.Println(sort.IntsAreSorted(values)) // "false"

????????為了使用方便，sort包為[]int,[]string和[]float64的正常排序提供了特定版本的函數(shù)和類型。對 于其他類型，例如[]int64或者[]uint，盡管路徑也很簡單，還是依賴我們自己實現(xiàn)。