欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

go语言算法版--冒泡排序和二分查找-吃透二分查找

程序员文章站 2024-03-20 09:53:58
...
//二分查找 返回找到num的index   时间复杂度是logn
// 循环次数 1    2    3  。。。  x
// n数     n/2  n/4  n/8 ...  n/(2^x)
//也就是当n个数为1,需要经历的查找次数与n的关系是 n/(2^x) = 1 -->x=logn
func binarySearch(ints []int, num int) int {
	len := len(ints)
	startIndex := 0
	endIndex := len - 1
	for startIndex <= endIndex {//循环条件
		midIndex := startIndex + (endIndex-startIndex)/2
		if ints[midIndex] == num {
			return midIndex
		}
		if ints[midIndex] < num {
			startIndex = midIndex + 1
		} else {
			endIndex = midIndex - 1
		}
	}
	return -1

}

//冒泡排序 时间复杂度n^2
func bubbleSort(ints []int) {
	len := len(ints)
	flag := true
	for i := 0; i < len-1; i++ {
		for j := 0; j < len-1-i; j++ {
			if ints[j] > ints[j+1] {
				flag = false
				ints[j], ints[j+1] = ints[j+1], ints[j]
			}
		}
		if !flag {
			flag = true
		} else {
			return
		}
	}
}

//快速排序
//插入排序
//归并排序

func main() {
	ints := []int{1, 3, 6, 9, 2, 0, 4, 8, 2, 5, 0, 12, 45, 32, 78, 65}
	bubbleSort(ints)
	fmt.Println(ints)
	ret := binarySearch(ints, 13)
	fmt.Println(ret)

}