golang 数据结构实现之内部排序（一)

   直接上代码：

package sort
   
//直接插入排序
func DirectInsertSort(array []int) []int {
    len := len(array)
    var tmp, j int
    for i := 1; i < len; i++ {
        if array[i] < array[i-1] {
            tmp = array[i]
            for j = i - 1; tmp < array[j]; j-- {
                array[j+1] = array[j]
            }
            array[j+1] = tmp
        }
    }
    return array
}
   
//折半插入排序
func BinaryInsertSort(array []int) []int {
    var tmp, low, high, mid int
    len := len(array)
    for i := 1; i < len; i++ {
        tmp = array[i]
        low, high = 0, i-1
        for low <= high {
            mid = (low + high) / 2
            if array[mid] > array[0] {
                high = mid - 1
            } else {
                low = mid + 1
            }
        }
        for j := i - 1; j >= high+1; j-- {
            array[j+1] = array[j]
        }
        array[high+1] = tmp
    }
    return array
}
   
//冒泡排序
func BubbleSort(array []int) []int {
    len := len(array)
    for i := 0; i < len-1; i++ {
        for j := len - 1; j > i; j-- {
            if array[j-1] > array[j] {
                array[j-1], array[j] = array[j], array[j-1]
            }
        }
    }
    return array
}
   
//简单选择排序
func SelectSort(array []int) []int {
    len := len(array)
    for i := 0; i < len-1; i++ {
        for j := len + 1; j < len; j++ {
            if array[j-1] > array[j] {
                array[j-1], array[j] = array[j], array[j-1]
            }
        }
    }
    return array
}
   
//快速排序
func QuickSort(array []int) []int {
    quickSort(array, 0, len(array)-1)
    return array
}
   
func quickSort(array []int, left, right int) {
    if left < right {
        pivotPosition := partition(array, left, right)
        quickSort(array, left, pivotPosition-1)
        quickSort(array, pivotPosition+1, right)
    }
}
   
func partition(array []int, left, right int) int {
    pivot := array[left]
    for left < right {
        for left < right && array[right] > pivot {
            right--
        }
        array[left] = array[right]
        for left < right && array[left] <= pivot {
            left++
        }
        array[right] = array[left]
    }
   
    array[left] = pivot
    return left
}

本文出自 “Programming in XMU” 博客，请务必保留此出处http://liuxp0827.blog.51cto.com/5013343/1388684

golang 数据结构实现之内部排序（一),布布扣,bubuko.com

golang 数据结构实现之内部排序（一)

原文：http://liuxp0827.blog.51cto.com/5013343/1388684