排序：内部和外部
内部排序：数据记录在内存中进行排序。
外部排序：排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。
图1.
几种排序算法的比较：
图2.
n：数据规模
k：“桶”的个数
In-place：占用常数内存，不占用额外内存
Out-place：占用额外内存
稳定性：排序后2个相等键值的顺序和排序之前它们的顺序相同
交换排序
1.冒泡排序
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数
- 针对所有的元素重复以上的步骤，除了最后一个
- 重复步骤1~3，直到排序完成。
python实现：
def BubbleSort(lst):
n=len(lst)
if n<=1:
return lst
for i in range (n):
for j in range(n-i-1):
if lst[j] > lst[j+1]:
lst[j],lst[j+1] = lst[j+1],lst[j] #Python交换两个数不用中间变量
return lst
如图3.冒泡排序对n个数据操作n-1轮，每轮找出一个最大（小）值。操作只对相邻两个数比较与交换，每轮会将一个最值交换到数据列首（尾），像冒泡一样。每轮操作O(n)次，共O(n)轮，时间复杂度O(n^2)。空间复杂度O(1)。
图3.冒泡排序
2.快速排序
- 从数列中选出一个元素，称为 “基准”（pivot）
- 重新排序数列，比基准值小元素的放在基准前面，比基准大的放在基准的后面（相同的数可以到任一边）。
- 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
python实现：
def quickSort(nums): # 这种写法的平均空间复杂度为 O(nlogn)
if len(nums) <= 1:
return nums
pivot = nums[0] # 基准值
left = [nums[i] for i in range(1, len(nums)) if nums[i] < pivot]
right = [nums[i] for i in range(1, len(nums)) if nums[i] >= pivot]
return quickSort(left) + [pivot] + quickSort(right)
'''
@param nums: 待排序数组
@param left: 数组上界
@param right: 数组下界
'''
def quickSort2(nums, left, right): # 这种写法的平均空间复杂度为 O(logn)
# 分区操作
def partition(nums, left, right):
pivot = nums[left] # 基准值
while left < right:
while left < right and nums[right] >= pivot:
right -= 1
nums[left] = nums[right] # 比基准小的交换到前面
while left < right and nums[left] <= pivot:
left += 1
nums[right] = nums[left] # 比基准大交换到后面
nums[left] = pivot # 基准值的正确位置，也可以为 nums[right] = pivot
return left # 返回基准值的索引，也可以为 return right
# 递归操作
if left < right:
pivotIndex = partition(nums, left, right)
quickSort2(nums, left, pivotIndex - 1) # 左序列
quickSort2(nums, pivotIndex + 1, right) # 右序列
return nums
图4.快速排序
插入排序
1.简单插入排序
2.希尔排序
选择排序
1.简单选择排序
2.堆排序
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
- 大顶堆：每个节点的值都大于或等于其子节点的值，用于升序排列。
- 小顶堆：每个节点的值都小于或等于其子节点的值，用于降序排列。
- 对于升序排列，首先构建大顶堆，此堆为初始的无序序列。
- 将堆顶与堆底最后一个元素交换。将无序元素重新构建成大顶堆。
- 反复执行至序列有序。
堆排序
Python实现：
# 大顶堆（升序排列）
def heapSort(nums):
# 调整堆
def adjustHeap(nums, i, size):
# 非叶子结点的左右两个孩子
lchild = 2 * i + 1
rchild = 2 * i + 2
# 在当前结点、左孩子、右孩子中找到最大元素的索引
largest = i
if lchild < size and nums[lchild] > nums[largest]:
largest = lchild
if rchild < size and nums[rchild] > nums[largest]:
largest = rchild
# 如果最大元素的索引不是当前结点的索引，把大的结点交换到上面，继续调整堆
if largest != i:
nums[largest], nums[i] = nums[i], nums[largest]
# 第 2 个参数传入 largest 的索引是交换前大数字对应的索引
# 交换后该索引对应的是小数字，应该把该小数字向下调整
adjustHeap(nums, largest, size)
# 建立堆
def builtHeap(nums, size):
for i in range(len(nums)//2)[::-1]: # 从倒数第一个非叶子结点开始建立大顶堆
adjustHeap(nums, i, size) # 对所有非叶子结点进行堆的调整
# print(nums) # 第一次建立好的大顶堆
# 堆排序
size = len(nums)
builtHeap(nums, size)
for i in range(len(nums))[::-1]:
# 每次根结点都是最大的数，最大数放到后面
nums[0], nums[i] = nums[i], nums[0]
# 交换完后还需要继续调整堆，只需调整根节点，此时数组的 size 不包括已经排序好的数
adjustHeap(nums, 0, i)
return nums # 由于每次大的都会放到后面，因此最后的 nums 是从小到大排列
