1. 冒泡排序
冒泡排序是最简单的排序算法,正如它的名字,算法的流程就是不断地将当前最大值往后交换的过程。
1.1 算法描述
- 比较相邻两个元素,将较大数换到后面;
- 遍历每一对元素到结尾,使得结尾的数是当前最大值;
- 重复上述操作,直到排序完成。
1.2 算法实现
def bubble_sort(arr): n = len(arr) # 注意边界条件,i从(1,n-1) for i in range(n-1,0,-1): for j in range(i): if arr[j]>arr[j+1]: # 需要交换 arr[j],arr[j+1] = arr[j+1],arr[j] return arr
1.3 稳定性
在相邻元素相等时,它们并不会交换位置,所以冒泡排序是稳定的。
1.4 算法改进
当前一轮没有交换时,说明数组已经有序,没有必要进行下一轮的循环,可以直接退出。
def bubble_sort(arr): n = len(arr) swap = False for i in range(n-1,0,-1): for j in range(i): if arr[j]>arr[j+1]: # 需要交换 arr[j],arr[j+1] = arr[j+1],arr[j] swap = True if not swap: break return arr
1.5 复杂度分析
1.5.1 时间复杂度
由于嵌套两轮循环,在最优情况下,若不考虑上述改进,则时间开销为,时间复杂度为;在最坏情况下,时间开销为,因为每次排序都需要交换两元素,需要的时间复杂度。
综上:
- 最优时间复杂度为,若经过上述优化,则只需要遍历一次发现数组本身有序,则最优时间复杂度为;
- 最差时间复杂度为;
- 平均时间复杂度为。
1.5.2 空间复杂度
冒泡排序占用的内存空间在于交换时的临时变量:
- 最优的空间复杂度就是数组本身有序,空间复杂度为0;
- 最差空间复杂度为,因为每次都需要占用临时变量。
2. 选择排序
选择排序是另一种简单直观地排序方法,与冒泡排序类似,每次从未排序的数中选取最小(大)值,放到已排序序列。
2.1 算法描述
- 在未排序序列中找到最小(大)元素,存放到排序序列的起始位置;
- 从剩余未排序的元素中,继续寻找最小(大)元素,放到已排序序列的末尾。
- 重复第二步,直到所有元素均排序。
2.2 算法实现
def selection_sort(arr): n = len(arr) for i in range(n): # i表示有序区域的末尾 # 循环查找最小值 min_idx = i for j in range(i+1,n): if arr[j]<arr[min_idx]: min_idx = j if min_idx != i: # 交换 arr[i],arr[min_idx] = arr[min_idx],arr[i] return arr
2.3 稳定性
选择算法是不稳定的,因为每次需要从未排序的数中选择最小值与前面的数进行交换,那么对于相同值很可能改变其顺序。
例如:[5,9,5,2,3]这一组数,第一遍历,找到2最小,需要和开头的5进行交换,那么数组变为[2,9,5,5,3]。可以看到,开头的5被交换到了后面。
2.4 复杂度分析
2.4.1 时间复杂度
与冒泡排序类似,选择排序的最优、最坏、平均时间复杂度均为,因为需要两轮遍历。
2.4.2 空间复杂度
由于仅需要交换时的临时变量,选择排序的空间复杂度为。
3. 插入排序
构建有序序列,对于未排序数据,在已排序的序列中,从后向前扫描,找到相应位置插入。
3.1 算法描述
- 把待排序数组分为已排序和未排序两部分,
初始时,认为第一个元素已排好
; - 从第二个元素开始,在已排序的子数组中,寻找该元素合适的位置并插入;
- 重复上述过程,直到最后一个数被插入有序子数组。
3.2 算法实现
def insert_sort(arr): n = len(arr) for i in range(1,n): # 将第一个数作为有序子数组 pos = i pos_val = arr[i] while pos>0 and pos_val<arr[pos-1]: # 这里直接将已排序区数字后移,以减少交换次数。 arr[pos] = arr[pos-1] pos-=1 arr[pos] = pos_val return arr
3.3 稳定性
插入排序是稳定的,排序后相同数字的先后顺序不会被改变。
3.4 复杂度分析
3.4.1 时间复杂度
最坏情况下,需要执行两轮遍历,时间复杂度为,而最优情况下,每个数仅需要遍历一次,时间复杂度为。
3.4.2 空间复杂度
由于仅需要临时变量保存待插入元素,空间复杂度为。
3.5 插入排序与选择排序
选择排序需要遍历未排序的数的最小值,而插入排序则需要找到当前数的合适位置,找这个位置的过程中其实是可以提前结束的,那么理论上,插入排序所需要的时间会少于选择排序。此外,选择排序是不稳定的,而插入排序是稳定的。
4. 归并排序
归并排序是采用分治法的典型算法,先使得每个子序列有序,再将已有序的子序列合并。
4.1 算法描述
申请空间
,用来存放合并后的序列;- 设定两个指针,最初位置分别为两个已经排序序列的起始位置;
- 比较两个指针指向的元素,选择相对较小的元素放入合并空间,并移动指针到下一位置;
- 重复步骤3直到某一指针到达序列尾;
- 将另一序列剩下的所有元素直接复制到合并序列尾。
4.2 算法实现
注意事项:
- 实现时注意划分边界问题,划分时定义左右两边界都能取到。
def merge_sort(arr): n = len(arr) # 辅助数组 tmp = [0]*n m_sort(arr,tmp,0,n-1) return arr def m_sort(arr,tmp,left,right): # 当left==right时,已经不需要再划分了 if left<right: mid = (left+right)//2 m_sort(arr,tmp,left,mid) m_sort(arr,tmp,mid+1,right) merge_array(arr,tmp,left,mid,right) # 合并两个有序数组 def merge_array(arr,tmp,left,mid,right): ptr1,ptr2 = left,mid+1 k = 0 while ptr1<=mid and ptr2<=right: if arr[ptr1]<= arr[ptr2]: tmp[k] = arr[ptr1] ptr1+=1 else: tmp[k] = arr[ptr2] ptr2+=1 k+=1 while ptr1 <= mid: tmp[k] = arr[ptr1] ptr1+=1 k+=1 while ptr2 <= right: tmp[k] = arr[ptr2] ptr2+=1 k+=1 # 把数据复制回原数组 for i in range(k): arr[left+i] = tmp[i]
4.3 稳定性
归并排序中的分组和合并子序列都不会改变,因此归并排序是稳定的。
4.4 复杂度分析
4.4.1 时间复杂度
归并排序的最优和最差情况相同,拆分数组共需要logn,每一步都是合并子序列的过程,时间复杂度为,因此综合时间复杂度为。
4.4.2 空间复杂度
需要辅助数组,长度为n,此外,递归实现需要的空间为,因此空间复杂度为。
5 快速排序
5.1 算法描述
- 令数组的第一个元素为哨兵“pivot”;
- 从数组尾部往前查找小于哨兵的元素A,把它放到第一位,即哨兵的位置;
- 从数组头部往后查找大于哨兵的元素B,将B放到元素A的位置上。
- 循环上面2、3步,直到最后一个元素,left<=right,将哨兵置于该位置。
- 递归地对前后两个分区进行排序。
5.2 算法实现
# 快速排序 def quick_sort(arr): n = len(arr) q_sort(arr,0,n-1) return arr def q_sort(arr,left,right): if left >= right: return # 将数组分区 pivot = partition(arr,left,right) # 进一步对pivot两段排序 q_sort(arr,left,pivot-1) q_sort(arr,pivot+1,right) def partition(arr,left,right): # pivot为第一个数,这里可以有一些策略选择更优的pivot pivot = arr[left] while left < right: while left < right and arr[right]>=pivot: right -=1 # 将小于pivot的数,交换至pivot的左侧 arr[left] = arr[right] while left < right and arr[left]<=pivot: left+=1 # 将大于pivot的数交换到pivot的右侧 arr[right] = arr[left] arr[left] = pivot return left
5.3 稳定性
快速排序是不稳定的,pivot有可能会被换到相同数字的后面。
5.4 复杂度分析
5.4.1 时间复杂度
最优情况下,所选的pivot正好可以平分数组,此时时间复杂度为。
最差情况下,每次取到的元素是数组中的最小/最大值,这种情况就和冒泡排序类似,每次只排好一个数的位置,时间复杂度为。平均时间复杂度为。
5.4.2 空间复杂度
快速排序真正消耗空间是递归调用的空间,最优情况下空间复杂度为,而最差情况下,空间复杂度为,平均空间消耗为。
6. 堆排序
利用堆这种数据结构的选择排序算法。堆排序就是把最大堆堆顶的最大数取出,将剩余的堆继续调整为最大堆,在将堆最大值取出。
6.1 堆的概念
堆是一种完全二叉树
,除了最底层外,每一层都是满的,且满足父节点大于/小于子节点。由于是完全二叉树,因此堆可以方便地由数组表示,且父子节点之间存在如下关系:
- 父节点为i,左子节点为2i+1
- 父节点为i,右子节点为2i+2
6.1.1 构建堆
遵循的原则为:
- 遍历所有父节点;
- 比较所有节点的值,将最大值赋给父节点;
- 递归
""" arr: 待堆化的列表 n: 列表长度 i: 开始节点 """ def heapify(arr,n,i): # 终止条件 if i >= n: return # 根节点,默认根节点为最大 largest = i # 左右子节点 left,right = 2*i+1,2*i+2 # 找到最大的节点索引 if left < n and arr[left] > arr[largest]: largest = left if right < n and arr[right] > arr[largest]: largest = right if largest != i: # 需要交换 arr[i],arr[largest]=arr[largest],arr[i] # 因为左右子节点变小了,需要再往下遍历,使其满足堆的条件 heapify(arr,n,largest)
需要注意的是,构建堆时,需要从下往上构建,这样才能保证根节点是最大值。
# 构建堆 n = len(arr) # 最后一个非叶子节点 for i in range(n//2-1,-1,-1): heapify(arr,n,i)
6.2 算法描述
对于构建升序序列来说,
- 构建大顶堆,分为已排序区和未排序区;
- 将堆顶与未排序区的堆尾元素调换,更新已排序区;
- 调整未排序区,使其满足堆条件;
- 重复上述过程,直到数组有序。
6.3 算法实现
# 堆排序 def heap_sort(arr): n = len(arr) # 构建大顶堆 # 自下而上构建,因为反过来,会使得根节点不一定是最大值 for i in range(n//2-1,-1,-1): # 这里从最后一个非叶子节点开始调整,算是一个优化。 heapify(arr,n,i) # 可以将arr看做未排序区和已排序区,每次将最大值与未排序区的末尾元素交换。 for i in range(n-1,-1,-1): arr[0],arr[i] = arr[i],arr[0] heapify(arr,i,0) return arr
6.4 稳定性
由于会将堆顶移至堆尾,会使得相同值的前者移动到较后位置,因此堆排序是不稳定的。
6.5 复杂度分析
6.5.1 时间复杂度
建立堆的过程,从n/2一直处理到0,这里的时间复杂度为。后续调整过程,因为沿着堆的父子节点进行调整,为,一共要执行n次,因此堆排序的时间复杂度为。
6.5.2 空间复杂度
由于可以对原数组构建堆,因此不需要额外的辅助空间。空间复杂度为
6.6 算法应用
6.6.1 数组中的第K个最大元素
这是一道leetcode原题,也是面试过程中经常出现的一道题。
给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。
请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
我们可以利用堆排序的性质,第k个最大的元素,正好可以出现在排序阶段的第k次,而前面堆化以及构建堆的代码都可以复用。
class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: # 堆化 def heapify(nums,n,i): if i >= n: return # 默认根节点为最大值 largest = i # 左右子节点 left,right = 2*i+1,2*i+2 if left < n and nums[left] > nums[largest]: largest = left if right < n and nums[right] > nums[largest]: largest = right if largest != i: # 交换 nums[largest],nums[i] = nums[i],nums[largest] # 递归调整 heapify(nums,n,largest) # 构建大顶堆 n = len(nums) for i in range(n//2-1,-1,-1): heapify(nums,n,i) # 执行k-1次删除,也可以理解为堆排序的第k步 for i in range(1,k): nums[0],nums[n-i] = nums[n-i],nums[0] heapify(nums,n-i,0) return nums[0]
7. 希尔排序
希尔排序是直接插入排序的改进版本,主要基于以下两点:
- 在最优情况下,数组基本有序时,插入排序的时间复杂度接近O(n);
- 但是在数组较大且基本无序的情况下性能会迅速降低。
将数组按下标的一定增量分组,对每组使用直接插入排序进行排序;随着增量逐渐减少,数组也趋于有序,最后增量为1时,算法终止。
希尔排序期望利用直接插入排序在数组基本有序的情况下,可以早停,接近。通过对数组进行分组,每个分组内进行直接插入排序。这里分组,通过增量序列实现,增量序列需要注意最后一定为1。
7.1 算法描述
- 选择一个增量序列,t1,t2,...,tk,其中ti>tj,tk=1;
- 按增量序列个数,对序列进行k趟排序;
- 每趟排序,根据对应的增量ti,将待排序的数组分为若干子序列,分别进行直接插入排序。
7.2 算法实现
7.2.1 Donald Shell 增量
增量每次缩小二分之一。
def shell_sort(arr): n = len(arr) incre = n//2 while True: for i in range(incre,n): pos = i pos_val = arr[pos] while pos >= incre and pos_val < arr[pos-incre]: arr[pos],arr[pos-incre] = arr[pos-incre],arr[pos] arr[pos] = pos_val if incre == 1: break incre = incre//2 return arr
7.3 稳定性
由于不是相邻元素的对比,难免造成相同元素的位置颠倒,因此,希尔排序是不稳定的。
7.4 复杂度分析
7.4.1 时间复杂度
希尔排序根据增量不同,最优情况的时间复杂度是不同的,但是由于分组,在最优情况下时间复杂度可以达到。
7.4.2 空间复杂度
和直接插入排序一样,仅需要交换到时的临时变量,因此空间复杂度为。
8. 计数排序
计数排序的核心在于将数值转为键存储在额外空间,计数排序要求输入的数据必须是有确定范围的整数。
8.1 算法描述
- 找出待排序数组的最大值和最小值,构建辅助数组;
- 统计数组中每个值为i的元素出现的次数,存入辅助数组的第i项;
- 对所有的数计数;
- 将辅助数组展开,得到排序结果。
8.2 算法实现
def count_sort(arr): # 获得最大最小值 max_,min_ = max(arr),min(arr) # 生成辅助数组 arr_ = [0]*(max_-min_+1) for num in arr: arr_[num-min_] += 1 idx = 0 # 将辅助数组展开,并赋值回原数组 for i in range(max_-min_+1): while arr_[i] > 0: arr[idx] = i+min_ idx+=1 arr_[i]-=1 return arr
8.3 复杂度分析
假设所给数据的最大值最小值的间隔为k
8.3.1 时间复杂度
假设所给数据在一定范围,即最大最小值已知,那么算法的时间消耗为
8.3.2 空间复杂度
计数排序的空间消耗主要是构建辅助数组需要的空间,即。
若所给数据的最大值最小值相差很大,那么计数排序需要消耗大量内存空间。
9. 桶排序
桶排序是计数排序的升级版,类似hash的思想,将数组分配到有限数量的桶里,然后对每个桶内进行排序,再将每个桶中的数据合并。
在划分桶时,可以保证桶间的数据相对有序。
9.1 算法描述
- 找出待排序数组的最大值、最小值;
- 构建桶,桶的数量为(max-min)/len(arr)+1;
- 遍历数组,计算每个元素应该存放的桶;
- 每个桶内进行排序;
- 将每个桶的元素重新组合。
9.2 算法实现
def bucket_sort(arr): n = len(arr) max_,min_ = max(arr),min(arr) # 构建桶 bucket_num = (max_-min_)//n+1 buckets = [[] for _ in range(bucket_num)] # 将每个元素放入对应桶 for num in arr: buckets[(num-min_)//n].append(num) # 对每个桶内进行排序 # 这里排序方法可以自选 idx = 0 for bucket in buckets: bucket = sorted(bucket) for num in bucket: arr[idx] = num idx+=1 return arr
9.3 复杂度分析
9.3.1 时间复杂度
假设待排序的数组个数为n,这n个数可以被分到m个桶中,这样每个桶里的数据就是k=n/m个。我们可以在每个桶内进行快速排序、归并排序、堆排序这些的方法。那么m个桶就是,。因此,当n/m接近1时,桶排序的时间复杂度接近。
然而在最坏情况下,所有数据都被分到同一个桶中,那么桶排序的时间复杂度退化为。
10. 基数排序
基数排序是桶排序的扩展,基本思想是:将整数按位数切割成不同的数字,然后按每个位数比较存储。
10.1 算法描述
- 从最低位开始,按当前位的值存储到对应的桶中;
- 在低位相对有序的情况下,再对高位用相同的方法进行排序。
10.2 算法实现
# 假设待排序数都是正整数 def radix_sort(arr): # 最大值的位数 k = len(str(max(arr))) for i in range(k): # 建桶 buckets =[[]*10] for num in arr: buckets[num//(10**i)%10].append(num) # 按当前顺序,重排列表 idx = 0 for bucket in buckets: for num in bucket: arr[idx] = num idx+=1 return arr
10.3 复杂度分析
10.3.1 时间复杂度
假设最大数的位数为k,基数排序需要进行k趟,每趟是一个位数的映射,因此,时间消耗为,当k远小于n时,算法的时间复杂度为。
10.3.2 空间复杂度
基数排序其实为桶占用的空间,为
各排序算法分析总结
方法 | 平均 | 最坏 | 最优 | 空间复杂度 | 稳定性 |
---|---|---|---|---|---|
冒泡排序 | O(1) | 稳定 | |||
选择排序 | O(1) | 不稳定 | |||
插入排序 | O(1) | 稳定 | |||
归并排序 | O(n) | 稳定 | |||
快速排序 | O(nlogn) | 不稳定 | |||
堆排序 | O(1) | 不稳定 | |||
希尔排序 | - | O(1) | 不稳定 | ||
计数排序 | O(k) | 稳定 | |||
桶排序 | O() | 稳定 | |||
基数排序 | O(k) | 稳定 |