时间就这样悄无声息的溜了，关注呦~No.1必备知识点时间复杂度时间复杂度是用来估算算法运行速度的一种方式，通常采用大O表示法。需要注意以下几点：时间复杂度指的不是算法运行的时间，而是算法运行的增速。时间复杂度是估算，一些非必要的会省略。通常表示为O(n)，其中n为操作数。快速判断时间复杂度的方法：如果发现循环数减半，那么复杂度就是 O(logn)。有几层循环就是n的几次方，不要在意具体循环几次。递归递归比较容易理解，有以下两个特征:
调用自身
有 终止条件
我们可以通过sys模块来进行查看默认最大执行次数,同时 sys.setrecursionlimit() 也能进行更改，默认是1000次。
#递归实现斐波那契数列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)
No.2查找简单查找简单查找就是按顺序查找，直到查到指定元素，时间复杂度为O(n)。二分查找二分查找是对简单查找的一种优化，但是操作的只能是有序数组，就是通过中间值和需求数比较，通过比较结果来改变左右范围。
二分查找的时间复杂度为 O(logn)。
需要注意的是，不要通过切片改变列表，那样会加大空间复杂度。尾递归的定义：尾递归就是所有递归语句都是在函数的最后出现的，正常是相当于循环的复杂度，但是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
#递归实现二分法lst = [1, 2, 33, 44, 555]def func(left,right,n): if left <= right: mid = (right + left) // 2 if n > lst[mid]: left = mid+1 if n < lst[mid]: right = mid - 1 if n == lst[mid]: return( "找到了") else: return("没找到") return func(left,right,n)ret = func(0,len(lst)-1,44)print(ret)
#区别:本方法利用切片,改变原序列表,增加了空间复杂度lst = [1, 2, 33, 44, 555]count = 0def func(lis,n): left = 0 right = len(lis)-1 global count count = count + 1 print(count) if left <= right: mid = (right + left) // 2 if n > lst[mid]: return func(lis[mid+1:],n) elif n < lst[mid]: return func(lis[:mid], n) else: return( "找到了") else: return("没找到")ret = func(lst,44)
一个小技巧主要思想为：新建列表作为索引,如果一个数的索引存在,说明这个数也存在。
lis = [2,4,6,7] #就是计数排序的反向使用n = 3 #查找nlst = [0,0,0,0,0,0,0,0] #创建一个元素均为0的列表,元素个数为lis中最大的数字加1li = [0,0,1,0,1,0,1,1] #把 lis 中对应的数字值变为1if li[3] == 1: print("存在")else: print("不存在")
No.3排序
排序算法是有稳定和不稳定之分，稳定的排序就是保证关键字相同的元素，排序之后相对位置不变。排序算法的关键点是分为有序区和无序区两个区域。
冒泡排序
冒泡排序思路：
比较列表中相邻的两个元素，如果前面的比后边的大，那么交换这两个数。这就会导致每一次的冒泡排序都会使有序区增加一个数，无序区减少一个数。可以认为得到一个排序完毕的列表需要n次或者n-1次。n-1次是因为最后一次不需要进行冒泡了，当然n或n-1的得到的列表是一样的。冒泡排序是稳定的，时间复杂度为O(n²)。
#基础冒泡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。注意是无序区。
选择排序的时间复杂度为O(n²)。
选择排序是不稳定的，跨索引交换(对比于相邻)就是不稳定的。
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次得出结果。
插入排序的时间复杂度为O(n²)。
每次进行插入比较就是一步步的往前进行比较，也就是位置所以要一次次的减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号元素
快速排序快排思路:取第一个元素,使元素归位。归位的意义为列表分为两部分,左边都比该元素小,右边都比该元素大。递归，进行多次归位。快速排序的时间复杂度为 O(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
在Haskell中只需要6行
quicksort :: (Ord a) =>[a] ->[a]quicksort [] = []quicksort (x:xs) = let smallersort = quicksort[a|a<- xs, a <=x] -- 属于xs，并且小于x let biggersort = quick[a|a<- xs,a>x] in smallersort ++ x ++ biggersort
堆排序知识储备：树是一种数据结构，可以通过递归定义。树是由n个节点构成的集合如果n=0，那么是一颗空树。如果n>0，那么存在 一个根节点，其他的节点都可以单拎出来作为一个树。根节点，就是回溯后存在的节点。叶子节点，就是没有下层节点的节点。树的深度可以粗略认为就是节点最多的分支有几个节点。度，度就是一个节点由几个分支，也就是说有几个子节点。父节点和子节点索引的关系，若父节点的索引为i，左子节点索引为2i+1，右子节点的索引为2i+2，子节点找父节点，i=(n-1)//2二叉树：度最多有两个的树。满二叉树：一个二叉树，每一层的节点数都是最大值，也就是2，那么它就是满二叉树。完全二叉树：叶子节点只能出现在最下层和次下层，并且最下面一层的节点都集中在该层最左侧，满二叉树是一种特殊的完全二叉树。
二叉树的存储方式：
链式存储，在之后的数据结构博客介绍。顺序存储，顺序存储就是列表。结构就是从上到下从左到右。堆：堆是一颗完全二叉树，分为大根堆和小根堆：大根堆就是任何的子节点都比父节点小。小根堆就是任何一个子节点都比父节点大。堆的向下调整性质：当根节点的左右子树都是堆，那么就可以将其通过向下调整来建立一个堆。向下调整就是把根节点单独拿出来，让它子节点尽行大小比较，然后把根节点插入到子节点位置，子节点成为新的根节点，如此递归，直到满足堆的定义。
堆排序也就是优先队列，进行多次向下调整，得出一个根堆，然后根据索引从后往前挨个输出节点。
快速排序的时间复杂度为 O(nlogn)。
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，那么就将另一方所有元素取出。归并排序：先分解后合并，分解为单个元素，那么单个元素就是有序的，然后再两两一次归并，得到有序列表。快速排序的时间复杂度为 O(nlogn)。也就是把归并排序看成多次的一次归并。
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_tmpdef _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。即所有元素在同一组内进行直接插入排序。
希尔排序的时间复杂度为O(
)。
希尔排序每次都会让列表更加接近有序，在那过程中不会使某些元素变得有序。
def shell_sort(li): gap = len(li) // 2 while gap > 0: #接下来进行的其实就是插入排序的代码，只不过无序区起始是从gap也就是从gap开始。 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
No.3总结
按照平均时间复杂度将排序分为3类：平方阶O(n²)排序，一般称为简单排序，例如直接插入排序，直接选择排序和冒泡排序。线性对数阶O(nlogn)排序，如快速排序、堆排序和归并排序。线性阶O(n)排序，如基数排序（假定数据的位数d和进制r为常量时）。
各种排序方法的性能
因为不同排序方法适应于不同的应用环境和要求，所以选择适合的排序方法应综合考虑下列因素：
待排序的元素数目n（问题规模）；元素的大小（每个元素的规模）；关键字的结构及其初始状态；对稳定性的要求；语言工具的条件；存储结构；时间和空间复杂度等。
没有一种排序方法是绝对好的。每一种排序方法都各有其优缺点，适用于不同的环境。因此，在实际应用中，应根据具体情况做选择。首先考虑排序对稳定性的要求，若要求稳定，则只能在稳定方法中选取，否则可以在所有方法中选取；其次要考虑待排序节点数n的大小，若n较大，则可在改进方法中选取，否则在简单方法中选取；然后在考虑其他因素。综合考虑以上几点可以得出的大致结论：
若n较小（如n<=50），可采用直接插入排序或直接选择排序。当元素规模较小时，直接插入排序较好；否则因为直接选择排序移动的元素少于直接插入排序，应选直接选择排序。若文件初始状态基本有序（指正序），则应选用直接插入、冒泡或随机的快速排序。若n较大，则应采用时间复杂度为O(nlogn)的排序方法：快速排序、堆排序或归并排序。快速排序被认为是目前基于比较的内部排序中较好的方法，当待排序的关键字随机分布时，快速排序的平均时间最短；但堆排序所需的辅助空间比快速排序少，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的，若要求稳定，则可选用归并排序。若要将两个有序表合并成一个新的有序表，最好的方法是归并排序。在基于比较的排序方法中，至少是需要O(nlogn)的时间。而基数排序只需要一步就会引起r种可能的转移，即把一个元素装入r个队列之一，因此一般情况下，基数排序可能在O(n)时间内完成对n个元素的排序。但遗憾的是，基数排序只适用于像字符串和整数这类有明显结构特征的关键字，而当关键字的取值范围属于某个无穷集合（例如实数型关键字）时，无法使用基数排序，这时只有借助于“比较”的方法来排序。由此可知，若n很大，元素的关键字位数较少且可以分解时，采用基数排序较好。
—【 THE END 】—
推荐日志
1
开启我的Plan B计划
2
使用FFmpeg转换媒体文件的快速指南
3
Docker 学习笔记：Docker简介和安装
后厂村不入流程序员
长按关注，修炼内功
如果觉得《数据结构与算法之查找和排序》对你有帮助，请点赞、收藏，并留下你的观点哦！
