冒泡排序

  首先必须讲冒泡排序，作为面试官最常出的最简单题型，可见其重要性和普及性。冒泡排序顾名思义，就是一组排序列表，从头到尾两两比较，大的排在后方，代码如下：

def bubble_sort(l):
 for i in range(len(l),-1,-1): #从后往前遍历，这样可以不用再对最后已排好序的重新排序
 for j in range(1,i): #从前往后，末尾是i，也就是还未还排好序的
 if l[j-1] > l[j]: #如果前面大，就和后面的调换顺序
 l[j-1],l[j] = l[j],l[j-1]
 return l

可以看到用Python写出的冒泡排序仅仅6行就解决了，并且代码非常的简单，但这里有个缺点，也就是无论是最好情况还是最坏情况都是O(n^2)的时间复杂度，那实际上可以这样优化。如果是最好情况，也就是数组本身已经排好序的话，那表示未交换过，所以通过标志位来标记当一轮排序通过后未交换过，则说明已经排好序即可。优化后的代码：

def bubble_sort(l):
 for i in range(len(l),-1,-1):
 flag = 1 #每次新一轮开始就增加标志位
 for j in range(1,i):
 if l[j-1] > l[j]:
 l[j-1],l[j] = l[j],l[j-1]
 flag = 0 #如果交换则标志位为0
 if flag == 1: #判断标志位决定是否有必要继续往下遍历
 return l
 return l

那分析下时间复杂度和空间复杂度！因为排序都是在数组里进行交换排序的，所以空间复杂度为O(1)，也就是内存消耗为0(原地排序)；时间复杂度的话最好是比较n-1次，所以为O(N)，最坏则是有序度为0，则为n*(n-1)/2，即O(n2)的时间复杂度。那平均是多少呢？这里可以用估算的方法，假如以交换来说，最好时是没有交换，最坏是比较了n*(n-1)/2，所以平均是n*(n-1)/4，那比较肯定比交换要多几倍，所以最大不会超过O(n2)。另外因为冒泡比较时相等的不会交换，所以其是稳定算法！

嗨喽：正在学习python的小伙伴或者打算学习的，可以私信小编“01”领取资料！

插入排序

  相比于冒泡排序，插入排序可以说是非常具有实用性的语言，并且现在很多语言还是会利用插入排序作为其排序的一部分来实现！

  插入排序就是从左到右分为两堆，左边是排好序的，右边是待排序的，每次从右边取一个数依次跟左边相比较，小于哪个数就排在哪个数前面，直到碰到比它大的数为止！代码如下：

def insert_sort(l):
	for i in range(1,len(l)):
		for j in range(i,-1,-1): #从左边的最后一个数开始比较
			if l[j-1] > l[j]: #如果比最后一个数小，则排在其前边
				l.insert(j-1,l.pop(j))
			else: #如果比最后一个数大，则排在其后边
				break
	return l

三个角度分析插入排序，首先没有开辟空间，所以是原地排序，O(1)的空间复杂度；由于比较时不比较相等的情况，所以相等的情况不会交换位置，即是稳定的排序算法；那时间复杂度呢？最好当然是满有序度(即排好序的)，则每次比较右边的都比左边的大，break出来，则仅需O(n)次比较，最坏是有序度为0，则每次相当于都要比较一遍全数组，即为n*(n+1)/2为O(n2)的时间复杂度，平均来说，相当于每次都是往数组中插入一个数，而往数组中插入一个数为O(n)，所以n个数需要O(n2)的时间复杂度。

选择排序

  选择排序作为三大排序中的最基础，其没有多少可讲，而且因为无论最好、最坏、平均都是O(n2)的时间复杂度，所以我们了解即可。

  选择排序就是每次从左到右选第一个数依次比较到最后，所以即使是有序的，每个数也都要比较n次，那么n个数就要比较n2的次，即O(n2)时间复杂度，代码如下：

def choose_sort(l):
	for i in range(len(l)):
		for j in range(i+1,len(l)): #从左边那个数的后面一个知道最后依次比较
 if l[i] > l[j]: #不断地比较，把最小的数移到最左边
 l[i],l[j] = l[j],l[i]
 return l

从三个角度分析，以此类推，则为原地排序，O(1)的空间复杂度；因为未涉及相等的判断，所以是稳定性排序，而时间复杂度则最好、最好、平均都是O(n2)。

快速排序

  快速排序简称快排，可以说是面试官最喜欢考得排序算法之一了！和冒泡并列，而相对于冒泡，快速排序的思想要更好得多！

最后多说一句，小编是一名python开发工程师，这里有我自己整理了一套最新的python系统学习教程，包括从基础的python脚本到web开发、爬虫、数据分析、数据可视化、机器学习等。想要这些资料的可以关注小编，并在后台私信小编：“01”即可领取！