//冒泡排序
func bubbleSort1(s []int) []int {
//加判断,顺序时跳出循环,尽量避免走完两层循环
var isDone = false
for !isDone {
isDone = true
var i = 0
for i < len(s)-1 {
if s[i] > s[i+1] {
var temp = s[i]
s[i] = s[i+1]
s[i+1] = temp
isDone = false
}
i++
}
}
return s
}
//选择排序
func selectSort1(s []int) []int {
for i := 0; i < len(s); i++ {
min := i
for j := i + 1; j < len(s); j++ {
if s[j] < s[min] {
min = j
}
}
if min != i {
temp := s[i]
s[i] = s[min]
s[min] = temp
}
}
return s
}
//插入排序
func insertSort(s []int) []int {
for i := 1; i < len(s); i++ {
value := s[i]
j := i - 1
for ; j >= 0; j-- {
if s[j] > value {
s[j+1] = s[j]
} else {
break
}
}
s[j+1] = value
}
return s
}
/**
希尔排序:插入排序变形,把切片分成n个batch,对每个batch进行插入排序;然后减小batch,再对每个batch进行插入排序;直到bathc等于1
*/
func shellSort(arr []int, batchSize int) {
if batchSize < 1 {
return
}
// k : 每个batch中的元素所在batch的index, 介于[0, batchSize)
for k := 0; k < batchSize; k++ {
// 用到了插入排序
for j := 1; batchSize*j+k < len(arr); j++ { // j: 用来获取每个batch所在的第k个元素,拥有多少个batch
for n := j; n > 0; n-- {
pre := batchSize*(n-1) + k
next := batchSize*n + k
if arr[next] < arr[pre] {
arr[next], arr[pre] = arr[pre], arr[next]
}
}
}
}
shellSort(arr, batchSize/2)
}
//传统递归快排
func quickSort(arr []int, startIndex, endIndex int) {
// 递归结束条件:startIndex大等于endIndex的时候
if startIndex >= endIndex {
return
}
// 得到基准元素位置
var pivotIndex = partition2(arr, startIndex, endIndex)
// 根据基准元素,分成两部分递归排序(分治法)
quickSort(arr, startIndex, pivotIndex-1)
quickSort(arr, pivotIndex+1, endIndex)
return
}
//Go语言专属快排,利用新建左右切片,内存开销较大
func QuickSort(s []int) []int {
if len(s) == 0 {
return []int{}
} else {
first := s[0]
var (
leftArr []int
rightArr []int
)
for _, c := range s[1:] {
if c < first {
leftArr = append(leftArr, c)
} else {
rightArr = append(rightArr, c)
}
}
left := QuickSort(leftArr)
right := QuickSort(rightArr)
return append(append(left, first), right...)
}
}
//快排指针法:从左开始找第一个大于a[0]的,从右开始找第一个小于a[0]的,两者交换。继续重复下去
func partition1(arr []int, startIndex, endIndex int) int {
// 取第一个位置的元素作为基准元素
var pivot = arr[startIndex]
var left = startIndex
var right = endIndex
for left != right {
//控制right指针比较并左移
for left < right && arr[right] > pivot {
right--
}
//控制right指针比较并右移
for left < right && arr[left] <= pivot {
left++
}
//交换left和right指向的元素
if left < right {
arr[left], arr[right] = arr[right], arr[left]
}
}
//pivot和指针重合点交换
arr[left], arr[startIndex] = arr[startIndex], arr[left]
return left
}
//快排挖坑法:从右开始找第一个小于step(以a[0]为step)的a[x],则a[0]赋值为它; 从左开始找第一个小于step的a[y],使a[x]=a[y]。继续重复下去
func partition2(arr []int, startIndex, endIndex int) int {
key := arr[startIndex]
for startIndex < endIndex {
for startIndex < endIndex && arr[endIndex] >= key {
endIndex--
}
arr[startIndex] = arr[endIndex]
for startIndex < endIndex && arr[startIndex] <= key {
startIndex++
}
arr[endIndex] = arr[startIndex]
}
arr[endIndex] = key
return endIndex
}
//归并排序--归,分治
func mergeSort(arr []int) []int {
if len(arr) < 2 {
return arr
}
mid := len(arr) / 2
left := mergeSort(arr[:mid])
right := mergeSort(arr[mid:])
result := merge(left, right)
return result
}
//归并排序--并,合并两个有序数组
func merge(left, right []int) []int {
temp := make([]int, 0)
i, j := 0, 0
for i < len(left) && j < len(right) {
if left[i] <= right[j] {
temp = append(temp, left[i])
i++
} else {
temp = append(temp, right[j])
j++
}
}
if i < len(left) {
temp = append(temp, left[i:]...)
}
if j < len(right) {
temp = append(temp, right[j:]...)
}
return temp
}