Golang实现经典算法

09-06 Mark 330

#### 冒泡排序：
由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。
```golang
func BubbleSort(data []int) []int {
		total := len(data)
		if total == 0 {
				return nil
		}

for i := 0; i < total; i++ {
				for j := 0; j < total-i-1; j++ {
						if data[j] > data[j+1] {
								data[j+1], data[j] = data[j], data[j+1]
						}
				}
		}
		return data
}
```

#### 快速排序:
快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
```golang
func QuickSort(data []int) []int {
		total := len(data)
		if total == 0 {
				return nil
		}

left := make([]int, 0)
		right := make([]int, 0)
		for i := 1; i < total; i++ {
				if data[i] < data[0] {
						left = append(left, data[i])
				} else {
						right = append(right, data[i])
				}
		}

left = QuickSort(left)
		right = QuickSort(right)
		return arrayMerge(left, data[0], right)
}

func arrayMerge(left []int, key int, right []int) []int {
		result := make([]int, 0)
		result = append(result, left...)
		result = append(result, key)
		result = append(result, right...)
		return result
}
```

#### 选择排序:
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。
```golang
func SelectSort(data []int) []int {
		total := len(data)
		if total == 0 {
				return nil
		}

var min, minKey int
		for i := 0; i < total-1; i++ {
				min = data[i]
				minKey = i
				for j := i + 1; j < total; j++ {
						if min > data[j] {
								min = data[j]
								minKey = j
						}
				}
				data[i], data[minKey] = data[minKey], data[i]
		}
		return data
}
```

#### 插入排序:
从第一个元素开始，该元素可以认为已经被排序，取出下一个元素，在已经排序的元素序列中从后向前扫描如果该元素（已排序）大于新元素，将该元素移到下一位置，重复步骤3，直到找到已排序的元素小于或者等于新元素的位置，将新元素插入到下一位置中，重复步骤2。
```golang
func InsertSort(data []int) []int {
		total := len(data)
		if total == 0 {
				return nil
		}

var key, pos int
		for i := 0; i < total; i++ {
				key = data[i]
				pos = i

for pos > 0 && data[pos-1] > key {
						data[pos] = data[pos-1]
						pos = pos - 1
				}
				data[pos] = key
		}
		return data
}
```