Go:排序

1、选择排序

在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到已排序序列的末尾,直到所有元素均排序完毕

1
2
3
4
5
6
7
8
9
10
11
func SelectSort(arr []int) {
for i := 0; i < len(arr) -1; i++ {
min := i
for j := i+1; j < len(arr); j++ {
if arr[j] < arr[min] {
min = j
}
}
arr[min], arr[i] = arr[i], arr[min]
}
}

2、冒泡排序

一次比较两个元素，如果它们的顺序错误就把它们交换过来。重复地进行比较直到没有再需要交换

1
2
3
4
5
6
7
8
9
10
11
12
func BubbleSort(arr []int) {
swapped := true
for swapped {
swapped = false
for i := 0; i < len(arr) -1; i++ {
if arr[i] > arr[i+1] {
arr[i], arr[i+1] = arr[i+1], arr[i]
swapped = true
}
}
}
}

3、插入排序

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入

1
2
3
4
5
6
7
8
9
10
11
12
13
func InsertSort(arr []int) {
for i := 0; i < len(arr); i++ {
selected := arr[i]
for j := i-1; j >= 0; j-- {
if arr[j] > selected {
arr[j], arr[j+1] = arr[j+1], arr[j]
} else {
arr[j+1] = selected
break
}
}
}
}

4、归并排序

把长度为n的输入序列分成两个长度为n/2的子序列，然后分别对这两个子序列分别采用归并排序，最后将两个排序好的子序列合并成一个最终的排序序列

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
func MergeSort(arr []int) []int{
if len(arr) <= 1 {
return arr
}
var middle int = len(arr)/2
left := MergeSort(arr[:middle])
right := MergeSort(arr[middle:])
return merge(left, right)
}

func merge(a, b []int) []int {
alen, blen := len(a), len(b)
var z []int = make([]int, alen + blen)
k := 0
i, j := 0, 0
for i < alen && j < blen  {
if a[i] < b[j] {
z[k] = a[i]
i++
} else {
z[k] = b[j]
j++
}
k++
}
for i != alen {
z[k] = a[i]
k++
i++
}
for j != blen {
z[k] = b[j]
k++
j++
}
return z
}

5、快速排序

从数列中挑出一个元素，称为 “基准”；然后，重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面。在这个分区退出之后，该基准就处于数列的中间位置，递归地把小于基准值元素的子数列和大于基准值元素的子数列排序

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
func QuickSort(arr []int) {
sort(arr, 0, len(arr)-1)
}
func sort(arr []int, left int, right int) {
if right <= left {
return
}
p := partition(arr, left, right) //快速排序切分
sort(arr, left, p-1)
sort(arr, p+1, right)
}
func partition(arr []int, left int, right int) int {
pivot := arr[left]
i, j := left, right+1
for true {
for i++; arr[i] < pivot; i++ {
if i == right {
break
}
}
for j--; pivot < arr[j]; j-- {
if j == left {
break
}
}
if i >= j {
break
}
arr[i], arr[j] = arr[j], arr[i]
}
arr[left], arr[j] = arr[j], arr[left]
return j
}

6、希尔排序

选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；按增量序列个数k，对序列进行k 趟排序；每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func ShellSort(arr []int) {
var gap int = len(arr) / 2
for gap > 0 {
for i := gap; i < len(arr); i++ {
temp := arr[i]
j := i
for j >= gap && arr[j-gap] > temp {
arr[j] = arr[j-gap]
j = j - gap
}
arr[j] = temp
}
gap = gap / 2
}
}

7、堆排序

将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成

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
func HeapSort(arr []int) {
var first int = len(arr) / 2                
for start := first; start > -1; start-- {
maxheapify(arr, start, len(arr)-1)
}
for end := len(arr) - 1; end > 0; end-- { 
arr[end], arr[0] = arr[0], arr[end]
maxheapify(arr, 0, end-1)
}
}
func maxheapify(arr []int, start int, end int) {
root := start
for true {
child := root*2 + 1
if child > end {
break
}
if child+1 <= end && arr[child] < arr[child+1] {
child = child + 1
}
if arr[root] < arr[child] {
arr[root], arr[child] = arr[child], arr[root]
root = child
} else {
break
}
}
}