冒泡排序
个人理解
两层循环，外层循环次数=元素个数；
内层循环挨个比较，当 arr[j] 大于 arr[j+1]时交换两个值；
当内循环结束时，最多有n-1次交换，会将最大值置于尾部；
当一次外循环无元素交换时，说明序列已有序，可提前结束外层循环。
func BubbleSort(arr []int) []int {
length := len(arr)
for i:=0;i<length-1;i++ {
for j:=0;j<length-1-i;j++{
if arr[j]>arr[j+1] {
// 大的水泡不断往上走
arr[j], arr[j+1] = arr[j+1], arr[j]
}
}
}
return arr
}
复制代码选择排序
个人理解
从原始数组中选择最小(大)的元素，放在序列的起始位置；然后在从剩下的序列中继续选择最小(大)的元素，放在已排序序列的队尾。
func SelectSort(arr []int) []int {
for i := 0; i < len(arr)-1; i++ {
for j := i + 1; j <= len(arr)-1; j++ {
if arr[j] < arr[i] {
arr[j], arr[i] = arr[i], arr[j]
}
}
}
return arr
}
复制代码插入排序
个人理解
构建有序序列，对于未排序数据，在已排序序列从后向前扫描，找到合适的位置K并插入。 位置K之后的元素需要全部后移。
func InsertSort(arr []int) []int {
for i := 1; i <= len(arr)-1; i++ {
for j := i; j > 0; j-- {
if arr[j-1] > arr[j] {
arr[j-1], arr[j] = arr[j], arr[j-1]
}
}
}
return arr
}
复制代码快速排序
个人理解
通过一趟排序将待排记录分割成独立的A、B两部分，A部分全部小于基准值，B部分全部大于基准值。然后在对两部分做相同的处理，已完成排序的功能。
func QuickSort(arr []int, l, r int) []int {
if l < r {
pivot := arr[r]
i := l - 1
for j := l; j < r; j++ {
if arr[j] <= pivot {
i++
arr[j], arr[i] = arr[i], arr[j]
}
}
i++
arr[r], arr[i] = arr[i], arr[r]
QuickSort(arr, l, i-1)
QuickSort(arr, i+1, r)
}
return arr
}
复制代码希尔排序
个人理解
先将原始数组分割成为若干小数组分别进行直接插入排序，待整个数组"基本有序"时，再对全体进行依次直接插入排序。
func ShellSort(arr []int, batchSize int) []int {
if batchSize < 1 {
return []int{}
}
// 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)
return arr
}
复制代码归并排序
个人理解
将大数组拆分成n个小数组，先使小数组有序，然后按大小合并所有小数组，得到排序结果。
func MergeSort(arr []int) []int {
if len(arr) < 2 {
return arr
}
i := len(arr) / 2
left := MergeSort(arr[0:i])
right := MergeSort(arr[i:])
result := make([]int, 0)
m, n := 0, 0 // left和right的index位置
l, r := len(left), len(right)
for m < l && n < r {
if left[m] > right[n] {
result = append(result, right[n])
n++
continue
}
result = append(result, left[m])
m++
}
result = append(result, right[n:]...)
result = append(result, left[m:]...)
return result
}
复制代码完整代码
package main
import "fmt"
// 冒泡排序
func BubbleSort(arr []int) []int {
length := len(arr)
for i:=0;i<length-1;i++ {
for j:=0;j<length-1-i;j++{
if arr[j]>arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j] // 大的水泡不断往上走
}
}
}
return arr
}
// 选择排序
func SelectSort(arr []int) []int {
for i := 0; i < len(arr)-1; i++ {
for j := i + 1; j <= len(arr)-1; j++ {
if arr[j] < arr[i] {
arr[j], arr[i] = arr[i], arr[j]
}
}
}
return arr
}
// 插入排序
func InsertSort(arr []int) []int {
for i := 1; i <= len(arr)-1; i++ {
for j := i; j > 0; j-- {
if arr[j-1] > arr[j] {
arr[j-1], arr[j] = arr[j], arr[j-1]
}
}
}
return arr
}
// 快速排序
func QuickSort(arr []int, l, r int) []int {
if l < r {
pivot := arr[r]
i := l - 1
for j := l; j < r; j++ {
if arr[j] <= pivot {
i++
arr[j], arr[i] = arr[i], arr[j]
}
}
i++
arr[r], arr[i] = arr[i], arr[r]
QuickSort(arr, l, i-1)
QuickSort(arr, i+1, r)
}
return arr
}
// 希尔排序：把切片分成n个batch，对每个batch进行插入排序；然后减小batch，再对每个batch进行插入排序；直到bathc等于1
func ShellSort(arr []int, batchSize int) []int {
if batchSize < 1 {
return []int{}
}
// 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)
return arr
}
// 归并排序
func MergeSort(arr []int) []int {
if len(arr) < 2 {
return arr
}
i := len(arr) / 2
left := MergeSort(arr[0:i])
right := MergeSort(arr[i:])
result := make([]int, 0)
m, n := 0, 0 // left和right的index位置
l, r := len(left), len(right)
for m < l && n < r {
if left[m] > right[n] {
result = append(result, right[n])
n++
continue
}
result = append(result, left[m])
m++
}
result = append(result, right[n:]...)
result = append(result, left[m:]...)
return result
}
func main() {
nums := []int{5,6,4,7,3,8,2,9,1,0}
temNum := BubbleSort(nums)
fmt.Println("冒泡排序")
fmt.Println(temNum)
temNum = SelectSort(nums)
fmt.Println("选择排序")
fmt.Println(temNum)
temNum = InsertSort(nums)
fmt.Println("插入排序")
fmt.Println(temNum)
temNum = QuickSort(nums, 1,2)
fmt.Println("快速排序")
fmt.Println(temNum)
temNum = ShellSort(nums, 8)
fmt.Println("希尔排序")
fmt.Println(temNum)
temNum = MergeSort(nums)
fmt.Println("归并排序")
fmt.Println(temNum)
}
复制代码如有不当敬请指正。
其实参考内容中还有其他 桶排序、堆排序、计数排序 等等，一大堆花里胡哨的。就省点时间不纠结排序的第几种写法了，直接去做力扣不香吗。
