使用 Go 實現「合併排序」

Algorithm
, , ,

做法

將陣列分割後排序，再將兩個已排序的陣列合併成一個陣列。

實作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
func MergeSort(items []int) []int {
	// 當元素的數量只剩一個，則返回自己
	if len(items) <= 1 {
		return items
	}

	// 將陣列一分為二
	half := len(items) / 2
	left := MergeSort(items[:half])
	right := MergeSort(items[half:])

	// 宣告一個新陣列
	result := []int{}

	// 疊代直到左切片和右切片的元素都被抽出
	for len(left) > 0 && len(right) > 0 {
		// 判斷左切片的第一個元素是否小於右切片的第一個元素
		if left[0] < right[0] {
			// 將左切片的第一個元素抽出
			item := left[0]
			left = left[1:]
			// 推進至新陣列
			result = append(result, item)
		} else {
			// 將右切片的第一個元素抽出
			item := right[0]
			right = right[1:]
			// 推進至新陣列
			result = append(result, item)
		}
	}

	// 將左切片推進至新陣列
	result = append(result, left...)
	// 將右切片推進至新陣列
	result = append(result, right...)

	return result
}

程式碼