排序算法总结
冒泡排序：
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
def bubbleSort(nums):
for i in range(len(nums) - 1): # 遍历 len(nums)-1 次
for j in range(len(nums) - i - 1): # 已排好序的部分不用再次遍历
if nums[j] > nums[j+1]:# Python 交换两个数不用中间变量
nums[j], nums[j+1] = nums[j+1], nums[j] # Python 交换两个数不用中间变量
return nums
选择排序：
从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
def selectionSort(nums):
for i in range(len(nums) - 1): # 遍历 len(nums)-1 次
minIndex = i
for j in range(i + 1, len(nums)):
if nums[j] < nums[minIndex]: # 更新最小值索引
minIndex = j
nums[i], nums[minIndex] = nums[minIndex], nums[i] # 把最小数交换到前面
return nums
插入排序：
从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
def insertionSort(nums):
for i in range(len(nums) - 1): # 遍历 len(nums)-1 次
curNum, preIndex = nums[i+1], i # curNum 保存当前待插入的数
while preIndex >= 0 and curNum < nums[preIndex]: # 将比 curNum 大的元素向后移动
nums[preIndex + 1] = nums[preIndex]
preIndex -= 1
nums[preIndex + 1] = curNum # 待插入的数的正确位置
return nums
希尔排序：
希尔排序是插入排序的高效实现，对简单插入排序减少移动次数优化而来。简单插入排序每次插入都要移动大量数据，前后插入时的许多移动都是重复操作，若一步到位移动效率会高很多。若序列基本有序，简单插入排序不必做很多移动操作，效率很高。
希尔排序将序列按固定间隔划分为多个子序列，在子序列中简单插入排序，先做远距离移动使序列基本有序；逐渐缩小间隔重复操作，最后间隔为1时即简单插入排序。
希尔排序对序列划分O(n)次，每次简单插入排序O(logn)，时间复杂度O(nlogn)
def shellSort(nums):
lens = len(nums)
gap = 1
while gap < lens // 3:
gap = gap * 3 + 1 # 动态定义间隔序列
while gap > 0:
for i in range(gap, lens):
curNum, preIndex = nums[i], i - gap # curNum 保存当前待插入的数
while preIndex >= 0 and curNum < nums[preIndex]:
nums[preIndex + gap] = nums[preIndex] # 将比 curNum 大的元素向后移动
preIndex -= gap
nums[preIndex + gap] = curNum # 待插入的数的正确位置
gap //= 3 # 下一个动态间隔
return nums
归并排序：
作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：
- 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第2种方法）
- 自下而上的迭代
def mergeSort(nums):
# 归并过程
def merge(left, right):
result = [] # 保存归并后的结果
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result = result + left[i:] + right[j:] # 剩余的元素直接添加到末尾
return result
# 递归过程
if len(nums) <= 1:
return nums
mid = len(nums) // 2
left = mergeSort(nums[:mid])
right = mergeSort(nums[mid:])
return merge(left, right)
快速排序：（两种写法）
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)
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
堆排序：
堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
大根堆：每个节点的值都大于或等于其子节点的值，用于升序排列；
小根堆：每个节点的值都小于或等于其子节点的值，用于降序排列。
将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
创建最大堆:将堆所有数据重新排序，使其成为最大堆
最大堆调整:作用是保持最大堆的性质，是创建最大堆的核心子程序
堆排序:移除位在第一个数据的根节点，并做最大堆调整的递归运算
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) # 对所有非叶子结点进行堆的调整
# 堆排序
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 是从小到大排列
计数排序：
计数排序用待排序的数值作为计数数组（列表）的下标，统计每个数值的个数，然后依次输出即可。计数数组的大小取决于待排数据取值范围，所以对数据有一定要求，否则空间开销无法承受。
计数排序只需遍历一次数据，在计数数组中记录，输出计数数组中有记录的下标，时间复杂度为O(n+k)。额外空间开销即指计数数组，实际上按数据值分为k类（大小取决于数据取值），空间复杂度O(k)。
def countingSort(nums):
bucket = [0] * (max(nums) + 1) # 桶的个数
for num in nums: # 将元素值作为键值存储在桶中，记录其出现的次数
bucket[num] += 1
i = 0 # nums 的索引
for j in range(len(bucket)):
while bucket[j] > 0:
nums[i] = j
bucket[j] -= 1
i += 1
return nums
桶排序：
桶排序实际上是计数排序的推广，但实现上要复杂许多。桶排序先用一定的函数关系将数据划分到不同有序的区域（桶）内，然后子数据分别在桶内排序，之后顺次输出。当每一个不同数据分配一个桶时，也就相当于计数排序。
假设n个数据，划分为k个桶，桶内采用快速排序，时间复杂度为O(n)+O(k * n/klog(n/k))=O(n)+O(n(log(n)-log(k))),显然，k越大，时间复杂度越接近O(n)，当然空间复杂度O(n+k)会越大，这是空间与时间的平衡。
def bucketSort(nums, defaultBucketSize = 5):
maxVal, minVal = max(nums), min(nums)
bucketSize = defaultBucketSize # 如果没有指定桶的大小，则默认为5
bucketCount = (maxVal - minVal) // bucketSize + 1 # 数据分为 bucketCount 组
buckets = [] # 二维桶
for i in range(bucketCount):
buckets.append([])
# 利用函数映射将各个数据放入对应的桶中
for num in nums:
buckets[(num - minVal) // bucketSize].append(num)
nums.clear() # 清空 nums
# 对每一个二维桶中的元素进行排序
for bucket in buckets:
insertionSort(bucket) # 假设使用插入排序
nums.extend(bucket) # 将排序好的桶依次放入到 nums 中
return nums
基数排序：
基数排序进行多轮按位比较排序，轮次取决于最大数据值的位数。先按照个位比较排序，然后十位百位以此类推，优先级由低到高，这样后面的移动就不会影响前面的。基数排序按位比较排序实质上也是一种划分，一种另类的‘桶’罢了。比如，第一轮按各个位比较，按个位大小排序分别装入10个‘桶’中，‘桶’中个位相同的数据视作相等，桶是有序的，按序输出，后面轮次接力完成排序。
基数排序‘桶’内数据在划分桶时便已排序O(n)，k个桶，时间复杂度为O(n*k)。额外空间开销出在数据划分入桶过程，桶大小O(n+k)，空间复杂度O(n+k)。
def radixSort(nums):
mod = 10
div = 1
mostBit = len(str(max(nums))) # 最大数的位数决定了外循环多少次
buckets = [[] for row in range(mod)] # 构造 mod 个空桶
while mostBit:
for num in nums: # 将数据放入对应的桶中
buckets[num // div % mod].append(num)
i = 0 # nums 的索引
for bucket in buckets: # 将数据收集起来
while bucket:
nums[i] = bucket.pop(0) # 依次取出
i += 1
div *= 10
mostBit -= 1
return nums
