Skip to content

Commit 0453ba7

Browse files
author
Eric Lee
committed
add sort
1 parent d288b58 commit 0453ba7

7 files changed

Lines changed: 245 additions & 0 deletions

File tree

‎algorithm/sort/bubble.go‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
package sort
2+
3+
//冒泡排序，a是数组，n表示数组大小
4+
func BubbleSort(a []int, n int) {
5+
if n <= 1 {
6+
return
7+
}
8+
for i := 0; i < n; i++ {
9+
// 提前退出标志
10+
flag := false
11+
for j := 0; j < n-i-1; j++ {
12+
if a[j] > a[j+1] {
13+
a[j], a[j+1] = a[j+1], a[j]
14+
//此次冒泡有数据交换
15+
flag = true
16+
}
17+
}
18+
// 如果没有交换数据，提前退出
19+
if !flag {
20+
break
21+
}
22+
}
23+
}

‎algorithm/sort/bucket.go‎

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
package sort
2+
3+
import (
4+
"fmt"
5+
)
6+
7+
// 桶排序
8+
9+
// 获取待排序数组中的最大值
10+
func getMax(a []int) int {
11+
max := a[0]
12+
for i := 1; i < len(a); i++ {
13+
if a[i] > max {
14+
max = a[i]
15+
}
16+
}
17+
return max
18+
}
19+
20+
func BucketSort(a []int) {
21+
num := len(a)
22+
if num <= 1 {
23+
return
24+
}
25+
max := getMax(a)
26+
buckets := make([][]int, num) // 二维切片
27+
28+
index := 0
29+
for i := 0; i < num; i++ {
30+
index = a[i] * (num - 1) / max // 桶序号
31+
buckets[index] = append(buckets[index], a[i]) // 加入对应的桶中
32+
}
33+
34+
tmpPos := 0 // 标记数组位置
35+
for i := 0; i < num; i++ {
36+
bucketLen := len(buckets[i])
37+
if bucketLen > 0 {
38+
QuickSort(buckets[i]) // 桶内做快速排序
39+
copy(a[tmpPos:], buckets[i])
40+
tmpPos += bucketLen
41+
}
42+
}
43+
44+
}
45+
46+
// 桶排序简单实现
47+
func BucketSortSimple(source []int) {
48+
if len(source) <= 1 {
49+
return
50+
}
51+
array := make([]int, getMax(source)+1)
52+
for i := 0; i < len(source); i++ {
53+
array[source[i]] ++
54+
}
55+
fmt.Println(array)
56+
c := make([]int, 0)
57+
for i := 0; i < len(array); i++ {
58+
for array[i] != 0 {
59+
c = append(c, i)
60+
array[i] --
61+
}
62+
}
63+
copy(source, c)
64+
65+
}

‎algorithm/sort/counting.go‎

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
package sort
2+
3+
import "math"
4+
5+
func CountingSort(a []int, n int) {
6+
if n <= 1 {
7+
return
8+
}
9+
10+
var max int = math.MinInt32
11+
for i := range a {
12+
if a[i] > max {
13+
max = a[i]
14+
}
15+
}
16+
17+
c := make([]int, max+1)
18+
for i := range a {
19+
c[a[i]]++
20+
}
21+
for i := 1; i <= max; i++ {
22+
c[i] += c[i-1]
23+
}
24+
25+
r := make([]int, n)
26+
for i := range a {
27+
index := c[a[i]] - 1
28+
r[index] = a[i]
29+
c[a[i]]--
30+
}
31+
32+
copy(a, r)
33+
}

‎algorithm/sort/insertion.go‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
package sort
2+
3+
// 插入排序，a表示数组，n表示数组大小
4+
func InsertionSort(a []int, n int) {
5+
if n <= 1 {
6+
return
7+
}
8+
for i := 1; i < n; i++ {
9+
value := a[i]
10+
j := i - 1
11+
//查找要插入的位置并移动数据
12+
for ; j >= 0; j-- {
13+
if a[j] > value {
14+
a[j+1] = a[j]
15+
} else {
16+
break
17+
}
18+
}
19+
a[j+1] = value
20+
}
21+
}

‎algorithm/sort/merge.go‎

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
package sort
2+
3+
func MergeSort(arr []int) {
4+
arrLen := len(arr)
5+
if arrLen <= 1 {
6+
return
7+
}
8+
9+
mergeSort(arr, 0, arrLen-1)
10+
}
11+
12+
func mergeSort(arr []int, start, end int) {
13+
if start >= end {
14+
return
15+
}
16+
17+
mid := (start + end) / 2
18+
mergeSort(arr, start, mid)
19+
mergeSort(arr, mid+1, end)
20+
merge(arr, start, mid, end)
21+
}
22+
23+
func merge(arr []int, start, mid, end int) {
24+
tmpArr := make([]int, end-start+1)
25+
26+
i := start
27+
j := mid + 1
28+
k := 0
29+
for ; i <= mid && j <= end; k++ {
30+
if arr[i] < arr[j] {
31+
tmpArr[k] = arr[i]
32+
i++
33+
} else {
34+
tmpArr[k] = arr[j]
35+
j++
36+
}
37+
}
38+
39+
for ; i <= mid; i++ {
40+
tmpArr[k] = arr[i]
41+
k++
42+
}
43+
for ; j <= end; j++ {
44+
tmpArr[k] = arr[j]
45+
k++
46+
}
47+
copy(arr[start:end+1], tmpArr)
48+
}

‎algorithm/sort/quick.go‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
package sort
2+
3+
// QuickSort is quicksort methods for golang
4+
func QuickSort(arr []int) {
5+
separateSort(arr, 0, len(arr)-1)
6+
}
7+
8+
func separateSort(arr []int, start, end int) {
9+
if start >= end {
10+
return
11+
}
12+
i := partition(arr, start, end)
13+
separateSort(arr, start, i-1)
14+
separateSort(arr, i+1, end)
15+
}
16+
17+
func partition(arr []int, start, end int) int {
18+
// 选取最后一位当对比数字
19+
pivot := arr[end]
20+
21+
var i = start
22+
for j := start; j < end; j++ {
23+
if arr[j] < pivot {
24+
if !(i == j) {
25+
// 交换位置
26+
arr[i], arr[j] = arr[j], arr[i]
27+
}
28+
i++
29+
}
30+
}
31+
32+
arr[i], arr[end] = arr[end], arr[i]
33+
34+
return i
35+
}

‎algorithm/sort/selection.go‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
package sort
2+
3+
// 选择排序，a表示数组，n表示数组大小
4+
func SelectionSort(a []int, n int) {
5+
if n <= 1 {
6+
return
7+
}
8+
for i := 0; i < n; i++ {
9+
// 查找最小值
10+
minIndex := i
11+
for j := i + 1; j < n; j++ {
12+
if a[j] < a[minIndex] {
13+
minIndex = j
14+
}
15+
}
16+
// 交换
17+
a[i], a[minIndex] = a[minIndex], a[i]
18+
19+
}
20+
}

0 commit comments

Comments
 (0)