欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

基础算法之排序算法

程序员文章站 2022-05-25 19:45:08
排序算法的Golang实现 ~~~go package main import ( "fmt" ) //冒泡排序:升序 func BubbleSort(s []int) { for i:= 0;i s[j+1] { temp := s[j] s[j] = s[j+1] s[j+1] = temp } ......

排序算法的golang实现

package main

import (
    "fmt"
)
//冒泡排序:升序
func bubblesort(s []int)  {
    for i:= 0;i < len(s);i++{
        for j := 0;j < len(s) - 1 - i;j++{
            if s[j] > s[j+1] {
                temp := s[j]
                s[j] = s[j+1]
                s[j+1] = temp
            }
        }
    }
}

//选择排序:升序
func selectsort(nums []int)  {
    for i := 0;i < len(nums);i++{
        min := nums[i]
        minindex := i
        for j := i + 1;j < len(nums);j++{
            if min > nums[j] {
                min = nums[j]
                minindex = j
            }
        }
        nums[minindex] = nums[i]
        nums[i] = min
    }
}

//快速排序
func quicksort(s []int,left,right int)  {
    sort := func(s []int,low,high int)int {
        tmp := s[low]
        for low < high{
            for low < high && s[high] >= tmp{
                high--
            }
            s[low],s[high] = s[high],s[low]
            for low < high && s[low] <= tmp{
                low++
            }
            s[low],s[high] = s[high],s[low]
        }
        return low
    }
    if left < right {
        index := sort(s,left,right)
        quicksort(s,left,index-1)
        quicksort(s,index+1,right)
    }
}

//堆排序
func heapsort(s []int)  {
    heapadjust := func(s []int,parent,len int) {
        var i int
        for 2 * parent + 1 < len{
            lchild := 2 * parent + 1
            rchild := lchild + 1
            i = lchild
            //取出两个子节点中最大的一个
            if rchild < len && s[rchild] > s[lchild]{
                i = rchild
            }
            //如果最大节点大于父节点则交换,否则退出循环
            if s[i] > s[parent] {
                s[parent],s[i] = s[i],s[parent]
                parent = i
            }else {
                break
            }
        }
    }
    //从最后一个非叶子节点开始调整(len(s)/2 - 1)
    for i := len(s)/2 - 1;i >= 0;i--{
        heapadjust(s,i,len(s))
    }
    for i := len(s) - 1;i > 0;i--{
        s[0],s[i] = s[i],s[0]
        heapadjust(s,0,i)
    }
}

//归并排序
func merge(left,right []int) []int  {
    result := make([]int,0)
    m,n := 0,0
    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 mergesort(arr []int) []int {
    if len(arr) < 2 {
        return arr
    }
    i := len(arr)/2
    left := mergesort(arr[0:i])
    right := mergesort(arr[i:])
    result := merge(left,right)
    return result
}

func main() {
    //数组是属于值类型,方法传递的话应该是副本
    array := []int{9,20,1,3,2,80,76}
    //bubblesort(array)
    //selectsort(array)
    //quicksort(array,0,len(array) - 1)
    //堆排序
    //heapsort(array)
    //归并排序
    array = mergesort(array)
    fmt.println(array)
}