本节主要介绍部分排序算法，包括快速排序、合并排序、二分法检索。
文章目录1 .快速排序1.1快速排序分析1.2快速排序实现和时间复杂度2 .合并排序2.1合并排序分析2.2合并排序实现和时间复杂度3 .常见排序算法效率总结4 .二分法搜索4.1二分法搜索4.2
快速排序(英语： Quicksort )也称为分区交换排序(partition-exchange sort )，将待排序的数据在一次排序中划分为两个独立的部分，其中一个部分的所有数据以该方式将两个部分的数据分别快速排序，从而能够递归地进行整个排序过程，由此实现整体
步骤如下。
1.1从快速排序的分析数列中提取一个元素，称为“基准”(pivot )，对数列进行排序，所有元素小于基准值的在基准之前，所有元素大于基准值的在基准之后)，可以将相同的数排列在任意一侧这个分区结束后，这个基准位于数列的中间位置。 这称为分区操作。 递归排序小于参考值的元素的子数列和大于参考值的元素的子数列。 递归的底部情况是数列的大小为零或一，即永远排序。 一直递归持续，但这个算法总是会结束。 这是因为在每次迭代中，至少有一个元素位于其最后一个位置。
1.2快速排序的实现和时间复杂度defquick_sort(alist，start， 将end(: )、快速排序)、递归结束条件if start=end: return #开始元素从序列左侧的左向右移动要定位的基准元素mid=alist[start] # low 如果high=endwhilelowhigh:#low和high不匹配，则high指向的元素不会小于基准元素。 将high向左移动whilelowhighandalist [ high ]=mid : high-=1# high指向的元素置于low位置alist[low]=alist[high]#low与high不重叠将mid:low=1#low所指向的元素置于high位置，在alist[high]=alist[low] #退出循环之后，low与high重叠，其中，low是基准元素的正确位置#数据快速排序基准元素左侧的子序列quick_sort(alist、start、low-1 )作为快速排序基准元素右侧子序列quick_sort(alist )的结束列表
最差的时间复杂度： o(N2 ) ) ) ) ) ) ) )。
稳定性：不稳定
从一开始就需要平均o(nlogn )时间进行快速排序的记述尚不清楚。 但是，可以容易地观察到阵列元素每循环访问一次，并且使用O(n )的时间。 在使用“连接”(concatenation )的版本中，该运算也为o(n )。
在最好的情况下，每次运行分区时，将一个数列分成两个几乎相等的片段。 这意味着每次递归调用处理一半大小的数列。 因此，在大小达到1的数字序列之前，log可以嵌套调用n次。 这意味着调用树的深度是o(logn )。 但是，在同一层次结构的两个程序调用中，没有处理到原始数列的相同部分； 因此，程序调用的各个层次全部只需要o(n )的时间。 )每个调用都有一些共同的开销，但每个层只有o ) n )的调用，因此它们可以归纳为o ) n系数。 结果，该算法只能使用o(nlogn )时间。
演示：
2 .合并排序合并排序是采用分割统治法的非常典型的应用。 合并排序的想法是递归分解数组，然后合并数组。
2.1合并排序分析数组最小分解后，合并两个有序数组。 基本思想是比较两个数组开头的数，先取谁小，取后对应的指针向后移动一个。 然后比较到一个数组为空，最后复制另一个数组的剩馀部分即可。
2.2合并排序的实现和时间复杂度##python2defmerge_sort(alist ) : if len (a list )=1: return alist #二分分解num=len(alist ) )
)/2 left = merge_sort(alist[:num]) right = merge_sort(alist[num:]) # 合并 return merge(left,right)def merge(left, right): '''合并操作，将两个有序数组left[]和right[]合并成一个大的有序数组''' #left与right的下标指针 l, r = 0, 0 result = [] while l<len(left) and r<len(right): if left[l] < right[r]: result.append(left[l]) l += 1 else: result.append(right[r]) r += 1 result += left[l:] result += right[r:] return resultalist = [54,26,93,17,77,31,44,55,20]sorted_alist = merge_sort(alist)print(sorted_alist)最优时间复杂度：O(nlogn)
最坏时间复杂度：O(nlogn)
稳定性：稳定
空间换时间
搜索是在一个项目集合中找到一个特定项目的算法过程。搜索通常的答案是真的或假的，因为该项目是否存在。 搜索的几种常见方法：顺序查找、二分法查找、二叉树查找、mtdmt查找。
4.1 什么是二分法查找二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
二分法查找适用于顺序表。
最优时间复杂度：O(1)
最坏时间复杂度：O(logn)