1.冒泡排序
2.选择排序
3.插入排序
4.希尔排序
5.快速排序
6.归并排序
7.二分查找算法
排序算法是将一串数据按照特定的顺序进行排列的算法。排序过程中涉及的排序算法稳定性是指，让原本有相等键值的记录维持原有相对次序，如对元组(4,1) (3,7) (3,1) (5,6)按照第一个值进行排序时，(3,7) (3,1)的第一个值相同，如果排序后，依然是(3,7) (3,1)，则称为稳定的。
注：笔记中排序均为左小右大。
1 .冒泡排序
冒泡排序是将每次冒泡过程，将最大值（或最小值）一直挪到一端，这样的冒泡过程要执行n-1次，下图为一次冒泡过程：
执行过程（右大左小）：
①比较相邻两个元素，如果左比右大，就交换位置
②重复对相邻的两个元素执行①，直到最后一对被比较，此时，最大的元素将会在最右端
③除了最后一个元素，重复①②
④除了最后两个元素，重复①②
⑤...
⑥直到所有元素排序完成
# coding:utf-8
def bubble_sort(alist):
n = len(alist)
for i in range(n-1):
for j in range(n-1-i):
if alist[j] > alist[j+1]:
alist[j],alist[j+1] = alist[j+1],alist[j]
return alist
if __name__ == "__main__":
ll = [32,41,1,8,89,12,56,45,3,]
print(ll)
print(bubble_sort(ll))
这个算法的时间复杂度为O(n2)，如果原本是一个已经有序的列表，再进行排序，依然需要全部遍历比较一遍，所以针对这种情况进行优化：
# coding:utf-8
def bubble_sort(alist):
n = len(alist)
for i in range(n-1):
count = 0
for j in range(n-1-i):
if alist[j] > alist[j+1]:
alist[j],alist[j+1] = alist[j+1],alist[j]
count += 1
if 0 == count:
return alist
return alist
if __name__ == "__main__":
ll = [32,41,1,8,89,12,56,45,3,]
print(ll)
print(bubble_sort(ll))
此时最优复杂度为O(n)，稳定
2 .选择排序
选出列表中最小值，将其放置到前面：
先假设下标为0的值最小，依次向后比较，发现比下标为0的值小的数就将值交换，交换完继续扫描比较，直到比较完成
然后第一个值不变，重复前述比较，直到所有元素有序
# coding:utf-8
def selected_sort(alist):
n = len(alist)
for i in range(n-1):
min = i
for j in range(i + 1,n):
if alist[j] < alist[min]:
min = j
alist[i],alist[min] = alist[min],alist[i]
return alist
if __name__ == "__main__":
ll = [12,48,3,44,5,48,4,11,3,7]
print(selected_sort(ll))
最优复杂度和最坏复杂度均为O(n2)，不稳定
3 .插入排序
①第一轮：插入算法将第0个元素假定为有序，比较第1个和第0个元素，如果比第0个小则交换
emsp; ②第二轮：此时第0、1个元素有序，将第2个元素与前两个依次比较，将其插入到前面有序位置，重复。
# coding:utf-8
def insert_sort(alist):
n = len(alist)
for i in range(1,n):
# min = i
# for j in range(i-1,-1,-1):
# if alist[min] < alist[j]:
# alist[min],alist[j] = alist[j],alist[min]
# min = j
j = i
while j > 0:
if alist[j] < alist[j - 1]:
alist[j],alist[j - 1] = alist[j - 1],alist[j]
j -= 1
else:
break
return alist
if __name__ == "__main__":
ll = [12,48,3,44,5,48,4,11,3,7]
print(insert_sort(ll))
如果采用注释掉的代码来执行插入排序，很明显，无论前面有序部分是否比当前比较数字小，都需要执行一遍比较，完全失去了插入比较的意义，更类似于选择排序。而采用while循环语句部分，则可在当前数字较大时退出while循环，算法更优，更具插入特性。
其最优复杂度为O(n)，最坏复杂度为O(n2)，稳定。
4 .希尔排序
取一个步长gap，将数组按gap切断并列成行，每一列作为子列进行插入排序。所有子列插入排序完成后，缩小gap重复。在代码实现过程中实际上并未真的将数组进行了切分，未引入额外的内存空间，而是在整个数组中执行的：
# coding:utf-8
import random
def shell_sort(alist):
n = len(alist)
gap = n // 2
while gap > 0:
for i in range(gap,n):
j = i
while j > 0:
if alist[j] < alist[j-gap]:
alist[j],alist[j-gap] = alist[j-gap],alist[j]
j -= gap
else:
break
gap //= 2
return alist
if __name__ == "__main__":
ll = [random.randint(0,100) for i in range(10) ]
print(ll)
print(shell_sort(ll))
最优时间复杂度根据步长序列的不同而不同（统计平均值为O(n1.3)），最坏时间复杂度为O(n2)，不稳定。插入排序即希尔排序gap=1时的例子。
5 .快速排序
快速排序的原理如下图所示：绿色框内值将是无意义值，在low或high停止后，将被low或high指向的值占据，棕色框内值即为占据绿色框的值，红色框为指针重合时的位置，选取的中间值将存放在该位置，即将该值排好序，对红色值两边分别再重复下图中操作，直到所有值被排序。
代码思路：
首先将一轮排序写出来：
def quick_sort(alist):
n = len(alist)
mid_val = alist[0]
low = 0
high = n - 1
while low < high:
while low < high and alist[high] >= mid_val:
high -= 1
alist[low] = alist[high]
while low < high and alist[low] < mid_val:
low += 1
alist[high] = alist[low]
alist[low] = mid_val
如果采用切片的方式将列表传递给快排函数递归：
quick_sort(alist[:low])
quick_sort(alist[low+1:])
这是不合适的，因为切片的方式相当于创建了一个新的列表，与原列表将没有关系，我们希望的是在原有列表上进行操作，所以需要对快排函数进行修改，给快排函数传递两个参数，用于标识初始的low、high游标位置：
# coding:utf-8
import random
def quick_sort(alist,first,last):
#if 语句为递归终止判别
if first >= last:
return
mid_val = alist[first]
low = first
high = last
while low < high:
#循环交替判断high、low上的值
while low < high and alist[high] >= mid_val:
high -= 1
alist[low] = alist[high]
while low < high and alist[low] < mid_val:
low += 1
alist[high] = alist[low]
#当low和high重合时将中间值赋予重合坐标
alist[low] = mid_val
#一轮排序结束后，进行递归：
quick_sort(alist,first,low - 1)
quick_sort(alist,low + 1,last)
if __name__ == "__main__":
ll = [random.randint(0,100) for x in range(10)]
print(ll)
quick_sort(ll,0,len(ll) - 1)
print(ll)
最优时间复杂度为O(nlogn)，每次中间值的位置刚好在正中间，最坏时间复杂度为O(n2)，每次中间值的位置刚好在第一个，不稳定。
6 .归并排序
如下图所示，归并排序的思想是将列表拆分至只有一个元素，按照拆分的顺序反向合并，合并时小的在前。第二次合并开始，每一组元素至少有两个元素，通过两个游标来标记，比较两个游标指向的元素，先取出小的放在前面，然后游标右移，重复。
如下图，实际代码执行时，递归的比较前2，4，8，...，n个元素，最后实现所有元素排序。
# coding:utf-8
import random
def merge_sort(alist):
if len(alist) <= 1:
return alist
mid = len(alist) // 2
left = merge_sort(alist[:mid])
right = merge_sort(alist[mid:])
left_point,right_point = 0,0
result = []
while left_point < len(left) and right_point < len(right):
if left[left_point] <= right[right_point]:
result.append(left[left_point])
left_point += 1
else:
result.append(right[right_point])
right_point += 1
result.extend(left[left_point:])
result.extend(right[right_point:])
return result
if __name__ == "__main__":
ll = [random.randint(0,100) for x in range(10)]
print(ll)
print(merge_sort(ll))
列表传递进入函数后，只要判定列表大于一个元素，都切半传递进入merge_sort()，如下图，只有同一分支下同一级都有了返回结果才会执行比较，否则将一直重复执行递归函数。
执行完①后阻塞，并不执行⑦，进入①后，先执行②，发现只有一个元素，直接返回列表。
开始执行③，进入③后，先执行⑤，返回列表，执行③里的⑥，返回列表，此时递归函数都有了返回值，开始执行③内的比较代码，然后③有了返回结果。
由于②③都有了返回结果，开始执行①内的比较代码，返回①代码结果
开始执行⑦，....
实际执行过程如同上面动态图所示。
7. 二分查找算法
对于一个无须列表，如果进行查找，按照顺序查找比对即可，但是对于有序的列表，如果依然按照顺序查找比对，这样的效率是比较低的。二分查找算法，直接与列表中间值比对，最优的情况一下，一次比对即返回结果。如果查找的值小于列表的中间值，则在列表左边执行二分查找，如果大于则在右边执行查找，代码实现如下：
# coding:utf-8
def binary_search(alist,item):
if len(alist) > 0:
mid = len(alist) // 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)
return False
if __name__ == "__main__":
li = [1,3,4,5,9,10,25,34,87,100,401,506]
print(binary_search(li,34))
非递归实现：
def binary_search(alist,item):
first = 0
last = len(alist) - 1
while first <= last:
mid = (first + last) // 2
if alist[mid] == item:
return True
elif item < alist[mid]:
last = mid - 1
else:
first = mid + 1
return False
最优时间复杂度为O(1)，最坏时间复杂度为O(logn)
