！！！认真学习，争取拿下Offer！！！
-------------------------------------进入学习模式---------------------------------------
常见的排序算法效率的比较：
| 排序方法 | 平均情况 | 最好 | 最坏 | 辅助空间 | 稳定性 |
| 冒泡 | o(n^2) | o(n) | o(n^2) | o(1) | √ |
| 选择 | o(n^2) | o(n^2) | o(n^2) | o(1) | × |
| 插入 | o(n^2) | o(n) | o(n^2) | o(1) | √ |
| 希尔 | o(nlogn)- o(n^2) | o(n^1.3) | o(n^2) | o(1) | × |
| 堆 | o(nlogn) | o(nlogn) | o(nlogn) | o(1) | × |
| 归并 | o(nlogn) | o(nlogn) | o(nlogn) | o(n) | √ |
| 快速【考的最多】 | o(nlogn) | o(nlogn) | o(n^2) | o(logn)- o(n) | √ |
一、冒泡排序
1、基本思想：两个数比较大小，较大的数下沉，较小的数冒起来。
2、过程：
（1）比较相邻的两个数据，如果第二个数小，就交换位置。
（2）从后向前两两比较，一直到比较最前两个数据。最终最小数被交换到起始的位置，这样第一个最小数的位置就排好了。
（3）继续重复上述过程，依次将第2.3...n-1个最小数排好位置。
3、平均时间复杂度：o(n^2)
4、python代码：
"""冒泡排序：每个元素都比较一遍，进行冒泡比较【从小到大】
最优时间复杂度：o(n) 最坏时间复杂度：o(n^2) 稳定性：稳定"""
def bubble_sort(alist):
n=len(alist)
for j in range(n-1):
for i in range(n-j-1):
if alist[i]>alist[i+1]:
alist[i],alist[i+1]=alist[i+1],alist[i]
return alist
print(bubble_sort([5,2,8,7,1,3,4])) #[1, 2, 3, 4, 5, 7, 8]
5、优化：
（1）针对问题：
数据的顺序排好之后，冒泡算法仍然会继续进行下一轮的比较，直到n-1次，后面的比较没有意义
（2）方案：
设置标志位flag，如果发生了交换flag设置为true；如果没有交换就设置为false。
这样当一轮比较结束后如果flag仍为false，即：这一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去。
def bubble_sort(alist):
n=len(alist)
for j in range(n-1):
flag=False
for i in range(n-j-1):
if alist[i]>alist[i+1]:
alist[i],alist[i+1]=alist[i+1],alist[i]
flag=True
if flag==False:
break
return alist
print(bubble_sort([5,2,8,7,1,3,4])) #[1, 2, 3, 4, 5, 7, 8]
二、选择排序
1、基本思想：
（1）在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；
（2）第二次遍历n-2个数，找到最小的数值与第二个元素交换；………………………………….
（3）第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。
2、过程：
3、平均时间复杂度：o(n2)
4、python代码
"""选择排序：始终从无序的列表中选择最小的往前面放【从小到大】
最优时间复杂度：o(n^2) 最坏时间复杂度：o(n^2) 稳定性：不稳定"""
def select_sort(alist):
n=len(alist)
for j in range(n-1):
min_index=j
for i in range(j+1,n):
if alist[min_index]>alist[i]:
min_index=i
alist[j],alist[min_index]=alist[min_index],alist[j]
return alist
print(select_sort([2,4,1,3,8,7,6])) #[1, 2, 3, 4, 6, 7, 8]
三、插入排序
1、基本思想：
在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
2、过程：【有点像打牌】
3、平均时间复杂度：o(n2)
4、python代码
"""插入排序：每次把最小的插入到第一个【从小到大】
最优时间复杂度：o(n) 最坏时间复杂度：o(n^2) 稳定性：稳定"""
def insert_sort(alist):
n=len(alist)
for j in range(1,n):
i=j
while i>0:
if alist[i]<alist[i-1]:
alist[i],alist[i-1]=alist[i-1],alist[i]
i-=1
else:
break
return alist
print(insert_sort([3,5,56,2,1,7,8])) #[1, 2, 3, 5, 7, 8, 56]
四、希尔排序
1、前言：
数据序列1： 13-17-20-42-28 利用插入排序，13-17-20-28-42. Number of swap:1;
数据序列2： 13-17-20-42-14 利用插入排序，13-14-17-20-42. Number of swap:3;
如果数据序列基本有序，使用插入排序会更加高效。
2、基本思想：
在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。
然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序。
3、过程：
3、平均时间复杂度：o(n^1.3) 【其时间复杂度与选择的步长有关】
4、python代码
"""希尔排序：插入排序的改进，增加一个gap（步长）【从小到大】
最优时间复杂度：根据gap的不同而不同 最坏时间复杂度：o(n^2) 稳定性：不稳定"""
def shell_sort(alist):
n=len(alist)
gap=n//2
while gap>=1:
for j in range(gap,n):
i=j
while i>0:
if alist[i]<alist[i-1]:
alist[i],alist[i-1]=alist[i-1],alist[i]
i-=gap
else:
break
gap//=2
return alist
print(shell_sort([3,5,56,2,1,7,8])) #[1, 2, 3, 5, 7, 8, 56]
五、快速排序
1、基本思想：（分治）
（1）先从数列中取出一个数作为key值；
（2）将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
（3）对左右两个小数列重复第二步，直至各区间只有1个数。
2、辅助理解：挖坑填数
（1）初始时 i = 0; j = 9; key=72
由于已经将a[0]中的数保存到key中，可以理解成在数组a[0]上挖了个坑，可以将其它数据填充到这来。
从j开始向前找一个比key小的数。当j=8，符合条件，a[0] = a[8] ; i++ ; 将a[8]挖出再填到上一个坑a[0]中。
这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。
这次从i开始向后找一个大于key的数，当i=3，符合条件，a[8] = a[3] ; j-- ; 将a[3]挖出再填到上一个坑中。
（2）此时 i = 3; j = 7; key=72
再重复上面的步骤，先从后向前找，再从前向后找。
从j开始向前找，当j=5，符合条件，将a[5]挖出填到上一个坑中，a[3] = a[5]; i++;
从i开始向后找，当i=5时，由于i==j退出。
此时，i = j = 5，而a[5]刚好又是上次挖的坑，因此将key填入a[5]。
（3）可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。
3、平均时间复杂度：o(N*logN)
4、代码实现：
"""快速排序：【重点！！！常考！！！】
最优时间复杂度：o(nlogn) 最坏时间复杂度：o(n^2) 稳定性：不稳定"""
def quick_sort(alist,first,last):
if first>=last:
return ''
else:
mid_value=alist[first]
low=first
high=last
while low<high:
while low<high and alist[high]>=mid_value:
high-=1
alist[low]=alist[high]
while low<high and alist[low]<mid_value:
low+=1
alist[high]=alist[low]
alist[low]=mid_value #退出循环时，low=high
quick_sort(alist,first,high-1) #对左侧的列表执行快速排序
quick_sort(alist,low+1,last) #对右侧的列表执行快速排序
return alist
l=[54,26,93,17,77,31,44,55,20]
res=quick_sort(l,0,len(l)-1)
print(res) #[17, 20, 26, 31, 44, 54, 55, 77, 93]
六、归并排序
1、基本思想：
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。
首先考虑下如何将2个有序数列合并。这个非常简单，只要从比较2个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。
解决了上面的合并有序数列问题，再来看归并排序，其的基本思路就是将数组分成2组A，B，如果这2组组内的数据都是有序的，那么就可以很方便的将这2组数据进行排序。如何让这2组组内数据有序了？
可以将A，B组各自再分成2组。依次类推，当分出来的小组只有1个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的2个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。
2、过程：
3、平均时间复杂度：o(NlogN)
归并排序的效率是比较高的，设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(N*logN)。
4、代码实现
"""归并排序：【重点！！！常考！！！】
最优时间复杂度：o(nlogn) 最坏时间复杂度：o(nlogn) 稳定性：稳定"""
def merge_sort(alist):
n=len(alist)
if n<=1:
return alist
mid=n//2
left_li=merge_sort(alist[:mid]) #采用归并排序左侧的有序列表
right_li=merge_sort(alist[mid:]) #采用归并排序右侧的有序列表
left_pointer,right_pointer=0,0
result=[]
while left_pointer<len(left_li) and right_pointer<len(right_li):
if left_li[left_pointer]<=right_li[right_pointer]:
result.append(left_li[left_pointer])
left_pointer+=1
else:
result.append(right_li[right_pointer])
right_pointer+=1
result+=left_li[left_pointer:]
result+=right_li[right_pointer:] #注：在Python中，若索引超出范围，就直接返回空列表[]
return result
print(merge_sort([7,8,3,2,4,5,1,6])) #[1, 2, 3, 4, 5, 6, 7, 8]
二分法查找：【重点！！！常考！！！】在一个有序的列表中查找
def binary_search(alist,item):
n=len(alist)
if n>0:
mid=n//2
if alist[mid]==item:
return True
elif item<alist[mid]:
return binary_search(alist[:mid],item)
else:
return binary_search(alist[mid+1:],item)
else:
return False
l1=[17, 20, 26, 31, 44, 54, 55, 77]
print(binary_search(l1,30)) #False
