《算法图解》学习（一）

二分查找

二分查找又称折半查找、二分搜索、折半搜索等，是在分治算法基础上设计出来的查找算法，对应的时间复杂度为O(logn)

具体思路
假定一列有序的数据如下：
1 2 3 4 5 6 7 8 9 10
查找一个数字在里面的位置，例如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))