算法是编程的基础3

package main

import "fmt"

func main() {
    arr := []int{8, 9, 5, 7, 1, 2, 5, 7, 6, 3, 5, 4, 8, 1, 8, 5, 3, 5, 8, 4}
    //result := mergeSort(arr)
    result := buckerSort(arr)
    fmt.Println(result, arr)
}

//要求在O(nlogn)的时间复杂度下排序链表，且时间复杂度在O(1)
//
//涉及到O(logn)的算法有
//
//二分法
//快速排序
//归并排序
//堆排序
//二分法通常应用在已排序的序列中，且常用语查找算法，而不用作排序算法

// 冒泡排序：O(n^2)
// 外层循环 0到n-1      //控制比较轮数   n 表示元素的个数
// 内层循环 0到n-i-1     //控制每一轮比较次数
// 两两比较做交换
func bubbleSort(data []int) {
    if len(data) < 2 {
        return
    }
    for i := 0; i < len(data)-1; i++ {
        for j := 0; j < len(data)-i-1; j++ {
            if data[j] > data[j+1] {
                data[j], data[j+1] = data[j+1], data[j]
            }
        }
    }
}

// 快速排序：O(n*logn)
// i, j := left, right,将左边第一个数挖出来作为基准。
// j--由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
// i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
// 再重复执行2，3二步，直到i==j，将基准数填入a[i]中。
func quickSort(data []int, left, right int) {
    fmt.Println("every000: ", left, right)
    if left >= right {
        return
    }
    i, j := left, right
    x := data[left]
    for i < j {
        for i < j && data[j] > x {
            j--
        }
        data[i] = data[j]
        for i < j && data[i] <= x {
            i++
        }
        data[j] = data[i]
    }
    fmt.Println("every: ", data)
    data[i] = x
    quickSort(data, left, i-1)
    quickSort(data, i+1, right)
}

// 归并排序：O(n*log(n))
// 建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用
// 先分治 -> 再合并
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 merge(left, right []int) []int {
    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
        } else {
            result = append(result, left[m])
            m++

        }
    }
    result = append(result, right[n:]...) // 这里竟然没有报数组越界的异常？
    result = append(result, left[m:]...)
    return result
}

// 堆排序：O(n*log(n)) https://blog.csdn.net/code_beeps/article/details/91488526
// s[0]不用，实际元素从角标1开始
// 父节点元素大于子节点元素
// 左子节点角标为2*k
// 右子节点角标为2*k+1
// 父节点角标为k/2
func HeapSort(s []int) {
    N := len(s) - 1 //s[0]不用，实际元素数量和最后一个元素的角标都为N
    //构造堆
    //如果给两个已构造好的堆添加一个共同父节点，
    //将新添加的节点作一次下沉将构造一个新堆，
    //由于叶子节点都可看作一个构造好的堆，所以
    //可以从最后一个非叶子节点开始下沉，直至
    //根节点，最后一个非叶子节点是最后一个叶子
    //节点的父节点，角标为N/2
    for k := N / 2; k >= 1; k-- {
        sink(s, k, N)
    }
    //下沉排序
    for N > 1 {
        s[1], s[N] = s[N], s[1] //将大的放在数组后面，升序排序
        N--
        sink(s, 1, N)
    }
}

//下沉（由上至下的堆有序化）
func sink(s []int, k, N int) {
    for {
        i := 2 * k
        if i > N { //保证该节点是非叶子节点
            break
        }
        if i < N && s[i+1] > s[i] { //选择较大的子节点
            i++
        }
        if s[k] >= s[i] { //没下沉到底就构造好堆了
            break
        }
        s[k], s[i] = s[i], s[k]
        k = i
    }
}

// 桶排序：O(n)
// 借助一个一维数组就可以解决这个问题
// 最大数值作为这个数组的长度,数组的下标key等于这元素的，value就+1
func buckerSort(s []int) []int {
    arr := make([]int, 10)
    for _, v := range s {
        arr[v] += 1
    }
    sortList := make([]int, 0, len(s))
    for k, v := range arr {
        if v > 0 {
            for i := 0; i < v; i++ {
                sortList = append(sortList, k)
            }
        }
    }
    return sortList
}