算法图解阅读笔记——第一曲（算法简介和选择排序）

灰太狼 2021-05-12 11:50 443阅读 0赞

## 前言 ##

> 零基础开始自学算法，目前用的都是python，于是就准备顺着python入门数据结构与算法。
> 
> 从风评得知，《算法图解》对小白比较友好，看下来也确实还好，内容以图为主，代码也较少，不需要什么代码功底。
> 
> 这是我看的第二遍，就决定来点笔记。

#### 目录结构 ####

第1章 算法简介

第2章 选择排序

--------------------

#### 正文 ####

## 算法简介 ##

> 重点讲到二分查找，大O表示法的初步介绍(后续章节还会细讲)，以及二分查找与简单查找的比较、旅行商问题

1.  二分查找：输入是一个有序的元素列表（**必须有序**）。如果要查找的元素包含在列表中，二分查找返回其位置；否则返回 null 。
    
    **就以书中的（0~100）猜数字为例：**
    
    ![在这里插入图片描述][2020082920372596.png_pic_center]
    
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center]
    
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 1]
    
        看完上图可发现在（0~100）中猜数，使用二分查找最多只有7步；
        而使用简单查找最坏的情况需要猜100次呢.....
    
    **Python3代码实现——二分查找**
    
        """ 作者：Troublemaker 功能： 版本： 日期：2020/8/15 8:55 脚本：binary_search.py """
        
        
        def binary_search(alist, item):
            low = 0
            high = len(alist) - 1
        
            while low <= high:
                mid = (low + high) // 2  # 向下取整
                guess = alist[mid]
                if guess == item:
                    return mid
                if guess > item:
                    high = mid - 1
                else:
                    low = mid + 1
        
            return None               # 找不到指定元素才执行
        
        my_list = [1, 3, 5, 7, 9]
        
        
        print(binary_search(my_list, 3))    # 1
        print(binary_search(my_list, -1))   # None
2.  大O表示法：一种特殊的表示法，指出了算法的速度有多快。
    
     *  大O表示法指的并非以秒为单位的速度
     *  大O表示法让你能够比较操作数，它指出了算法运行时间的增速。
    
    下面列出上述简单查找和二分查找的大O表示法，并附算法速度图
    
     *  简单查找： O ( n ) O(n) O(n)，线性时间
     *  二分查找： O ( l o g n ) O(logn) O(logn)，对数时间
    
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 2]
3.  旅行商问题为NP问题(np后续会解释)  
    算法复杂度为： O ( n ! ) O(n!) O(n!)，算法非常复杂，很多计算机科学领域的专家也认为没有改进的空间了  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 3]

## 选择排序 ##

> 重点介绍数组和链表的结构、以及数组和链表的优缺点，最后提出了选择排序

1.  数组
    
     *  数组中所有元素的位置在内存中都是相连的
     *  当所存元素超出预留内存大小时，需要整体转移
2.  链表
    
     *  链表的每个元素不仅存储了该元素的内容，还存储了下一个元素的地址
     *  只要有足够的内存空间，就能为链表分配内存
    
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 4]
    
        比较数组和链表的优缺点
        数组--优势：读取速度较快 O(1)| 劣势：插入和删除速度较慢 O(n)
        链表--优势：插入和删除速度较快 O(1)| 劣势：读取速度较慢 O(n)
        
        总结：当你需要使用更多读取而较少使用插入和删除功能时，使用数组；反之，使用链表
3.  选择排序：简单说，便是遍历数组，每次都找出数组中最大或最小的数，放入新数组，最终新数组就是有序数列。 大O表示法： O ( n 2 ) O(n^2) O(n2)
    
    **Python3代码实现——选择排序**
    
        """ 作者：Troublemaker 功能： 版本： 日期：2020/8/16 11:05 脚本：select_sort.py """
        
        
        def select_sort(alist):
            sorted_list = []
        
            while alist:
                small_index = 0
                smallest = alist[0]
                for idx in range(1, len(alist)):
        
                    if alist[idx] < smallest:
                        smallest = alist[idx]
                        small_index = idx
        
                alist.pop(small_index)
                sorted_list.append(smallest)
        
            return sorted_list
        
        
        print(select_sort([5,3,6,2,10]))

[2020082920372596.png_pic_center]: /images/20210511/a3896fab856148c896c37602ae92bbaa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20210511/61e7462afb4844f69c20de0e4c732b02.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20210511/790a5ae6622d479584b6ee3de7ca65d7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20210511/73fe32da551a4061bb9659b9629523cd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20210511/9d0cdf5682304de2841ef45987ce286a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20210511/a452b617a6a34b848b0b0fe9c4ad5d00.png