常见经典算法整理

一、排序算法

1.1 冒泡排序

func BubbleSort(nums []int) {
	for i := 0; i < len(nums); i++ {
		for j := 0; j < len(nums)-i-1; j++ {
			if nums[j] > nums[j+1] {
				nums[j], nums[j+1] = nums[j+1], nums[j]
			}
		}
	}
}

1.2 选择排序

func SelectionSort(nums []int) {
	for i := 0; i < len(nums); i++ {
		minIdx := i
		for j := i; j < len(nums); j++ {
			if nums[minIdx] > nums[j] {
				minIdx = j
			}
		}
		nums[i], nums[minIdx] = nums[minIdx], nums[i]
	}
}

1.3 插入排序

func InsertionSort(x []int) {
	for i := 0; i < len(x); i++ {
		m := i
		n := i - 1
		for n >= 0 {
			if x[m] > x[n] {
				x[m], x[n] = x[n], x[m]
			} else {
				break
			}
			m--
			n--
		}
	}
}

1.4 归并排序

func MergeSort(nums []int) []int {
	if len(nums) < 2 {
		return nums
	}
	mid := len(nums) / 2
	left := nums[0:mid]
	right := nums[mid:]
	return merge(MergeSort(left), MergeSort(right))
}

func merge(nums1 []int, nums2 []int) []int {
	nums := make([]int, 0)

	i := 0
	j := 0
	for i < len(nums1) && j < len(nums2) {
		if nums1[i] <= nums2[j] {
			nums = append(nums, nums1[i])
			i++
		} else {
			nums = append(nums, nums2[j])
			j++
		}
	}
	if i < len(nums1) {
		nums = append(nums, nums1[i:]...)
	}
	if j < len(nums2) {
		nums = append(nums, nums2[j:]...)
	}

	return nums
}

1.5 快速排序

def QuickSort(arr):
    if(len(arr)) < 2:
        return arr
    mid = arr[0]
    left, right = [], []
    for k in range(1, len(arr)):
        if mid >= arr[k]:
            left.append(arr[k])
        else :
            right.append(arr[k])
    return QuickSort(left) + [mid] + QuickSort(right)

二、查找算法

2.1 顺序查找

最常见的随机查找方式，时间复杂度O(n)

func Search(nums []int, k int) int {
	for i, v := range nums {
		if v == k {
			return i
		}
	}
	return -1
}

2.2 二分查找

func BinarySearch(nums []int, k int) int {
	left := 0
	right := len(nums) - 1
	if k < nums[left] || k > nums[right] {
		return -1
	}
	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] > k {
			right = mid - 1
		} else if nums[mid] < k {
			left = mid + 1
		} else {
			return mid
		}
	}
	return -1
}

前提需要元素是有序的，当查找的元素和中间节点比较时，如果查找元素比中间节点大则说明元素只可能在右半区，比其小则只可能在左半区，依次类推查找下去。

2.3 插值查找

func InterpolationSearch(nums []int, k int) int {
	left := 0
	right := len(nums) - 1
	if k == nums[left] {
		return left
	}
	for k >= nums[left] && k <= nums[right] && nums[left] != nums[right] {
		mid := left + (right-left)*(k-nums[left])/(nums[right]-nums[left])
		if nums[mid] > k {
			right = mid - 1
		} else if nums[mid] < k {
			left = mid + 1
		} else {
			return mid
		}
	}
	return -1
}

func main() {
	nums := []int{1, 4, 6, 9, 11, 66, 78}
	fmt.Println(InterpolationSearch(nums, 22))
}

二分查找是每次进行一次折半，插值在二分查找基础上进行改进，通过插值公式对节点所在位置进行预测，适用于元素分布相对均匀的数据集。