算法与数据结构之查找和排序

必备知识点

时间复杂度

时间复杂度是用来估算算法运行速度的一种方式，通常采用大O表示法。
需要注意以下几点：

1、时间复杂度指的不是算法运行的时间，而是算法运行的增速。
2、时间复杂度是估算，一些非必要的会省略。
3、通常表示为O(n)，其中n为操作数。

快速判断时间复杂度的方法：

4、如果发现循环数减半，那么复杂度就是logn。
5、有几次循环就是n的几次方，不要在意具体循环几次。

递归

递归比较容易理解，有以下两个特征:

调用自身

有 终止条件

#递归实现斐波那契数列
def fibnacci(n):
 if n=0 or n=1:
 return 1
 else:
 return fibnacci(n-1)+fibnacci(n-2) #这就是递归的精髓，把复杂重复的运算抽丝剥茧，每递归一次就简化一次

#斐波那契数列可以用更简单的方法实现
def fibnacci(n):
 a=b=c=1
 for i in range(2,n+1):
 c=a+b
 a=b
 b=c
 return c

#递归实现汉诺塔
def hanoi(n, A, B, C):
 if n > 0:
 hanoi(n-1, A, C, B)
 print('%s->%s' % (A, C))
 hanoi(n-1, B, A, C)

查找

简单查找

简单查找就是按顺序查找，直到查到指定元素，时间复杂度为O(n)。 

二分查找 

二分查找是对简单查找的一种优化，但是操作的只能是有序数组，就是通过中间值和需求数比较，通过比较结果来改变左右范围。
需要注意的是，不要通过切片改变列表，那样会加大空间复杂度。
尾递归的定义：尾递归就是所有递归语句都是在函数的最后出现的，正常是相当于循环的复杂度，但是python内没有优化。 

def bin_search(li, val):
 low = 0
 high = len(li)-1
 while low <= high: # 只要候选区不空,继续循环
 mid = (low + high) // 2
 if li[mid] == val:
 return mid
 elif li[mid] < val:
 low = mid + 1
 else: # li[mid] > val
 high = mid - 1
 return -1

一个小技巧

主要思想为:新建列表作为索引,如果一个数的索引存在,说明这个数也存在. 

lis = [2,4,6,7]
n = 3 #查找n
lst = [0,0,0,0,0,0,0,0] #创建一个元素均为0的列表,元素个数为lis中最大的数字加1
li = [0,0,1,0,1,0,1,1] #把 lis 中对应的数字值变为1
if li[3] == 1:
 print("存在")
else:
 print("不存在")

排序

排序算法是有稳定和不稳定之分。
稳定的排序就是保证关键字相同的元素，排序之后相对位置不变，所谓关键字就是排序的凭借，对于数字来说就是大小。

排序算法的关键点是分为有序区和无序区两个区域。 

冒泡排序 

冒泡排序思路：

比较列表中相邻的两个元素，如果前面的比后边的大，那么交换这两个数。
这就会导致每一次的冒泡排序都会使有序区增加一个数，无序区减少一个数。
可以认为得到一个排序完毕的列表需要n次或者n-1次。n-1次是因为最后一次不需要进行冒泡了，当然n或n-1的得到的列表是一样的。
冒泡排序是稳定的。

#基础冒泡
def bubble_sort(li):
 for i in range(len(li)-1): #第一层循环代表处于第几次冒泡
 for j in range(len(li)-i-1): #第二层循环代表无序区的范围
 if li[j]>li[j+1]:
 li[j],li[j+1]=li[k+1],li[j]

如果考虑冒泡的最好情况，也就是冒泡没有进行到n次的时候就已经不出现j>j+1了，那么排序已经进行完毕。 

def bubble_sort(li):
 for i in range(len(li)-1): #第一层循环代表处于第几次冒泡
 a= 1
 for j in range(len(li)-i-1): #第二层循环代表无序区的范围
 if li[j]>li[j+1]:
 li[j],li[j+1]=li[k+1],li[j]
 a=2
 if a=1:
 break

选择排序

选择排序的思路：

一次遍历找出最小值，放到第一个位置。
再一次遍历找最小值，在放到无序区第一个位置。
与冒泡一样是进行n或n-1次
每次都会让有序区增加一个元素，无序区减少一个元素。那么进行第i次的时候，它的第一位置的索引就是i。注意是无序区。
选择排序是不稳定的，跨索引交换(对比于相邻)就是不稳定的。

def select_sort(li):
 for i in range(len(li)-1):
 min_pos=i #第几次，无序区的第一个位置的索引就为几减一
 for j in range(i+1,len(li)):
 if li[j]<li[min_pos]: #min_pos会随着循环变换值
 min_pos=j
 li[i],li[min_pos]=li[min_pos],li[i]

插入排序

插入排序的思路：

在最开始有序区就把列表的第一个元素就放入有序区（这种有序是相对有序）。
在无序区第一个位置取出一个元素与有序区本来存在的元素进行比较，根据大小插入。
插入排序需要n-1次得出结果。
每次进行插入比较就是一步步的往前进行比较，也就是位置所以要一次次的减1，可能出现位置在最前面也就是插入位置索引为0，也可能是在中间，所以有两种情况。

def insert_sort(li):
 for i in range(1,len(li)): #i表示需要进行插入的元素的位置
 j=i-1 #j的初始位置，也就是无序区第一个元素的位置
 while j!=-1 and li[j]>li[i]:#只要能够与无序区元素进行比较,循环就不停止 
 #跳出循环的情况只有是有序区进行比较的元素没了，但是跳出循环时与li[j]<=li[i]时执行的语句是一样的，都是li[j+1]=li[i]，所以进行一个合并，减少代码量
 li[j+1]=li[j] #进行比较的有序区索引加一
 j-=1 #进行比较元素的索引减一
 li[j+1]=li[i] #也就是成为0号元素

快速排序

 快排思路:

取第一个元素,使元素归位。
归位的意义为列表分为两部分,左边都比该元素小,右边都比该元素大。
递归，进行多次归位。
快速排序的时间复杂度为 nlogn。

def _quick_sort(li,left,right):
 if left<right: #待排序区域至少有两个元素，left和right指的是索引
 mid = partition(li,left,right)
 _quick_sort(li,left,mid-1)
 _quick_sort(li,mid+1,right)
 
def quick_sort(li): #包装一下,因为循环不能直接递归,会非常慢
 _quick_sort(li,0,len[li]-1)
 
def partition(li,left,right): #此函数的意义是归位
 tmp=li[left] #left为第一个元素的索引，也就是需要进行归位的元素的索引
 while left<right:
 #注意，小的在左边，大的在右边
 while li[right]>tmp and left<right: #当right的值小于tmp是退出
 right-=1 #进行下一个right
 li[left]=li[right] #把left位置放比tmp小的right
 while li[left]<=tmp and left<right:
 left+=1
 li[right]=li[left] #把right位置放比tmp大的left
 li[left]=tmp #把tmp放在left=right时剩下的位置
 return left

堆排序

知识储备：

树是一种数据结构，可以通过递归定义。
树是由n个节点构成的集合
如果n=0，那么是一颗空树。
如果n>0，那么存在 一个根节点，其他的节点都可以单拎出来作为一个树。
根节点，就是回溯后存在的节点。
叶子节点，就是没有下层节点的节点。
树的深度可以粗略认为就是节点最多的分支有几个节点
度，度就是一个节点由几个分支，也就是说有几个子节点。
父节点和子节点索引的关系，若父节点的索引为i，左子节点索引为2i+1，右子节点的索引为2i+2，子节点找父节点，i=(n-1)//2
二叉树：度最多有两个的树。
满二叉树：一个二叉树，每一层的节点数都是最大值，也就是2，那么它就是满二叉树。
完全二叉树：叶子节点只能出现在最下层和次下层，并且最下面一层的节点都集中在该层最左侧，满二叉树是一种特殊的完全二叉树。

二叉树的存储方式：

链式存储，在之后的数据结构博客介绍。
顺序存储，顺序存储就是列表。结构就是从上到下从左到右。
堆：堆是一颗完全二叉树，分为大根堆和小根堆：
大根堆就是任何的子节点都比父节点小。
小根堆就是任何一个子节点都比父节点大。
堆的向下调整性质：当根节点的左右子树都是堆，那么就可以将其通过向下调整来建立一个堆
向下调整就是把根节点单独拿出来，让它子节点尽行大小比较，然后把根节点插入到子节点位置，子节点成为新的根节点，如此递归，直到满足堆的定义。
堆排序也就是优先队列，进行多次向下调整，得出一个根堆，然后根据索引从后往前挨个输出节点。
向下调整

 def sift(li,low,high):

 i=low #相对根节点
 j=2*i+1 #它的左子节点位置
 tmp=li[i] #根节点元素大小
 while j<=high:
 if j<high and li[j]<li[j+1]: #先判断左右节点大小,j<high是因为可能出现没有有节点的情况
 j+=1
 if tmp <li[j]: #再判断左节点或有节点与根节点的大小
 li[i]=li[j] #把左右节点移动到根节点
 i=j #把相对根节点移动到下一层
 j=2*i+1 #新的子节点索引
 else:
 break
 li[i]=tmp #最后把原来的根节点放到索引i上

从堆中取出节点元素 

def heap_sort(li):
 for low in range(len(li)//2-1,-1,-1): #构造堆，low的取值是倒序，从后面到0
 sift(li,low,len(li)-1) #high被假设是固定的，因为它为最小对结果不会影响。
 for high in range(len(li)-1,-1,-1): #取出时high一直是动态的,让取出的low不参加之后的调整，也就是构建新堆的过程
 li[0],li[high]=li[high],li[0] #把得出的无序区最后一个值，放到根结点处进行构建新堆
 sift(li,0,high-1) #

python的heapq内置模块

nlargest，nsmallest 前几个最大或最小的数
heapify(li) 构造堆
heappush 向堆里提交然后构造堆
heappop 弹出最后一个元素

归并排序

归并排序思路：

一次归并：含义就是给定一个列表，分为两段有序，让它成为一个整体有序的列表。
一次归并的方法：把两段有序列表，两两比较，把较小的那个元素拿出来，若一方元素数量为0，那么就将另一方所有元素取出。
归并排序： 先分解后合并，分解为单个元素，那么单个元素就是有序的，然后再两两一次归并，得到有序列表。
也就是把归并排序看成多次的一次归并。

def merge(li, low, mid, high): #mid为两段有序分界线左边第一个数的索引
 # 列表两段有序: [low, mid] [mid+1, high]
 i = low #i指向左半边列表进行比较的元素
 j = mid + 1 #j指向右半边列表进行比较的元素
 li_tmp = [] #比较出较小的元素暂存的位置
 while i <= mid and j <= high: #当左右两侧比较的元素都不为空时
 if li[i] <= li[j]: #左边小，左边元素拿到暂存li_tmp中，左边指针向右移动
 li_tmp.append(li[i])
 i += 1
 else: #右边小，右边元素拿到li_tmp中，右边元素的指针向左移动
 li_tmp.append(li[j])
 j += 1
 while i <= mid: #将剩余的元素都拿到li_tmp中
 li_tmp.append(li[i])
 i += 1
 while j <= high:
 li_tmp.append(li[j])
 j += 1
 for i in range(low, high+1): #把li_tmp中的元素放到li中
 li[i] = li_tmp[i-low]
 # 也可以这样移动： li[low:high+1] = li_tmp

def _merge_sort(li, low, high): #排序li从low到high的范围
 if low < high:
 mid = (low + high) // 2 #开始递归分散
 _merge_sort(li, low, mid)
 _merge_sort(li, mid+1, high)
 merge(li, low, mid, high) #合并

希尔排序

 希尔排序思路：

希尔排序是一种分组插入排序算法。
首先去一个整数d1=n/2,将元素分为d1个组，每组相邻量元素之间的距离为d1，在各组内直接插入排序。
接下来，去第二个元素d2=d1/2，重复上一步，直到di=1。
即所有元素在同一组内进行直接插入排序。
希尔排序每次都会让列表更加接近有序，在那过程中不会使某些元素变得有序。

def shell_sort(li):
 gap = len(li) // 2
 while gap > 0:
 for i in range(gap, len(li)):
 tmp = li[i]
 j = i - gap
 while j >= 0 and tmp < li[j]:
 li[j + gap] = li[j]
 j -= gap
 li[j + gap] = tmp
 gap /= 2

作者：崔园樟