10种排序算法
排序low B三人组
1、冒泡排序：
思路：遍历列表列表中的元素，如果当前元素比后面相邻的元素大，那么就交换，最大的数也就‘浮’在最后。
代码：
# -*- coding:utf-8 -*-
# @File : bubble_sort.py
# @Author : Clint
import random
def bubble_sort(data_list): # 冒泡排序 O(n^2)
for i in range(len(data_list)-1):
for j in range(len(data_list)-i-1):
if data_list[j] < data_list[j+1]:
data_list[j], data_list[j+1] = data_list[j+1], data_list[j]
data = list(range(100))
random.shuffle(data) # 洗牌函数，将有序的列表打乱
bubble_sort(data)
print(data) 优化后的冒泡排序
# -*- coding:utf-8 -*-
# @Author : Clint
def bubble_sort(data_list): # 优化后的冒泡排序 最好情况下的时间复杂时间是O(n)
for i in range(len(data_list)-1):
exchange = False
for j in range(len(data_list)-i-1):
if data_list[j] < data_list[j+1]:
data_list[j], data_list[j+1] = data_list[j+1], data_list[j]
exchange = True
if not exchange:
break 2、选择排序：
思路：一趟遍历最小的数，放到第一个位置；再一趟遍历剩余列表中最小的数，继续放置已排序元素后面；... 排序完成。
问题：怎么选出最小的数？
代码：
# -*- coding:utf-8 -*-
# @Author : Clint
# @File : select_sort.py
def select_sort(data_list): # 选择排序 O(n^2)
for i in range(len(data_list)-1):
min_loc = i
for j in range(i+1, len(data_list)):
if data_list[j] < data_list[min_loc]:
min_loc = j
data_list[i], data_list[min_loc] = data_list[min_loc], data_list[i]
data = [3, 5, 7, 4, 2, 6, 33, 0, 54]
select_sort(data)
print(data) 3、插入排序：
思路：列表被分为有序区和无序区两个部分，最初有序区只有一个元素（第一次元素）；从无序区遍历一个元素，在有序区从后往前扫描，找到相应位置并插入，直到无序区变空
代码：
# -*- coding:utf-8 -*-
# @Author : Clint
def insert_sort(data_list): # 插入排序 O(n^2)
for i in range(1, len(data_list)):
temp = data_list[i]
j = i-1
while j >= 0 and data_list[j] > temp:
data_list[j+1],data_list[j] = data_list[j], temp
j -= 1
data = [7,5,8,6,3,1,2,9,0]
insert_sort(data)
print(data)
# PS： 插入排序有个优化空间：应用二分查找来寻找插入点 排序NB二人组
4、堆排序：
前置知识点：
树：
1.树是一种数据库结构，如：目录结构
2.树是一种可以递归定义的数据结构
3.树是由n个节点组成的集合：
如果n=0，那这是一颗空树；
如果n>0，那存在1个节点作为树的 根节点，其他节点可以分为m个集合，每个集合本身又是一棵树。
相关概念：根节点、叶子节点；树的深度(高度)；树的度；孩子节点、父节点；子树等等；
二叉树：
二叉树的储存方式：链式储存、顺序存储(列表)
堆：
大根堆：一颗完全二叉树，满足任一节点都比其孩子节点大
小根堆：一颗完全二叉树，满足任一节点都比其孩子节点小
思路：
1.建立堆（sift）；
2.得到堆顶，为最大元素
3.去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一次调整重新使堆有序；
4.堆顶元素为第二大元素；
5.重复步骤3，直到堆变空；
代码：
# -*- coding:utf-8 -*-
# @Author : Clint
# 升序 建大根堆
def sift(data_list, low, high):
i = low # 最开始的父节点
j = 2*i+1 # 最开始的左子节点
tmp = data_list[i]
while j <= high: # 如果子节点没到子树的最后，那么继续
if data_list[j] < data_list[j+1] and j+1 <= high:
j += 1
if tmp < data_list[j]: # 如果父节点比子节点小
data_list[i] = data_list[j] # 那么父子节点互换
i = j # 字节点成为父节点
j = 2*i+1 # 新子节点
else:
break
data_list[i] = tmp
def heap_sort(data_list):
n = len(data_list)
for i in range(n//2 - 1, -1, -1):
sift(data_list, i, n-1)
# 堆建好了
for i in range(n-1, -1, -1): # i指向堆的最后
data_list[0], data_list[i] = data_list[i], data_list[0] # 父节点出局，堆的最后叶子节点上位
sift(data_list, 0, i-1) # 调整出新的父节点
data = [7, 5, 8, 6, 3, 1, 2, 9, 0]
heap_sort(data)
print(data) # 升序排列，若要降序排列，则建小根堆即 5、归并排序
思路：
1.将列表越分越小，直至分成一个元素；
2.把一个元素理解成是是有序的；
3.合并：将两个有序列表归并，列表越来越大；
代码：
# -*- coding:utf-8 -*-
# @Author : Clint
import sys
import random
sys.setrecursionlimit(10000) # python最大递归数为999
def one_merge(data_list, low, mid, high): # 一次归并
i = low
j = mid + 1
lda = []
while i <= mid and j <= high:
if data_list[i] < data_list[j]:
lda.append(data_list[i])
i += 1
else:
lda.append(data_list[j])
j += 1
while i <= mid:
lda.append(data_list[i])
i += 1
while j <= high:
lda.append(data_list[j])
j += 1
data_list[low:high+1] = lda
def merge_sort(data_list, low, high): # 合并排序 O(nlogn)
if low < high:
mid = (low + high)//2
merge_sort(data_list, low, mid) # 递归实现
merge_sort(data_list, mid+1, high)
one_merge(data_list, low, mid, high)
data = list(range(100))
random.shuffle(data) # 洗牌函数，将有序的列表打乱
print(data)
merge_sort(data, 0, len(data)-1)
print(data) 其他更优方案
6、快速排序：
思路：取一个元素p（第一个元素），使元素p归位；列表被p分成两部分，左边都比p小，右边都比p大；递归完成排序
算法关键点：1.整理；2.递归
代码：
# -*- coding:utf-8 -*-
# @Author : Clint
def quick_sort(data_list, left, right): # 快速排序 O(nlogn)
if left < right:
mid = partition(data_list, left, right)
quick_sort(data_list, left, mid-1)
quick_sort(data_list, mid+1, right)
def partition(data_list, left, right):
temp = data_list[left]
while left < right:
while left < right and data_list[right] >= temp:
right -= 1
data_list[left] = data_list[right]
while left < right and data_list[left] <= temp:
left += 1
data_list[right] = data_list[left]
data_list[left] = temp
return left
data = [7, 5, 8, 6, 3, 1, 2, 9, 0]
quick_sort(data, 0, len(data)-1)
print(data) 7、希尔排序
实质上是一种分组的插入排序；
思路：
1.首先取一个整数d1 = n / 2，将元素分为d1个组，每组相邻的元素之间距离为d1，在各组内进行直接插入排序；
2.取第二个整数d2 = d1 / 2 ，重复上述分组排序过程，直到 di = 1，既所有元素在同一组内进行直接插入排序；
PS：希尔排序每趟并不使某些元素有序，而是使整体数据越来越接近有序；最后一趟排序使得所有数据有序。
代码：
# -*- coding:utf-8 -*-
# @Author : Clint
def shell_sort(data_list): # 希尔排序 O（n(1+T)）
gap = len(data_list) // 2
while gap > 0:
for i in range(gap, len(data_list)):
temp = data_list[i]
j = i-gap
while j >= 0 and temp < data_list[j]:
data_list[j+gap] = data_list[j]
j -= gap
data_list[j+gap] =temp
gap /= 2 
千里马应驰骋广阔天地，而非困于逼仄马厩。你有更大的舞台，莫执着于这破公司
