基础算法之排序算法

排序算法的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)
}