排序算法是面试时常考的基础知识，今天对三个基本排序算法进行总结。
---------------------------------------------------------------------------------------------------------------
首先写一个计算排序算法时间的装饰器以及3个辅助函数来帮助测试排序算法性能。
装饰器：
def timmer(func): #func 为传进来的排序函数对象 def warpper(arr, nums): # arr:待排序数组， nums:数组长度 start = time.time() r = func(arr, nums) end = time.time() print('toatl time is :', str(end - start)) return r return warpper生成无序数组或基本有序数组：
def random_list(num, start, end): # 生成无序数组 res = [] for i in range(num): res.append(random.randint(start, end)) return res def list_near_order(nums, start): #生成基本有序数组 a = [i for i in range(start, start + nums)] for i in range(nums//10): ind1 = random.randint(0,nums) ind2 = random.randint(0, nums) a[ind1], a[ind2] = a[ind2], a[ind1] return a检查排序是否正确：
def check_list(arr,ori_arr): #arr:排序后的数组， ori_arr: 原始数组 new_arr = sorted(ori_arr) if arr == new_arr: return True return False------------------------------------------------------------------------------------------------------
一、冒泡排序
基本思想：比较相邻的两个数，如果前者比后者大，则进行交换。每一轮排序结束，选出一个未排序中最大的数放到数组后面
冒泡排序算法的运作如下：
比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 def bubble_sort(arr): n = len(arr) for i in range(n-1): for j in range(1,n-i): if arr[j] < arr[j-1]: arr[j],arr[j-1] = arr[j-1], arr[j]特点总结：
最差时间复杂度为O(n^2),平均时间复杂度为O(n^2)。稳定性：稳定。辅助空间O(1)。
算法改进：
n个元素比较n-1趟，第i趟比较n-i次
若在其中的某一趟排序中：若始终未发生元素的交换说明已经排序号好，函数结束！
def bubble_sort_pro(arr): n = len(arr) for i in range(n-1): flag = 0 for j in range(1,n-i): if arr[j] < arr[j-1]: arr[j],arr[j-1] = arr[j-1], arr[j] flag = 1 if flag == 0: break冒泡排序算法应该是我们学习的第一个排序算法，非常简单，但是时间复杂度高，基本不会选择排序算法来解决排序问题。
二、选择排序
基本思想：依次选出数组最小的数放到数组的前面。首先从数组的第一个元素开始往后遍历，找出最小的数放到第一个位置。再从剩下数组中找出最小的数放到第二个位置。以此类推，直到数组有序。
def slect_sort(arr, nums): #arr：待排序数组， nums：数组长度 for i in range(nums): minInd = i for j in range(i, nums): if arr[j] < arr[minInd]: minInd = j arr[i], arr[minInd] = arr[minInd], arr[i]算法特点：
时间复杂度：O(n^2)
选择排序是不稳定的排序算法，不稳定发生在最小元素与A[i]交换的时刻。
比如序列：{ 5, 8, 5, 2, 9 }，一次选择的最小元素是2，然后把2和第一个5进行交换，从而改变了两个元素5的相对次序。
三、插入排序
基本思想 ：在要排序的一组数中，假设前面(n-1)[n>=2] 个数已经是排好顺序的，现在要把第n个数找到相应位置并插入，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
def insert_sort(arr,nums): #arr:待排序数组， nums: 数组长度 for i in range(1, nums): j = i - 1 # i 指向的元素为待插入的元素， j 指向的元素为已排好序序列的最后一个 if arr[i] < arr[j]: #若arr[i] > arr[j] 则 i 及之前的元素均为有序，直接过， 否则找到 i 指向的元素应该在的位置 temp = arr[i] while j >= 0 and arr[j] > temp: arr[j+1] = arr[j] j -= 1 arr[j+1] = temp算法分析：
在第一趟排序中，插入排序最多比较一次，第二趟最多比较两次，依次类推，最后一趟最多比较N-1次。因此有：
1+2+3+...+N-1 =N*(N-1)/2
因为在每趟排序发现插入点之前，平均来说，只有全体数据项的一半进行比较，我们除以2得到：
N*(N-1)/4
复制的次数大致等于比较的次数，然而，一次复制与一次比较的时间消耗不同，所以相对于随机数据，这个算法比冒泡排序快一倍，比选择排序略快。
与冒泡排序、选择排序一样，插入排序的时间复杂度仍然为O(N2)，这三者被称为简单排序或者基本排序。
如果待排序数组基本有序时，插入排序的效率会更高。
算法改进：
在插入某个元素之前需要先确定该元素在有序数组中的位置，上例的做法是对有序数组中的元素逐个扫描，当数据量比较大的时候，这是一个很耗时间的过程，可以采用二分查找法改进，这种排序也被称为二分插入排序。
改进后的代码如下：
def _binary_search(arr, l, r, target): #基于二分查找来找到插入点， 但不能直接照搬二分查找的算法。 arr：数组；l，r：查找的左,右端点索引值，target：目标值 while l < r: if r - l == 1: #当搜索范围 r - l == 1时，开始判断插入点的具体索引 if arr[l] > target: return l else: return r ind = (l + r)//2 if arr[ind] > target: r = ind else: l = ind def insert_sort_improve(arr, nums): for i in range(1, nums): j = i - 1 if arr[i] < arr[j]: temp = arr[i] ind = _binary_search(arr, 0, j, arr[i]) while j >= ind: arr[j+1] = arr[j] j -= 1 arr[ind] = temp插入排序的改进算法还有很多，如希尔排序，2-路插入排序等。在次不再一一叙述。
插入排序，在数组基本有序的情况下，性能优异。对于较大数组的排序，一般使用快速排序与插入排序组合。可进一步提升快速排序的性能。
