1. 冒泡排序

冒泡排序是最简单的排序算法,正如它的名字,算法的流程就是不断地将当前最大值往后交换的过程。

1.1 算法描述

  1. 比较相邻两个元素,将较大数换到后面;
  2. 遍历每一对元素到结尾,使得结尾的数是当前最大值;
  3. 重复上述操作,直到排序完成。

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 时间复杂度

由于嵌套两轮循环,在最优情况下,若不考虑上述改进,则时间开销为n(n1)2\frac{n(n-1)}{2},时间复杂度为O(n2)O(n^2);在最坏情况下,时间开销为3n(n1)2\frac{3n(n-1)}{2},因为每次排序都需要交换两元素,需要O(n2)O(n^2)的时间复杂度。
综上:

  • 最优时间复杂度为O(n2)O(n^2),若经过上述优化,则只需要遍历一次发现数组本身有序,则最优时间复杂度为O(n)O(n)
  • 最差时间复杂度为O(n2)O(n^2)
  • 平均时间复杂度为O(n2)O(n^2)

1.5.2 空间复杂度

冒泡排序占用的内存空间在于交换时的临时变量:

  • 最优的空间复杂度就是数组本身有序,空间复杂度为0;
  • 最差空间复杂度为O(1)O(1),因为每次都需要占用临时变量。

2. 选择排序

选择排序是另一种简单直观地排序方法,与冒泡排序类似,每次从未排序的数中选取最小(大)值,放到已排序序列。

2.1 算法描述

  1. 在未排序序列中找到最小(大)元素,存放到排序序列的起始位置;
  2. 从剩余未排序的元素中,继续寻找最小(大)元素,放到已排序序列的末尾。
  3. 重复第二步,直到所有元素均排序。

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 时间复杂度

与冒泡排序类似,选择排序的最优、最坏、平均时间复杂度均为O(n2)O(n^2),因为需要两轮遍历。

2.4.2 空间复杂度

由于仅需要交换时的临时变量,选择排序的空间复杂度为O(1)O(1)

3. 插入排序

构建有序序列,对于未排序数据,在已排序的序列中,从后向前扫描,找到相应位置插入。

3.1 算法描述

  1. 把待排序数组分为已排序和未排序两部分,初始时,认为第一个元素已排好
  2. 从第二个元素开始,在已排序的子数组中,寻找该元素合适的位置并插入;
  3. 重复上述过程,直到最后一个数被插入有序子数组。

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 时间复杂度

最坏情况下,需要执行两轮遍历,时间复杂度为O(n2)O(n^2),而最优情况下,每个数仅需要遍历一次,时间复杂度为O(n)O(n)

3.4.2 空间复杂度

由于仅需要临时变量保存待插入元素,空间复杂度为O(1)O(1)

3.5 插入排序与选择排序

选择排序需要遍历未排序的数的最小值,而插入排序则需要找到当前数的合适位置,找这个位置的过程中其实是可以提前结束的,那么理论上,插入排序所需要的时间会少于选择排序。此外,选择排序是不稳定的,而插入排序是稳定的。

4. 归并排序

归并排序是采用分治法的典型算法,先使得每个子序列有序,再将已有序的子序列合并。

4.1 算法描述

  1. 申请空间,用来存放合并后的序列;
  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置;
  3. 比较两个指针指向的元素,选择相对较小的元素放入合并空间,并移动指针到下一位置;
  4. 重复步骤3直到某一指针到达序列尾;
  5. 将另一序列剩下的所有元素直接复制到合并序列尾。

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,每一步都是合并子序列的过程,时间复杂度为O(n)O(n),因此综合时间复杂度为O(nlogn)O(nlogn)

4.4.2 空间复杂度

需要辅助数组,长度为n,此外,递归实现需要的空间为O(logn)O(logn),因此空间复杂度为O(n)O(n)

5 快速排序

5.1 算法描述

  1. 令数组的第一个元素为哨兵“pivot”;
  2. 从数组尾部往前查找小于哨兵的元素A,把它放到第一位,即哨兵的位置;
  3. 从数组头部往后查找大于哨兵的元素B,将B放到元素A的位置上。
  4. 循环上面2、3步,直到最后一个元素,left<=right,将哨兵置于该位置。
  5. 递归地对前后两个分区进行排序。

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正好可以平分数组,此时时间复杂度为O(nlogn)O(nlogn)
最差情况下,每次取到的元素是数组中的最小/最大值,这种情况就和冒泡排序类似,每次只排好一个数的位置,时间复杂度为O(n2)O(n^2)。平均时间复杂度为nO(logn)nO(logn)

5.4.2 空间复杂度

快速排序真正消耗空间是递归调用的空间,最优情况下空间复杂度为O(logn)O(logn),而最差情况下,空间复杂度为O(n)O(n),平均空间消耗为O(nlogn)O(nlogn)

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 算法描述

对于构建升序序列来说,

  1. 构建大顶堆,分为已排序区和未排序区;
  2. 将堆顶与未排序区的堆尾元素调换,更新已排序区;
  3. 调整未排序区,使其满足堆条件;
  4. 重复上述过程,直到数组有序。

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,这里的时间复杂度为O(n)O(n)。后续调整过程,因为沿着堆的父子节点进行调整,为O(logn)O(logn),一共要执行n次,因此堆排序的时间复杂度为O(nlogn)O(nlogn)

6.5.2 空间复杂度

由于可以对原数组构建堆,因此不需要额外的辅助空间。空间复杂度为O(1)O(1)

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. 希尔排序

希尔排序是直接插入排序的改进版本,主要基于以下两点:

  1. 在最优情况下,数组基本有序时,插入排序的时间复杂度接近O(n);
  2. 但是在数组较大且基本无序的情况下性能会迅速降低。
    将数组按下标的一定增量分组,对每组使用直接插入排序进行排序;随着增量逐渐减少,数组也趋于有序,最后增量为1时,算法终止。
    希尔排序期望利用直接插入排序在数组基本有序的情况下,可以早停,接近O(n)O(n)。通过对数组进行分组,每个分组内进行直接插入排序。这里分组,通过增量序列实现,增量序列需要注意最后一定为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 时间复杂度

希尔排序根据增量不同,最优情况的时间复杂度是不同的,但是由于分组,在最优情况下时间复杂度可以达到O(nlogn)O(nlogn)

7.4.2 空间复杂度

和直接插入排序一样,仅需要交换到时的临时变量,因此空间复杂度为O(1)O(1)

8. 计数排序

计数排序的核心在于将数值转为键存储在额外空间,计数排序要求输入的数据必须是有确定范围的整数。

8.1 算法描述

  1. 找出待排序数组的最大值和最小值,构建辅助数组;
  2. 统计数组中每个值为i的元素出现的次数,存入辅助数组的第i项;
  3. 对所有的数计数;
  4. 将辅助数组展开,得到排序结果。

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 时间复杂度

假设所给数据在一定范围,即最大最小值已知,那么算法的时间消耗为O(n+k)O(n+k)

8.3.2 空间复杂度

计数排序的空间消耗主要是构建辅助数组需要的空间,即O(k)O(k)
若所给数据的最大值最小值相差很大,那么计数排序需要消耗大量内存空间。

9. 桶排序

桶排序是计数排序的升级版,类似hash的思想,将数组分配到有限数量的桶里,然后对每个桶内进行排序,再将每个桶中的数据合并。
在划分桶时,可以保证桶间的数据相对有序。

9.1 算法描述

  1. 找出待排序数组的最大值、最小值;
  2. 构建桶,桶的数量为(max-min)/len(arr)+1;
  3. 遍历数组,计算每个元素应该存放的桶;
  4. 每个桶内进行排序;
  5. 将每个桶的元素重新组合。

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个。我们可以在每个桶内进行快速排序、归并排序、堆排序这些O(nlogn)O(nlogn)的方法。那么m个桶就是,mO(klogk)=mO(n/mlog(n/m))=O(nlog(n/m))m* O(k * logk) = m*O(n/m*log(n/m)) = O(nlog(n/m))。因此,当n/m接近1时,桶排序的时间复杂度接近O(n)O(n)
然而在最坏情况下,所有数据都被分到同一个桶中,那么桶排序的时间复杂度退化为O(nlogn)O(nlogn)

10. 基数排序

基数排序是桶排序的扩展,基本思想是:将整数按位数切割成不同的数字,然后按每个位数比较存储。

10.1 算法描述

  1. 从最低位开始,按当前位的值存储到对应的桶中;
  2. 在低位相对有序的情况下,再对高位用相同的方法进行排序。

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趟,每趟是一个位数的映射,因此,时间消耗为O(kn)O(kn),当k远小于n时,算法的时间复杂度为O(n)O(n)

10.3.2 空间复杂度

基数排序其实为桶占用的空间,为O(10k)=O(k)O(10k) = O(k)

各排序算法分析总结

方法 平均 最坏 最优 空间复杂度 稳定性
冒泡排序 O(n2)O(n^2) O(n2)O(n^2) O(n2)O(n^2) O(1) 稳定
选择排序 O(n2)O(n^2) O(n2)O(n^2) O(n2)O(n^2) O(1) 不稳定
插入排序 O(n2)O(n^2) O(n2)O(n^2) O(n)O(n) O(1) 稳定
归并排序 O(nlogn)O(nlogn) O(nlogn)O(nlogn) O(nlogn)O(nlogn) O(n) 稳定
快速排序 O(nlogn)O(nlogn) O(n2)O(n^2) O(nlogn)O(nlogn) O(nlogn) 不稳定
堆排序 O(nlogn)O(nlogn) O(nlogn)O(nlogn) O(nlogn)O(nlogn) O(1) 不稳定
希尔排序 O(nlogn)O(nlogn) O(nlogn)O(nlogn) - O(1) 不稳定
计数排序 O(n+k)O(n+k) O(n+k)O(n+k) O(n+k)O(n+k) O(k) 稳定
桶排序 O(n)O(n) O(nlog(n))O(nlog(n)) O(n)O(n) O() 稳定
基数排序 O(n)O(n) O(kn)O(kn) O(n)O(n) O(k) 稳定