七叶笔记 » golang编程 » golang 动画实现经典排序算法

golang 动画实现经典排序算法

分类: golang编程 | 浏览: 178

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
}

插入排序

个人理解

构建有序序列，对于未排序数据，在已排序序列从后向前扫描，找到合适的位置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)
}

如有不当敬请指正。

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

参考内容

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

References

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

相关文章