|
元素放左边或者右边都可以，最后使得该基数在处于数列中间位置，这个称为分区操作；
递归上述操作，完成排序，如下如；
demo：
#!/usr/bin/env python3
#_*_ coding:utf-8 _*_
#Author:wd
def quick_sort(data,left,right):
"""
快速排序
:param data: 待排序的数据列表
:param left: 基准数左边元素的索引
:param right: 基准数右边元素的索引
:return:
"""
if left < right:
mid = partition(data,left,right) # 分区操作,mid代表基数所在的索引
quick_sort(data,left,mid-1) # 对基准数前面进行排序
quick_sort(data,mid+1,right) # 对基准数后面进行排序
def partition(data,left,right):
tmp=data[left] # 随机选择的基准数,从最左边开始选
while left < right:
while left < right and data[right] >= tmp: # 右边的数比基准数大
right-=1 # 保留该数，然后索引指针往左移动
data[left]=data[right] # 否则此时右边数比基数小，则将该数放到基准位置
while left < right and data[left] <= tmp: # 右边的数比基准数小
left+=1 # 此时保持该数位置不动，索引指针往前移动
data[right]=data[left] # 否则此时左边的数比基数大，则将该数放到右边
data[left] = tmp # 最后将基准数量放回中间
return left # 返回基准数位置
if __name__=='__main__':
data_list=[1,3,21,6,50,33,34,58,66]
quick_sort(data_list,0,len(data_list)-1)
print(data_list)
###结果：[1, 3, 6, 21, 33, 34, 50, 58, 66]
堆排序
堆定义：本质是一个完全二叉树，如果根节点的值是所有节点的最小值称为小根堆，如果根节点的值是所有节点的最大值，称为大根堆。
效率：O(nlogn)
原理：
- 将待排序数据列表建立成堆结构(建立堆)；
- 通过上浮(shift_up)或下沉(shift_down)等操作得到堆顶元素为最大元素（已大根堆为例）；
- 去掉堆顶元素，将最后的一个元素放到堆顶，重新调整堆，再次使得堆顶元素为最大元素（相比第一次为第二大元素）；
- 重复3操作，直到堆为空，最后完成排序；
demo:
def sift(data, low, high):
"""
调整堆函数
:param data: 带排序的数据列表
:param low: 值较小的节点的位置，可以理解为是根节点
:param high:值较大的节点的位置
:return:
"""
i = low
j = 2 * i # 父节点i所对应的左孩子
tmp = data[i] # 最较小节点的值
while j <= high:
if j < high and data[j] < data[j + 1]: # 如果右孩子比左孩子大则把j指向右节点
j += 1 # 指向右节点
if tmp < data[j]: # 如果此时位置较小的节点值比该节点值小，则将该节点上浮最为新的父节点，并调整该节点双亲
data[i] = data[j]
i = j # 调整该节点的双亲的位置
j = 2 * i
else:
break # 否则代表本次调整已经完成，并且节点i已经无值
data[i] = tmp # 最后将被调整节点的值放到i节点上（空出的位置）
def heap_sort(data):
"""
堆排序
:param data: 待排序的数据列表
:return:
"""
n = len(data)
for i in range(n // 2 - 1, -1, -1):
sift(data, i, n - 1)
# 构建堆
for i in range(n - 1, -1, -1): # 调整过程，从最后一个元素开始交换
data[0], data[i] = data[i], data[0] # 交换
sift(data, 0, i - 1) # 开始调整
if __name__ == '__main__':
import random
data_list = [1, 3, 21, 6, 50, 33, 34, 58, 66]
random.shuffle(data_list) # 打乱列表数据
print("pre:", data_list)
heap_sort(data_list)
print("after:", data_list)
#结果：
#pre: [66, 3, 58, 34, 1, 33, 21, 6, 50]
#after: [1, 3, 6, 21, 33, 34, 50, 58, 66]
归并排序
效率：O(nlogn)
空间复杂度：O(n)
原理：
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
- 重复步骤3直到某一指针达到序列尾；
- 将另一序列剩下的所有元素直接复制到合并序列尾。
demo：
def merge(data, low, mid, high):
"""
合并函数
:param data: 数据列表
:param low: 列表开头位置
:param mid: 分割中间位置
:param high: 列表最后位置
:return:
"""
i = low # 第一个指针
j = mid + 1 # 第二个指针
tmp = [] # 临时存放的列表
while i <= mid and j <= high: # 分割的列表当两边都有数才进行
if data[i] < data[j]:
tmp.append(data[i])
i += 1 # 低的指针往右移动
else:
tmp.append(data[j]) # 右边大，存右边的数
j += 1 # 同时指针右移动
while i <= mid: # 左边分割有剩下
tmp.append(data[i])
i += 1
while j <= high: # 右边有剩下
tmp.append(data[j])
j += 1
data[low:high + 1] = tmp # 最后将tmp中的数写入到原来的列表中
|