数据结构是一门基础学科，你只有将数据结构知识掌握牢固才能够在以后的工作中得心应手，而且现在各大厂第一道就是笔试卡了不少初级程序员，所以作为计算机的从业者不得不重视数据结构算法的学习！而我则是打算先将数据结构书面知识思想掌握再去力扣进行系统刷题，是因为我觉得这样的学习更加科学，更加有效率也更加扎实。

一、初识算法-二分查找及大O表示法

开始学习前你最好需要有：数据结构知识，基础编程语言经验（Python即可）

1. 二分查找

二分查找？没错，就是你像的那样！其实还真的就是从中间的数开始找起，如果没有找到对应的数就将low和high的值进行修改，当你要寻找的值小于mid处值时我们令high = mid - 1,而当(这里你要找的值设为item)item > mid时我们令low = mid + 1(此处应当注意是>,<号而不带等号,可以先自行思考为何，后面我会作出解释)。而当low <= high时while循环将会继续进行，直至low > high跳出循环return mid或者None。

二分查找比简单查找要快得多，同样的问题可以将40亿规模缩小到32个！仅当列表是有序的时候二分查找才管用。二分查找的运行时间为对数时间O(log n)，简单查找为线性时间O(n)。

1.1 示例代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


def binary_search(list, item):
    low = 0
    high = len(list)-1
    while low <= high:
        mid = (low + high) // 2 # 这个地方注意Python3.x与Python2.x有差异
        guess = list[mid]
        if guess == item:
            return mid
        if guess < item:
            low = mid + 1
        else:
            high = mid -1
    return None

my_list = [1, 3, 5, 7, 9]

print(binary_search(my_list, 3))
print(binary_search(my_list, -1))

2. 大O表示法

大O表示法是一种特殊的表示法，指出算法的速度有多快。二分查找和简单查找的运行时间增速不同，也就是说，随着元素数量的增加，二分查找需要的额外时间并不多，而简单查找需要的额外时间却很多。因此，随着列表的增长（问题规模的扩大）二分查找的速度会比简单查找快得多。

大O表示法指的并非以秒为单位的速度。大O表示法让你能够比较操作数，它指出了算法运行时间的增速。
大O表示法指出了最糟情况下的运行时间。

下面按照从快到慢的顺序列出了你经常会遇到的5种大O运行时间。

O(log n)对数时间，二分查找
O(n)线性时间，简单查找
O(n * log n)快速排序，一种较快的排序算法
O(n^2)选择排序，一种速度较慢的排序算法
O(n!)旅行商问题解决方案，一种非常慢的算法

3. 小结

算法的速度指的并非时间，而是操作数的增速。
谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。
算法的运行时间用大O表示法表示。
O(log n)比O(n)快，当需要搜索的元素越多时，前者比后者快得越多。

二、选择排序

本章将介绍两种最基本的数据结构—数组和链表，学习选择排序算法，选择排序算法是下一章将介绍的快速排序的基石。

1. 内存工作原理

需要将数据存储到内存时，你请求计算机提供存储空间，计算机给你一个存储地址。需要存储多项数据时，有两种基本方式—数组和链表。但它们并非都适用于所有的情形，因此知道它们的差别很重要。接下里介绍数组和链表以及它们的优缺点。

2. 数组和链表的优缺点

2.1 随机读取元素

现在我们编写一个管理待办事项的应用程序，为此需要将这些事项存储在内存中，使用数组意味着所有待办事项在内存中都是相连的。

数组的优点也是易于查找，随机读取元素效率很高。但是当你有更多的待办事项时，如果内存不够则会重新申请一块内存地址，这会产生极大的浪费，面对这种问题我们就需要使用链表。

链表中的元素可存储在内存的任何地方，链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。链表的优势在插入元素方面。而链表不能够随机读取数据，需要从头节点开始依次往后遍历整个链表。

2.2 中间插入元素

在需要往中间插入元素时，链表更加合适，只需要修改它前面的那个元素指向的地址。而使用数组时，则必须将后面的元素都向后移。如果没有足够的空间，可能还要将整个数组复制到其他地方！

2.3 删除

删除元素时链表也是更好的选择，因为只需修改前一个元素指向的地址即可。使用数组时，删除元素后，必须将后面的元素都向前移。不同于插入，删除元素总能够成功。如果内存中没有足够的空间，插入操作可能失败，但在任何情况下都能够将元素删除。

	数组	链表
读取	O(1)	O(n)
插入	O(n)	O(1)
删除	O(n)	O(1)

以上是常见数组和链表操作的运行时间。

需要指出的是，仅当能够立即访问要删除的元素时，删除操作的运行时间才为O(1)。通常我们都记录了链表的第一个元素和最后一个元素，因此删除这些元素时运行时间为O(1)。

3. 选择排序

有了前面的知识，你就可以学习第二种算法—-选择排序了。

学习本节内容你需要掌握：数组、链表和大O表示法

假设你的计算机存储了很多乐曲。对于每个乐队，你都记录了其作品被播放的次数。你要将整个列表按播放次数从多到少的顺序排列，从而将你喜欢的乐队排序。我们该怎么做？

有一种办法时遍历这个列表，找出作品播放次数最多的乐队，并将该乐队添加到一个新列表中。再次这样做，找出播放次数第二多的乐队。继续这样做，你将得到一个有序表。接下来我们来分析一下这需要多长的时间。别忘了，O(n)时间意味着查看列表中的每个元素一次。要找出播放次数最多的乐队，我们必须检查列表中的每个元素。对于这种时间为O(n)的操作，你需要执行n次。需要总时间为O(n*n)，即O(n^2)。

3.1 示例代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


def findSmallest(arr):
    smallest = arr[0] # 存储最小元素
    smallest_index = 0 # 最小元素索引
    for i in range(1, len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_index = i
    return smallest_index

def selectionSort(arr): # 对数组排序
    newArr = []
    for i in range(len(arr)):
        smallest = findSmallest(arr) # 找到数组中的最小元素
        newArr.append(arr.pop(smallest)) # 将其加入到新数组中
    return newArr

print(selectionSort([5, 3, 6, 2, 10]))

注意：选择排序是一种灵巧的算法，但其速度不是很快。快速排序是一种更快的排序算法，其运行时间为O(n log n)，这将在下一章介绍。

4.小结

计算机内存犹如一大堆抽屉。
需要存储多个元素时，可使用数组或链表
数组的元素都在一起。
链表的元素是分开的，其中每个元素都存储了下一个元素的地址。
数组的读取速度很快。
链表的插入和删除速度很快。
在同一个数组中，所有元素的类型都必须相同（都为int、double等）。

三、递归

本章内容：学习递归，学习如何将问题分成基线条件和递归条件。

递归是一种优雅的解决方法

数据结构算法学习-算法图解

经过考研，数据结构这门课算是完整的了解，但是要说掌握程度肯定还是不太行，只停留在基础阶段（算法思想的理解），并未经常动手实践代码，而这篇文章旨在于帮助我记录平时学习数据结构算法的心得。