排序分类
- 比较类排序（非线性时间比较类排序）：通过比较决定元素之间的相对次序，时间复杂度不能突破O(nlogn)
- 非比较排序（线性时间非比较排序）：不通过比较决定元素之间的相对次序，突破了基于比较排序的时间下界，以线性时间运行
算法复杂相关基础
- 时间复杂度：对排序数据的总的操作次数，反应当n变化时，操作次数呈现什么规律
- 时间复杂度（平均）
- 时间复杂度（最好）
- 时间复杂度（最坏）
- 空间复杂度：算法在计算机内执行时所需存储空间的度量，数据规模n的函数
- 稳定性：相邻的相同两元素排序之后位置变化就是不稳定的， 不变就是稳定的
比较排序
-
冒泡排序
比较相邻两元素，第一个比第二个大，就交换他们，最后的元素应该是最大数（用小于号就是降序）
正序时，最快；反序时，最慢。
遍历次数n-1次
def bubbleSort(a_list):
# 外层循环 设置循环次数 列表长度-1，
for i in range(len(a_list) - 1):
# 内层循环 屏蔽已排序的部分
for j in range(len(a_list) - i - 1):
# 就近数据比较
if a_list[j] > a_list[j + 1]:
# 符合要求就交换（元组解包）
a_list[j], a_list[j + 1] = a_list[j + 1], a_list[j]
# 返回列表
# return nums
print(a_list)
a_list = [3, 2, 5, 62, 3, 6, 73, 34, 767, 3, 34]
bubbleSort(a_list)
- 选择排序
首先寻找最（小）大元素，存放起始位置，然后再从剩余元素中继续寻找极值放到之前极值后面(需要极值的下标)
选择排序不受输入数据影响，即在任何情况下时间复杂度不变
遍历次数n-1次
def selectSort(a_list):
# 外层循环设置 循环长度-1次
for i in range(len(a_list) - 1):
# 定义最小值下标
minIndex = i
# 设置内层循环区间，屏蔽前面排好的部分
for j in range(i + 1, len(a_list)):
# 如果有值比前面的小
if a_list[j] < a_list[minIndex]:
# 替换最小值的下标
minIndex = j
# 元组解包交换值
a_list[i], a_list[minIndex] = a_list[minIndex], a_list[i]
# return a_list
print(a_list)
a_list = [2, 34, 5, 62, 43, 655, 984, 532, 2]
selectSort(a_list)
- 插入排序
构建有序数列（第一个元素可以认为是有序数列），未排序的数据，在已排序的序列中从后往前扫描，找到合适的位置插入。
优化算法，拆半拆入（感觉像是与二分法查找结合了，减少了比较次数，元素移动次数没变）
时间复杂度O（n^2）
def insertionSort(a_list):
# 设置循环次数
for i in range(len(a_list) - 1):
# 定义待插入数和比这个数大的数的下标
curNum, preIndex = a_list[i + 1], i
# 第二个数开始为待插入数和前面数比较
while preIndex >= 0 and curNum < a_list[preIndex]:
# 条件成立比较数位置的数后移一位
a_list[preIndex + 1] = a_list[preIndex]
# 重置指针
preIndex -= 1
# 待插入数的正确位置位置
a_list[preIndex + 1] = curNum
print(a_list)
# return a_list
a_list = [12, 4, 565, 23, 345, 634, 4, 6, 34, 32]
insertionSort(a_list)
- 希尔排序
希尔排序在插入排序的基础上增加一个叫增量的概念。那什么增量？插入排序只能与相邻的元素进行比较，而希尔排序则是进行跳跃比较，而增量就是步长。比如增量为3时，下标为0的元素与下标为3的元素比较，3再与6比较，1与4比较，4再与7比较……比较完后，再去减少增量，重复之前步骤，直到增量为1，此时只有一个分组了，再对这一个分组进行插入排序，整个希尔排序就结束了。
个人理解： 就是按下标步长分组重新排列数组，对每个分组进行插入排序，然后缩小步长，继续分组，排序，当步长为1时，数组排序结束
简书著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。
简单插入排序的改进版，第一个突破O(n²)的算法
实质是分组插入排序，与插入排序不同在于，它会优先比较距离较远的元素（缩小增量排序）
希尔排序的核心在于间隔序列的设定：提前设定间隔序列和动态定义间隔序列
def shellSort(a_list):
# 定义增量
increment = 1
# 动态定义增量间隔序列
while increment < len(a_list) // 3:
increment = increment * 3 + 1 #
while increment > 0:
for i in range(increment, len(a_list)):
# 当前插入的数,被插入数的下标
curNum, preIndex = a_list[i], i - increment
# 比较
while preIndex >= 0 and curNum < a_list[preIndex]:
# 将比插入数大的元素后移
a_list[preIndex + increment] = a_list[preIndex]
# 下标复位
preIndex -= increment
# 保证待插入的数的正确位置
a_list[preIndex + 1] = curNum
# 设置下一个动态间隔
increment //= 3
# return a_list
print(a_list)
a_list = [1, 2, 4, 12, 34, 56, 23, 4, 64, 32, 23, 23]
shellSort(a_list)
- 归并排序
自上而下的递归和自下而上的迭代（所有的递归都可以用迭代重写）
长度为n的序列，分为n/2的子列，递归下分，从最小单位两两排序，最后将两个排序好的子列合并
不受输入数据影响，时间复杂度：始终都是O(n log n），需要使用额外的内存空间
def mergeSort(a_list):
# 归并过程
def merge(left, right):
result = [] # 保存归并之后的结果
# 定义子列长度
i = j = 0
# 设置循环条件
while i < len(left) and j < len(right):
# 左面小，保存左面，条件+1
if left[i] <= right[j]:
result.append(left[i])
i += 1
# 右面小保存右面，条件+1
else:
result.append(right[j])
j += 1
# 剩余元素追加到末尾
result += (left[i:] + right[j:])
return result
# 递归过程
if len(a_list) <= 1:
return a_list
mid = len(a_list) // 2
left = mergeSort(a_list[:mid])
right = mergeSort(a_list[mid:])
return merge(left, right)
a_list = [1, 3, 3, 52, 35, 6, 4, 75, 34, 23]
result = mergeSort(a_list)
print(result)
- 快速排序
冒泡排序基础上的递归分治法，处理大数据最快的排序算法之一
设置基准值，通过一趟排序将待排记录分区=比基准值小的放左面，大的放右面，递归排序子数列
不稳定的排序，最好的内排序，东拆西补或西拆东补，一边拆一边补，直到所有元素达到有序状态。
写法一：平均空间复杂度为O(nlonn)
def quickSort(a_list):
if len(a_list) <= 1:
return a_list
pivot = a_list[0]
# 生成式写法
# left = [a_list[i] for i in range(1,len(a_list)) if a_list[i] < pivot]
# right = [a_list[i] for i in range(1,len(a_list)) if a_list[i] >= pivot]
# 常规写法
left = []
right = []
for i in range(1, len(a_list)):
if a_list[i] < pivot:
left.append(a_list[i])
if a_list[i] >= pivot:
right.append(a_list[i])
return quickSort(left) + [pivot] + quickSort(right)
a_list = [2, 3, 4, 2, 3, 41, 34, 656, 7, 45, 34, 45]
print(quickSort(a_list))
写法二：平均空间复杂度为 O(logn)
def quickSort(a_list, left, right):
"""
:param a_list: 待排序数组
:param left: 数组上界 这里是0？
:param right: 数组下界 这里是数组长度-1？
:return:
"""
# 分区
def partition(a_list, left, right):
# 设置基准值
pivot = a_list[left]
while left < right:
while left < right and a_list[right] >= pivot:
# 条件成立，右侧指针左移一位
right -= 1
# 比基准值小的交换到基准前面
a_list[left] = a_list[right]
while left < right and a_list[left] <= pivot:
left += 1
# 比基准值大的交换到基准后面面
a_list[right] = a_list[left]
# 校验基准，也可以是a_list[right] = pivot
a_list[left] = pivot
# 返回基准索引 return right
return left
# 递归
if left < right:
pivotIndex = partition(a_list, left, right)
# 左序列
quickSort(a_list, left, pivotIndex - 1)
# 右序列
quickSort(a_list, pivotIndex + 1, right)
return a_list
a_list = [23, 4, 34, 54, 23, 43, 34, 54, 657, 34, 2, 232]
print(quickSort(a_list, 0, len(a_list) - 1))
- 堆排序
- 大根堆：每个节点的值都大于或等于其子节点的值，用于升序排列；
- 小根堆：每个节点的值都小于或等于其子节点的值，用于降序排列。
堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。
（大顶堆）构造初始堆，将堆顶元素与末尾元素进行交换，使末尾元素最大，然后继续调整堆，再将堆顶元素与末尾元素交换，得到次大值，如此反复交换、重建、交换
# 大根堆（升序排列）
def heapSort(a_list):
# 调整堆
def adjustHeap(a_list, i, size):
# 定义非叶子节点的左右子节点
lchild = 2 * i + 1
rchild = 2 * i + 2
# 当前节点和左右子节点中找到最大元素的索引
# 最大元素索引
largest = i
if lchild < size and a_list[lchild] > a_list[largest]:
largest = lchild
if rchild < size and a_list[rchild] > a_list[largest]:
largest = rchild
if largest != i:
a_list[largest], a_list[i] = a_list[i], a_list[largest]
# 交换后该索引对应的小数字向下调整
adjustHeap(a_list, largest, size)
# 建立堆
def buildHeap(a_list, size):
for i in range(len(a_list) // 2)[::-1]:
adjustHeap(a_list, i, size)
# 堆排序
size = len(a_list)
buildHeap(a_list, size)
for i in range(len(a_list))[::-1]:
# 每次根节点都是最大数，最大数放后面
a_list[0], a_list[i] = a_list[i], a_list[0]
# 交换完成后调整堆，只需要调整根节点，size不包括已排序的数
adjustHeap(a_list, 0, i)
return a_list
a_list = [23, 52, 35, 23, 212, 34, 51, 34, 5, 78, 34, 512, 12, 123, 243]
a = heapSort(a_list)
print(a)
# 小根堆（降序序排列）
def heapSort(a_list):
# 调整堆
def adjustHeap(a_list, i, size):
# 定义非叶子节点的左右子节点
lchild = 2 * i + 1
rchild = 2 * i + 2
# 当前节点和左右子节点中找到最小元素的索引
# 最小元素索引
smallest = i
if lchild < size and a_list[lchild] < a_list[smallest]:
smallest = lchild
if rchild < size and a_list[rchild] < a_list[smallest]:
smallest = rchild
if smallest != i:
a_list[smallest], a_list[i] = a_list[i], a_list[smallest]
# 交换后该索引对应的大数字向下调整
adjustHeap(a_list, smallest, size)
# 建立堆
def buildHeap(a_list, size):
for i in range(len(a_list) // 2)[::-1]:
adjustHeap(a_list, i, size)
# 堆排序
size = len(a_list)
buildHeap(a_list, size)
for i in range(len(a_list))[::-1]:
# 每次根节点都是最小数，最小数放后面
a_list[0], a_list[i] = a_list[i], a_list[0]
# 交换完成后调整堆，只需要调整根节点，size不包括已排序的数
adjustHeap(a_list, 0, i)
return a_list
a_list = [23, 52, 35, 23, 212, 34, 51, 34, 5, 78, 34, 512, 12, 123, 243]
a = heapSort(a_list)
print(a)
非比较排序
- 计数排序
输入数据作为健存储在额外开辟的数组空间中，计数排序要求输入的数据必须是有确定范围的整数。
先找出最大最小元素，然后统计每个值i出现的次数，存入额外数组的第i项，然后累加计数，最后反向填充额外定义的数组（每个元素i放在额外数组（i）项，每放一个元素额外数组(i)-1）
def countingSort(a_list):
bucket = [0] * (max(a_list) + 1) # 桶的个数
for num in a_list:
# 元素值为键存入桶中，并记录出现的次数
bucket[num] += 1
i = 0 # 待排序数组的索引
for j in range(len(bucket)):
while bucket[j] > 0:
# 反向填充目标数组：将每个元素j放在新数组的第C(j)项，每放一个元素就将C(j)减去1
a_list[i] = j
bucket[j] -= 1
i += 1
return a_list
a_list = [2, 23, 5, 23, 35, 3, 34, 23, 3, 54, 34, 23, 423, 234, 24, 234, 24, 432, 32]
a = countingSort(a_list)
print(a)
- 桶排序
计数排序的升级版。利用函数映射关系，高效与否的关键在于映射函数的确定。
桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
先设置定量数组为空桶，遍历数据将数据一一放入对应的桶中，对非空桶排序，拼接桶中排序好的数据
为了使桶排序更加高效，我们需要做到这两点：
- 在额外空间充足的情况下，尽量增大桶的数量
- 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
输入数据可以均匀的分配到每个桶中时候最快，输入数据被分到同一个桶中最慢
def bucketSort(a_list, defaultBucketSize=5):
# 确认最大最小值
maxVal, minVal = max(a_list), min(a_list)
# 指定桶的大小，没指定就用默认的
bucketSize = defaultBucketSize
# 数据分组的桶个数
bucketCount = (maxVal - minVal) // bucketSize + 1
# 二维桶
buckets = []
for num in range(bucketCount):
buckets.append([])
# 利用函数映射将各个数据对应放入桶中
for i in a_list:
buckets[(i - minVal) // bucketSize].append(i)
a_list.clear() # 清空原待排序数组
# 对每一个二维桶中的元素进行排序
for bucket in buckets:
# 选择排序方法， 假设用的插入排序,也可以直接调用之前的定义好的排序方法insertionSort(bucket)
for a in range(len(bucket) - 1): # 遍历 len(nums)-1 次
curNum, preIndex = bucket[a + 1], a # curNum 保存当前待插入的数
while preIndex >= 0 and curNum < bucket[preIndex]: # 将比 curNum 大的元素向后移动
bucket[preIndex + 1] = bucket[preIndex]
preIndex -= 1
bucket[preIndex + 1] = curNum # 待插入的数的正确位置
a_list.extend(bucket) # 将排序好的桶一词放入空的待排序数组中
return a_list
a_list = [23, 423, 4, 643, 32, 234, 435, 56, 234, 754]
b = bucketSort(a_list)
print(b)
- 基数排序
基数排序是桶排序的一种推广，它所考虑的待排记录包含不止一个关键字。需要最主位关键字和最次位关键字。基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
基数排序有两种方法：
- MSD （主位优先法）：从高位开始进行排序
- LSD （次位优先法）：从低位开始进行排序
先获取数组中的最大数，并取得位数，然后在原始数组中从最低位开始取每个位组成radix（基数）数组，对基数数组进行计数排序（计数排序适用于小范围数）
# 次位优先法 LSD Radix Sort
def radixSort(a_list):
mod = 10 # 空桶个数
div = 1
mostBit = len(str(max(a_list))) # 最大数的位数，决定了外循环多少次
# 构造mod个空桶
buckets = [[] for row in range(mod)]
while mostBit:
# 将数据放入对应的桶中
for num in a_list:
buckets[num // div % mod].append(num)
i = 0 # a_list的索引
# 收集数据
for bucket in buckets:
while bucket:
a_list[i] = bucket.pop(0) # 依次取出
i += 1
div *= 10
mostBit -= 1
return a_list
a_list = [234, 34, 634, 57, 34, 6, 83, 48, 23, 734, 834, 21, 1, 3, 342, 2, 6, 34, 56, 48]
b = radixSort(a_list)
print(b)
补充
- 外部排序
外部排序是指大文件排序，即待排序的数据记录以文件的形式存储在外存储器上。由于文件中的记录很多、信息容量庞大，所以整个文件所占据的存储单元往往会超过了计算机的内存量，因此，无法将整个文件调入内存中进行排序。于是，在排序过程中需进行多次的内外存之间的交换。在实际应用中，由于使用的外设不一致，通常可以分为磁盘文件排序和磁带文件排序两大类。
外部排序基本上由两个相对独立的阶段组成。首先，按可用内存大小，将外存上含 N 个记录的文件分成若干长度为 L(<N) 的子文件，依次读入内存，利用内部排序算法进行排序。然后，将排序后的文件写入外存，通常将这些文件称为归并段（Run）或“顺串”；对这些归并段进行逐步归并，最终得到整个有序文件。可见外部排序的基本方法是归并排序法，下面的例子给出了一个简单的外部排序解决过程。
给定磁盘上有6大块记录需要排序,而计算机内存最多只能对3个记录块进行内排序
【解析】首先将连续的3大块记录读入内存，用任何一种内部排序算法完成排序，再写回磁盘。经过2次3大块记录的内部排序，得到上图（a）的结果。然后另用一个可容纳6大块记录的周转盘，辅助最后的归并。方法是将内存分成3块，其中2块用于输入，1块用于输出，指定一个输入块只负责读取一个归并段中的记录，如上图（b）所示。归并步骤为：
当任一输入块为空时，归并暂停，将相应归并段中的一块信息写入内存
将内存中2个输入块中的记录逐一归并入输出块
当输出块写满时，归并暂停，将输出块中的记录写入周转盘
如此可将2个归并段在周转盘上归并成一个有序的归并段。上例的解决方法是最简单的归并法，事实上外部排序的效率还可以进一步提高。提高外排的效率，关键要解决以下4个问题：
- 如何减少归并轮数
- 如何有效安排内存中的输入、输出块，使得机器的并行处理能力被最大限度利用
- 如何有效生成归并段
- 如何将归并段进行有效归并
针对这四大问题，人们设计了多种解决方案，例如釆用多路归并取代简单的二路归并，就可以减少归并轮数；例如在内存中划分出2个输出块，而不是只用一个，就可以设计算法使得归并排序不会因为磁盘的写操作而暂停，达到归并和写周转盘同时并行的效果；例如通过一种“败者树”的数据结构，可以一次生成2倍于内存容量的归并段；例如利用哈夫曼树的贪心策略选择归并次序，可以耗费最少的磁盘读写时间等。
-
排序比较
-
基数排序 vs 计数排序 vs 桶排序
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
基数排序：根据键值的每位数字来分配桶
计数排序：每个桶只存储单一键值
桶排序：每个桶存储一定范围的数值 -
哪些排序算法可以在未结束排序时找出第 k 大元素？
冒泡、选择、堆排序、快排（想想为什么？）
-
网友评论