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

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

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

1.5.2 空间复杂度

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

• 最优的空间复杂度就是数组本身有序，空间复杂度为0；
• 最差空间复杂度为$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(n^2)$，因为需要两轮遍历。

2.4.2 空间复杂度

由于仅需要交换时的临时变量，选择排序的空间复杂度为$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(n^2)$，而最优情况下，每个数仅需要遍历一次，时间复杂度为$O(n)$。

3.4.2 空间复杂度

由于仅需要临时变量保存待插入元素，空间复杂度为$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(nlogn)$。

4.4.2 空间复杂度

需要辅助数组，长度为n，此外，递归实现需要的空间为$O(logn)$，因此空间复杂度为$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(n^2)$。平均时间复杂度为$nO(logn)$。

5.4.2 空间复杂度

快速排序真正消耗空间是递归调用的空间，最优情况下空间复杂度为$O(logn)$，而最差情况下，空间复杂度为$O(n)$，平均空间消耗为$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(logn)$，一共要执行n次，因此堆排序的时间复杂度为$O(nlogn)$。

6.5.2 空间复杂度

由于可以对原数组构建堆，因此不需要额外的辅助空间。空间复杂度为$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)$。通过对数组进行分组，每个分组内进行直接插入排序。这里分组，通过增量序列实现，增量序列需要注意最后一定为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)$。

7.4.2 空间复杂度

和直接插入排序一样，仅需要交换到时的临时变量，因此空间复杂度为$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)$

8.3.2 空间复杂度

计数排序的空间消耗主要是构建辅助数组需要的空间，即$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)$的方法。那么m个桶就是，$m* O(k * logk) = m*O(n/m*log(n/m)) = O(nlog(n/m))$。因此，当n/m接近1时，桶排序的时间复杂度接近$O(n)$。
然而在最坏情况下，所有数据都被分到同一个桶中，那么桶排序的时间复杂度退化为$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)$，当k远小于n时，算法的时间复杂度为$O(n)$。

10.3.2 空间复杂度

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

各排序算法分析总结