《算法图解》学习(一) 二分查找 二分查找又称折半查找、二分搜索、折半搜索等,是在分治算法 基础上设计出来的查找算法,对应的时间复杂度为O(logn)
具体思路 假定一列有序的数据如下:
查找一个数字在里面的位置,例如7 记录两个起始位置,start
end
,和一个中间位置middle
((start + end)/2
) 取整
第一轮
start
middle
end
1
2
3
4
5
6
7
8
9
10
每次比较中间的数和目标值的大小,则无论大或者小,总会排除一半的数据剩下 (target>middle)middle+1~end 或者(target<middle) start ~middle -1, 例如本次示例 7>5(middle)则剩下
第一轮
start
middle
end
第二轮
start
middle
end
1
2
3
4
5
6
7
8
9
10
以此类推,下一次循环为:剩下 6 和 7 并且 start和middle都是6
第一轮
start
middle
end
第二轮
start
middle
end
第三轮
start(middle)
end
1
2
3
4
5
6
7
8
9
10
在下一轮,6 <7 start+1 这时 start = end =7 命中目标,跳出循环
第一轮
start
middle
end
第二轮
start
middle
end
第三轮
start(middle)
end
第四轮
target
1
2
3
4
5
6
7
8
9
10
代码示例 (返回查找次数) python: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 def binary (list , num ): low = list [0 ] step = 0 high = list [-1 ] while low < high: middle = int ((low + high) / 2 ) step += 1 if num > middle: low = middle + 1 elif num < middle: high = middle - 1 else : return step print (f"low:{low} high:{high} " ) return step if __name__ == '__main__' : list = [0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 ] print (binary(list , 15 ))
Java: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 package main.java.binary;import java.util.Arrays;import java.util.List;public class BinarySearch { public static void main (String[] args) { BinarySearch binarySearch = new BinarySearch (); List<Integer> list = Arrays.asList(1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 ); System.out.println(binarySearch.serach(list, 11 )); } public int serach (List<Integer> list, Integer num) { int low = list.get(0 ); int high = list.get(list.size()-1 ); int step = 0 ; while (low < high){ int middle = (low + high)/2 ; step++; if (num > middle){ low = middle+1 ; }else if (num < middle){ high = middle -1 ; }else { return step; } } return step; } }
冒泡排序
逻辑:
步骤:
最里面循环(递增):
比较相邻两个数据 ([i]
[i+1]
)得大小,如果大于则交换位置,
这样保证一次循环后 最大得数据过滤到了最后,下次循环只需要排序list[:-1]
依次下次执行,数据会从后往前,完整排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 # 冒泡排序 sortNum = [12, 23, 14, 43, 24, 64, 124, 1, 544, 87, 53] def bubbleSort(sorts): for i in range(len(sortNum)): for j in range(len(sortNum[i:-1])): if sortNum[j] < sortNum[j + 1]: temp = sortNum[j] sortNum[j] = sortNum[j + 1] sortNum[j + 1] = temp return sorts if __name__ == '__main__': print(bubbleSort(sortNum))
快速排序 原理:递归将原字段分割成最小得部分(单个数据或者空)
递归出口:
递归逻辑:
选择一个基准值用作比较
过滤出大于和小于改基准值得数据分成两组,
将两组数据递归执行,1,2步骤,直到分成最小部分
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 sortNum = [12, 23, 14, 43, 24, 64, 124, 1, 544, 87, 53] def fastSort(sort_num): if len(sort_num) < 2: return sort_num base_num = sort_num[0] lift_list = [i for i in sort_num if i < base_num] right_list = [i for i in sort_num if i > base_num] return fastSort(lift_list) + [base_num] + fastSort(right_list) if __name__ == '__main__': print(fastSort(sortNum))