golang 动画实现经典排序算法

golang 动画实现经典排序算法

冒泡排序

个人理解

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

}

希尔排序

个人理解

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

}

完整代码

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)

}

如有不当敬请指正。

其实参考内容中还有其他 桶排序、堆排序、计数排序 等等，一大堆花里胡哨的。就省点时间不纠结排序的第几种写法了，直接去做力扣不香吗。

参考内容

js实现十大经典排序算法（动图演示）[1]

References

[1] js实现十大经典排序算法（动图演示）: https://www.cnblogs.com/onepixel/articles/7674659.html

js实现计数排序的方法

原版计数排序，桶的容积需要一个可以包含最小值到最大值所有可能出现的数字。这里我们可以将桶换成对象，利用对象的自动排序与不能出现相同属性名的键值对这两个特点，不需要一个有序容积的桶，随意新增键值对即可。js实现计数排序的方法是什么，一起了解一下代码如下：

var ary=[23,14,12,24,53,31,53,35,46,12,62,23]

代码示例如下：

function countSort(arr){
let obj={};
//遍历原数组，给对象新增键值对，如果已经存在就对应的属性值++，如果不存在则新增键值对
for(let i=0;i<arr.length;i++){
if(!obj[arr[i]]){
obj[arr[i]]=1;
}else{
obj[arr[i]]++;
} 
}
let index=0;
//遍历对象属性名，按顺序放回覆盖原数组
for(let key in obj){
while(obj[key]>0){
arr[index]=Number(key);
obj[key]--;
index++
}
}
return arr;
}
console.log(countSort(ary));

以上就是js实现计数排序的方法的详细内容。