# \u5806\u6392\u5e8f (Heap Sort) in Go<\/p>\n
\u5806\u6392\u5e8f\u662f\u4e00\u79cd\u57fa\u4e8e\u4e8c\u53c9\u5806\u6570\u636e\u7ed3\u6784\u7684\u6bd4\u8f83\u6392\u5e8f\u7b97\u6cd5\u3002\u4e0b\u9762\u662f\u4e00\u4e2a\u5b8c\u6574\u7684Go\u8bed\u8a00\u5b9e\u73b0：<\/p>\n
```go
\npackage main<\/p>\n
import "fmt"<\/p>\n
\/\/ heapSort \u5806\u6392\u5e8f\u4e3b\u51fd\u6570
\nfunc heapSort(arr []int) {
\nn := len(arr)<\/p>\n
\/\/ \u6784\u5efa\u6700\u5927\u5806（\u4ece\u6700\u540e\u4e00\u4e2a\u975e\u53f6\u5b50\u8282\u70b9\u5f00\u59cb）
\nfor i := n\/2 – 1; i >= 0; i– {
\nheapify(arr, n, i)
\n}<\/p>\n
\/\/ \u4e00\u4e2a\u4e2a\u4ece\u5806\u9876\u53d6\u51fa\u5143\u7d20
\nfor i := n – 1; i > 0; i– {
\n\/\/ \u5c06\u5f53\u524d\u5806\u9876（\u6700\u5927\u503c）\u79fb\u5230\u6570\u7ec4\u672b\u5c3e
\narr[0], arr[i] = arr[i], arr[0]<\/p>\n
\/\/ \u5bf9\u5269\u4f59\u5143\u7d20\u91cd\u65b0\u6784\u5efa\u6700\u5927\u5806
\nheapify(arr, i, 0)
\n}
\n}<\/p>\n
\/\/ heapify \u7ef4\u62a4\u5806\u7684\u6027\u8d28
\nfunc heapify(arr []int, n, i int) {
\nlargest := i\u00a0\u00a0\u00a0 \/\/ \u521d\u59cb\u5316\u6700\u5927\u503c\u4e3a\u5f53\u524d\u8282\u70b9
\nleft := 2*i + 1 \/\/ \u5de6\u5b50\u8282\u70b9
\nright := 2*i + 2 \/\/ \u53f3\u5b50\u8282\u70b9<\/p>\n
\/\/ \u5982\u679c\u5de6\u5b50\u8282\u70b9\u5b58\u5728\u4e14\u5927\u4e8e\u5f53\u524d\u6700\u5927\u503c
\nif left < n && arr[left] > arr[largest] {
\nlargest = left
\n}<\/p>\n
\/\/ \u5982\u679c\u53f3\u5b50\u8282\u70b9\u5b58\u5728\u4e14\u5927\u4e8e\u5f53\u524d\u6700\u5927\u503c
\nif right < n && arr[right] > arr[largest] {
\nlargest = right
\n}<\/p>\n
\/\/ \u5982\u679c\u6700\u5927\u503c\u4e0d\u662f\u5f53\u524d\u8282\u70b9，\u4ea4\u6362\u5e76\u7ee7\u7eed\u5806\u5316
\nif largest != i {
\narr[i], arr[largest] = arr[largest], arr[i]
\nheapify(arr, n, largest)
\n}
\n}<\/p>\n
func main() {
\narr := []int{12, 11, 13, 5, 6, 7}
\nfmt.Println("\u6392\u5e8f\u524d:", arr)<\/p>\n
heapSort(arr)
\nfmt.Println("\u6392\u5e8f\u540e:", arr)
\n}
\n```<\/p>\n
## \u7b97\u6cd5\u8bf4\u660e<\/p>\n
1. **\u6784\u5efa\u6700\u5927\u5806**：\u9996\u5148\u5c06\u65e0\u5e8f\u6570\u7ec4\u6784\u5efa\u6210\u4e00\u4e2a\u6700\u5927\u5806，\u8fd9\u6837\u6700\u5927\u7684\u5143\u7d20\u4f4d\u4e8e\u5806\u9876（\u6570\u7ec4\u5f00\u5934）\u3002<\/p>\n
2. **\u6392\u5e8f\u9636\u6bb5**：
\n\u00a0\u00a0 – \u5c06\u5806\u9876\u5143\u7d20（\u6700\u5927\u503c）\u4e0e\u6570\u7ec4\u672b\u5c3e\u5143\u7d20\u4ea4\u6362
\n\u00a0\u00a0 – \u51cf\u5c11\u5806\u7684\u5927\u5c0f（\u6392\u9664\u5df2\u6392\u5e8f\u7684\u6700\u5927\u5143\u7d20）
\n\u00a0\u00a0 – \u5bf9\u65b0\u7684\u5806\u9876\u5143\u7d20\u8fdb\u884c\u5806\u5316，\u4f7f\u5176\u6ee1\u8db3\u6700\u5927\u5806\u6027\u8d28
\n\u00a0\u00a0 – \u91cd\u590d\u4e0a\u8ff0\u8fc7\u7a0b\u76f4\u5230\u5806\u7684\u5927\u5c0f\u4e3a1<\/p>\n
## \u65f6\u95f4\u590d\u6742\u5ea6<\/p>\n
– \u6784\u5efa\u5806\u7684\u65f6\u95f4\u590d\u6742\u5ea6：O(n)
\n– \u6bcf\u6b21\u5806\u5316\u7684\u65f6\u95f4\u590d\u6742\u5ea6：O(log n)
\n– \u603b\u65f6\u95f4\u590d\u6742\u5ea6：O(n log n)
\n– \u7a7a\u95f4\u590d\u6742\u5ea6：O(1)（\u539f\u5730\u6392\u5e8f）<\/p>\n
## \u7279\u70b9<\/p>\n
– \u4e0d\u7a33\u5b9a\u6392\u5e8f\u7b97\u6cd5
\n– \u9002\u5408\u5927\u6570\u636e\u91cf\u7684\u6392\u5e8f
\n– \u4e0d\u9700\u8981\u989d\u5916\u7684\u5b58\u50a8\u7a7a\u95f4（\u539f\u5730\u6392\u5e8f）
\n– \u5b9e\u9645\u5e94\u7528\u4e2d\u6bd4\u5feb\u901f\u6392\u5e8f\u6162，\u4f46\u6700\u574f\u60c5\u51b5\u4e0b\u6027\u80fd\u66f4\u597d（O(n log n) vs \u5feb\u901f\u6392\u5e8f\u7684O(n\u00b2)）<\/p>\n
\u8fd9\u4e2a\u5b9e\u73b0\u4f7f\u7528\u4e86\u9012\u5f52\u7684\u5806\u5316\u65b9\u6cd5，\u4e5f\u53ef\u4ee5\u6539\u4e3a\u8fed\u4ee3\u5b9e\u73b0\u4ee5\u63d0\u9ad8\u6027\u80fd\u3002
\n\u00a0<\/p>\n
\u00a0<\/p>\n","protected":false},"excerpt":{"rendered":"
# \u5806\u6392\u5e8f (Heap Sort) in Go\u5806\u6392\u5e8f\u662f\u4e00\u79cd\u57fa\u4e8e\u4e8c\u53c9\u5806\u6570\u636e\u7ed3\u6784\u7684\u6bd4\u8f83\u6392\u5e8f\u7b97\u6cd5\u3002\u4e0b\u9762\u662f\u4e00\u4e2a\u5b8c\u6574\u7684Go\u8bed\u8a00\u5b9e\u73b0：go
\npackage mainimport \\”fmt\\”\/\/ heapSort \u5806\u6392\u5e8f\u4e3b\u51fd\u6570
\nfunc heapSort(arr []int) {
\nn : len(arr)\/\/ \u6784\u5efa\u6700\u5927\u5806（\u4ece\u6700\u540e\u4e00\u4e2a\u975e\u53f6\u5b50\u8282\u70b9\u5f00\u59cb）
\nfor i : n\/2 – 1; i > 0; i– {
\nheapify(arr, n, i)
\n}<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[746,292,1813,427],"topic":[],"class_list":["post-60200","post","type-post","status-publish","format-standard","hentry","category-server","tag-golang","tag-292","tag-1813","tag-427"],"yoast_head":"\n