排序算法：golang实现

1、二分查找：

         输入是一个有序的元素列表。如果要查找的元素包含在列表中，二分查找返回其位置；否则返回空。

二分查找时间复杂度：

对于包含n个元素的列表，用二分查找最多需要

二分查找算法golang实现：

//二分查找算法
func binary_search(list []int, item int) int {
	low := 0
	high := len(list) - 1   //low,high用于跟踪要在其中查找的部分
	for low <= high {    //只要范围没有缩小到只有一个元素。
		mid := (low + high) / 2     //取数组中间值
		guess := list[mid]
		if guess == item {          //找到了元素
			return mid
		} else if guess > item {    //猜的数字大了
			high = mid - 1
		} else if guess < item {    //猜的数字小了
			low = mid + 1
		}
	}
	return -1         //没有指定的元素返回-1
}

Example：

二维有序数组，行和列都是递增的，找出某一个数
/*  对每行使用二分查找，此情况下的算法复杂度为O(nlogn)    */

func searchNumber(nums [][]int, elem int) (int, int) {
	for i := 0; i < len(nums); i++ {
		index := binary_search(nums[i], elem)
		if index != -1 {
			fmt.Println(i+1, "行", index+1, "列")
			return i, index
		}
	}
	return -1, -1
}

2、选择排序

选择排序是一种简单直观的排序算法， 时间复杂度：O(n²) 。适用于数据规模较小的情况。唯一的好处可能就是不占用额外的内存空间了吧。

1. 算法步骤

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

//选择排序
func slectionSort(nums []int) []int {
	newNums := []int{}
	length := len(nums)
	for i := 0; i < length; i++ {
		smallestIndex := findSmallest(nums)
		newNums = append(newNums, nums[smallestIndex])
		nums = append(nums[:smallestIndex], nums[smallestIndex+1:]...) //把最小值剔除掉,对剩余的元素进行排序
	}
	fmt.Println("newNums", newNums)
	return newNums
}

 遍历查找数组中的最小值索引：（时间复杂度为O（n））

func findSmallest(nums []int) int {
	smallest := nums[0]
	smallestIndex := 0
	for index, elem := range nums {
		if elem < smallest {
			smallest = elem
			smallestIndex = index
		}
	}
	return smallestIndex
}

3、快速排序

学习快速排序需要先了解递归。递归函数最简单的描述就是：自己调用自己。

每个递归函数有两部分： 基线条件（base case）和递归条件（recursive case）

递归条件：指的是函数调用自己；

基线条件：指的是函数不再调用自己，从而避免形成无限循环。

快速排序使用分而治之（D&C:divide and comquer）的策略。

D&C是递归的，使用D&C解决问题包括两个步骤：

1、找出基线条件，这种基线条件必须尽可能简单

2、不断将问题分解（缩小规模），直到符合基线条件。

提示：涉及数组的递归函数时，基线条件通常是数组为空或只包含一个元素。陷入困境时，请检查基线条件是不是这样。

使用快速排序对数组进行排序。基线条件为：数组为空或只包含一个元素。步骤如下：

1、选择基准值

2、将数组分成两个数组：小于基准值的元素组成的子数组和大于基准值的元素组成的子数组。

3、对这两个子数组进行快速排序。

快排的性能高度依赖基准值，最佳情况和平均情况都是，最糟糕情况。

func main() {
    N3 := []int{3, 14, 45, 6, 12, 10, 0, 4}
	fmt.Println(quickSort(N3))
}

//输出
>>[0 3 4 6 10 12 14 45]

func quickSort(nums []int) (sortArray []int) {
	if len(nums) < 2 {
		sortArray = nums
		return nums
	} else {
		pivot := nums[0]
		less, great := []int{}, []int{}
		for i := 1; i < len(nums); i++ {
			if nums[i] <= pivot {
				less = append(less, nums[i])
			} else {
				great = append(great, nums[i])
			}
		}
		sortArray = append(sortArray, quickSort(less)...)
		sortArray = append(sortArray, pivot)
		sortArray = append(sortArray, quickSort(great)...)
		return sortArray
	}
}

4、归并排序（Merge sort）将已经有序的数组合并，得到另一个有序的数组。

归并排序也叫合并排序，属于稳定排序算法，时间复杂度是

func mergeSort(nums []int, start, end int) {
    if start >= end {
        return
    }
    mid:=(start + end) / 2
    mergeSort(nums, start, mid)
    mergeSort(nums, mid+1, end)
    merge(nums, start, mid, end)
}

func merge(nums[]int, start, mid, end int) {
    temp := []int{}
    s1, s2 := start, mid+1
    for s1<= mid && s2<= end{
        if nums[s1] > nums[s2] {
            temp= append(temp, nums[s2])  //小的append在前面
            s2++
        } else {
            temp= append(temp, nums[s1])
            s1++
        }
    }
//两子数组长度不一定相同，比较结束后，可能会有一个子数组还有剩余的数没有比较
    if s1<=mid {  //前面一个子数组未比较的数直接append  
        temp= append(temp, nums[s1: mid+1]...)
    }
    if s2<=end {   //后面一个子数组未比较的数直接append 
        temp= append(temp, nums[s2: end+1]...)
    }
    for pos,item:=range temp{
        nums[start + pos] = item
    }
}

import(
    "fmt"
)
func main() {
var a=[]int{3,4,0,1,5,6,7,8}
    mergeSort(a, 0, len(a) - 1)
    fmt.Println(a)
}

5、堆排序

堆排序可以说是一种利用堆的概念来排序的选择排序，分为两种方法：

    大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列。

    小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列。

    堆排序的平均时间复杂度为。

    堆排序是不稳定的排序！

堆排序过程：

     1、构造一个大顶堆，取堆顶数字，也就是最大值。

     2、再将剩下的数字构造一个大顶堆，取堆顶数字（也就是剩下值当中的最大值）

     3、重复以上操作，直到取完堆中的数字，最终得到一个从大到小排列的序列

func heapSort(arr []int) []int {
        arrLen := len(arr)
        buildMaxHeap(arr, arrLen)
        for i := arrLen - 1; i >= 0; i-- {
                swap(arr, 0, i)
                arrLen -= 1
                heapify(arr, 0, arrLen)
        }
        return arr
}

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

func heapify(arr []int, i, arrLen int) {
        left := 2*i + 1     //节点i的左叶子节点
        right := 2*i + 2    //节点i的右叶子节点
        largest := i        //父亲节点i 
        if left < arrLen && arr[left] > arr[largest] {
                largest = left     
        }
        if right < arrLen && arr[right] > arr[largest] {
                largest = right
        }
        if largest != i {  //子节点如果大于节点i对应的值，将对应的节点跟i节点的值交换
                swap(arr, i, largest)  
                heapify(arr, largest, arrLen)
        }
}

func swap(arr []int, i, j int) {
        arr[i], arr[j] = arr[j], arr[i]
}

6、贪心算法

LeetCode55题：/*跳跃游戏：给定一个非负数组，你最初位于数组第一个位置。数组中每个元素代表你在该位置可以跳跃的最大长度。判断你是否可以到达最后一个位置。*/

func skipGame(nums []int) bool {
	n := len(nums)
	farthest := 0
	for i := 0; i < n; i++ {
		if farthest >= i { // 当前位置能够到达
			if farthest < (i + nums[i]) {
				farthest = i + nums[i] // 更新能够到达的最远位置
			} else if farthest >= n-1 { // 当前能够到达的最远位置已经大于数组长度，就不用再往后遍历了
				return true
			}
		}
	}
	return false
}