[go语言 排序算法]

快速排序

package main

import "fmt"

func main()  {
    arr := []int{1,2,-3,1,0,-5}
    qsort(arr,0,len(arr)-1)
    fmt.Println(arr)
}

func qsort(arr []int,left int,right int) {
    fmt.Println(left,right,"\n")
    if left > right {
        return;
    }
    tmp := arr[left];
    i:=left;j:=right;
    for i < j{
        for i < j && arr[j]>= tmp{
            j--;
            continue;
        }

        for i < j && arr[i] <= tmp  {
            i++;
            continue
        }

        if i < j {
            t := arr[i];
            arr[i] = arr[j];
            arr[left] = t;
        }
    }
    arr[left] = arr[i]
    arr[i] = tmp;
    qsort(arr,left,i-1);
    qsort(arr,i+1,right);
}

堆排序

package main

import "fmt"

func main()  {
    arr := []int{1,2,-3,2,0,-5}
    heapSort(arr)
    fmt.Println(arr)
}

func heapAdjust(arr []int, currentRootNode int,size int)  {
    if currentRootNode < size {
        left := currentRootNode*2+1;
        right := currentRootNode*2+2;
        var max = currentRootNode;
        if left< size && arr[left] > arr[max] {
            max = left;
        }

        if right <size && arr[right] > arr[max] {
            max = right;
        }

        if max!=currentRootNode {
            t := arr[max]
            arr[max] = arr[currentRootNode];
            arr[currentRootNode] = t;
            heapAdjust(arr,max,size)
        }
    }
}

func buildMaxHeap(arr []int)  {
    for i:= len(arr)/2;i>=0;i--{
        heapAdjust(arr,i,len(arr))
    }
}

func heapSort(arr []int)  {
    buildMaxHeap(arr)
    a := len(arr)
    for i:=a-1;i>0;i--{
        t:=arr[0]
        arr[0] = arr[i];
        arr[i] =t;
        a--;
        heapAdjust(arr,0,a)
    }
}