算法总结

要素说明

  1. 时间复杂度：这个直接检验一个排序算法执行的耗时情况，即快或慢；
  2. 空间复杂度：算法在执行过程中需要使用额外的空间的情况；
  3. 稳定性：排序完成后原本的顺序是否还保留，比如A原先排在B前面，现在按2人年龄排序，2人年龄是相同的，排序完成后能保证A一定排在B前面则是稳定排序；
  4. 排序方式：分为内排序和外排序，内排序只使用常数的额外空间或者不使用额外空间，一般是直接操作当前数组，改变元素位置使其有序，也叫原地排序；外排序通常需用借助额外的空间来保存排序结果，并不直接调整原数组中元素位置。

代码实现

冒泡排序

两两比较，如果后面的数比前面的数小，就交换位置。每轮迭代，本轮最大的数就好像气泡一样一直滚动到数组的最末端，因而得名冒泡排序。
优点是不占用额外空间，原地排序，并且是稳定的，代码简单容易理解。
致命缺点是时间复杂度达到了$ O(n^2) $。
冒泡排序可以在算法中添加一个变量记录每轮迭代中是否发生位置交换，如果某一轮发现没有任何位置交换，说明数组已经是有序的，可以直接退出，无需再进行后续迭代了。

1
2
3
4
5
6
7
def bubble_sort(nums: List[int]) -> List[int]:
    n=len(nums)
    for i in range(n):
        for j in range(1,n-i):
            if nums[j-1]>nums[j]:
                nums[j-1],nums[j]=nums[j],nums[j-1]
    return nums

选择排序

每一轮选择整个数组中最小（或者最大）的元素将其和数组中第0个（或者最后一个）交换位置，找到最小（或最大）的元素后，剩下的元素继续重复这个操作。
和冒泡排序很类似，不过选择排序是不稳定排序。举个例子：对于数组[5,2,5,3,1]，在第一轮迭代中交换变成了[1,2,5,3,5]，这样原本排在前面的5移动到了第2个5的后面。

1
2
3
4
5
6
7
8
9
def selection_sort(nums: List[int]) -> List[int]:
    n=len(nums)
    for i in range(n):
        min=i
        for j in range(min+1,n):
            if nums[j]<nums[min]:
                min=j
        nums[min],nums[i]=nums[i],nums[min]
    return nums

插入排序

从数组第1个元素开始枚举，依次和左侧的数值比较，直到找到一个比它还小的数，就插入到这个数的后面，如果一直没有找到比它小的数，就插入到数组的最前面。
每轮迭代中，选中的数字左侧一定是有序的，找到插入的位置后，该数字比较过的数都要向右移动一个位置，以腾出位置给该数。此过程很像你手握一副扑克牌，从左往右开始选择，每次抽出一张牌，插入到指定位置，以使整副牌有序的过程。
插入排序虽然平均时间复杂度达到了$ O(n^2) $，不过适合数组中大部分元素都是有序的，只有少量元素需要调整位置的情况。

1
2
3
4
5
6
7
8
9
def insertion_sort(nums: List[int]) -> List[int]:
    for i in range(1,len(nums)):
        if nums[i]<nums[i-1]:
            temp,j=nums[i],i
            while j>0 and temp<nums[j-1]:
                nums[j]=nums[j-1]
                j-=1
            nums[j]=temp
    return nums

希尔排序

希尔排序因发明者叫希尔(Donald Shell)而命名，可以看到希尔排序和插入排序非常相似，就是在插入排序上的进一步优化。
插入排序以1为步长，即每次比较相邻的2个元素，而希尔排序将插入排序划分为了多轮，每轮以h作为步长，即比较相邻为[0,h,2h,3h...]的元素，一定要保证最后一轮的h是1，这样才可避免有漏掉比较的元素。
代码的前部分是生成一个步长的序列，随后按步长来执行插入排序，每轮插入排序后，步长在逐步缩小，直到变成1。可以看到，最后一轮的插入排序就是完整的一遍直接插入排序。
希尔排序的时间复杂度和步长的序列以及排序数据有关，平均来看比插入排序要快很多，但是由于每次比较和交换位置是有跨度的，所以它并不是稳定排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def shell_sort(nums: List[int]) -> List[int]:
    h=1
    while h < len(nums):
        h=3*h+1
    while h>=1:
        for i in range(h,len(nums)):
            if nums[i]<nums[i-h]:
                temp,j=nums[i],i
                while j>0 and temp<nums[j-h]:
                    nums[j]=nums[j-h]
                    j-=h
                nums[j]=temp
        h=h//3
    return nums

归并排序

归并排序将数组从中间一分为二，然后对2个子数组进行排序，由于子数组都是有序的，所以只需从2个子数组的开头开始，依次比较，较小的那个填入到新数组，即将两个有序数组合并成一个有序数组。
对于子数组的排序，可以采用递归的方式再次使用归并排序。
归并排序的时间复杂度和数据无关，始终稳定在$ O(n\log n)$，同时它也是稳定排序，唯一的缺点是它需要$ O(n) $的额外空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def merge_sort(nums: List[int]) -> List[int]:
    def merge(left,right):
        res=[]
        i,j=0,0
        while i<len(left) and j<len(right):
            if left[i]<right[j]:
                res.append(left[i])
                i+=1
            else:
                res.append(right[j])
                j+=1
        if i==len(left):
            res+=right[j:]
        if j==len(right):
            res+=left[i:]
        return res
    if len(nums)<2:
        return nums
    mid=len(nums)//2
    left=merge_sort(nums[:mid])
    right=merge_sort(nums[mid:])
    return merge(left,right)

另一种归并排序的实现，通过索引来拆分数组，思想都是一样的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def merge_sort(self, nums: List[int]) -> int:
    temp=[0]*len(nums)
    def merge(left,mid,right):
        for k in range(left,right+1):
            temp[k]=nums[k]
        i,j=left,mid+1
        for k in range(left,right+1):
            if i>mid:
                nums[k]=temp[j]
                j+=1
            elif j>right:
                nums[k]=temp[i]
                i+=1
            elif temp[i]<=temp[j]:
                nums[k]=temp[i]
                i+=1
            else:
                nums[k]=temp[j]
                j+=1
    def sort(left,right):
        if left>=right:
            return
        mid=(left+right)//2
        sort(left,mid)
        sort(mid+1,right)
        merge(left,mid,right)
    sort(0,len(nums)-1)
    return nums

快速排序

快速排序从数组中选择一个值作为基准(pivot)，将数组一分为二，小于这个值的排在左边，大于这个值的排在右边，拆分的2个数组再采用递归的方式继续拆分，直到全部有序。例如下面的代码每次使用第1个元素的值作为基准(pivot)。
时间复杂度受选取的pivot影响，所以数据越随机排序效率越高。由于使用了递归，每次递归中需声明一个pivot，所以总共需要占用$ O(\log n) $的栈空间。
如果数据完全倒序，同时每次采用第一个元素作为pivot，算法会退化成冒泡排序，时间复杂度变成最坏情况的$ O(n^2) $。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def quick_sort(nums: List[int]) -> List[int]:
    def sort(lo,hi):
        if lo>hi:
            return
        v=nums[lo]
        i,j=lo+1,hi
        while True:
            while i<=j and nums[i]<=v:
                i+=1
            while i<=j and nums[j]>=v:
                j-=1
            if i>j:
                break
            nums[i],nums[j]=nums[j],nums[i]
        nums[lo],nums[j]=nums[j],nums[lo]
        sort(lo,j-1)
        sort(j+1,hi)
    sort(0,len(nums)-1)
    return nums

堆排序

堆排序把数组看作是一棵完全二叉树的结构，下标为0的元素是二叉树的根，那么根据完全二叉树的定义，如果一个数组元素的下标是i，那么它的左右子节点的下标分别是 2*i+1 和 2*i+2。
堆排序分2个步骤，首先构造一个大顶堆，即所有父节点一定是大于或等于它的2个孩子节点的，在大顶堆中根节点就是最大的元素。
其次，将根节点和最后一个元素交换，这样最大的元素排在了数组末尾，同时排除这个元素；换过来的元素变成了根节点，不断和子节点进行比较，如果比子节点小则交换位置，直到满足一个大顶端。
重复步骤2，直到大顶端只剩最后一个元素，此时数组已经是有序的了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def heap_sort(nums: List[int]) -> List[int]:
    def sink(k,last):
        while True:
            j=2*k+1
            if j>last:
                break
            if j<last and nums[j]<nums[j+1]:
                j+=1
            if nums[k]>=nums[j]:
                break
            nums[k],nums[j]=nums[j],nums[k]
            k=j
    n=len(nums)
    for k in range(n//2,-1,-1):    #构造大顶堆
        sink(k,n-1)
    k=n-1
    while k>0:
        nums[0],nums[k]=nums[k],nums[0]
        k-=1
        sink(0,k)
    return nums

堆排序的时间复杂度是$ O(n\log n) $，但是它有一种应用场景，比如你想从大量的数据中找到最大的5个，选择堆排序使你并不需要对整个数组进行排序后才能得到结果。

计数排序

统计每个数值出现的次数，用counter数组记录，counter的下标j是具体数值counter[j]表示次数，枚举counter将次数大于0的j值依次填回到原数组。
非原地排序，时间复杂度只有$ O(n+k) $，k表示数值间的最大跨度，需要用$ O(k) $空间来存储counter。
非常规排序，适合于数值排序，并且数值跨度较小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def count_sort(nums: List[int]) -> List[int]:
    _min=50000                     #排序数组的最大值
    _max=-50000                    #排序数组的最小值
    for n in nums:
        _min=min(n,_min)
        _max=max(n,_max)
    counter=[0]*(_max-_min+1)
    for n in nums:
        counter[n-_min]+=1
    j=0
    for i in range(len(nums)):
        while counter[j]==0:
            j+=1
        nums[i]=j+_min
        counter[j]-=1
    return nums

桶排序

和计数排序很相像，不同的是计数排序每个桶只存储一个值，而桶排序每个桶存储的是某个区间范围的值，可以看到当把bucketSize设置为1的时候和计数排序是一样的。
当把元素按值的范围归到不同的桶之后，再针对每个桶进行排序，代码为了演示仍然采用了桶排序进行递归调用，为了避免无限制的递归，当只能分一个桶的时候bucketCnt==1，强制将桶容量减小bucketSize-=1，以分出多个桶。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def bucket_sort(nums: List[int], bucketSize: int) -> List[int]:
    if len(nums)<2:
        return nums
    _min=50000                     #排序数组的最大值
    _max=-50000                    #排序数组的最小值
    for n in nums:
        _min=min(n,_min)
        _max=max(n,_max)
    bucketCnt = (_max - _min) // bucketSize + 1
    buckets = [[] for _ in range(bucketCnt)]
    for n in nums:
        buckets[(n - _min) // bucketSize].append(n)
    res = []
    for b in buckets:
        if not b:
            continue
        if bucketSize==1:
            res+=b
        else:
            if bucketCnt==1:
                bucketSize-=1
            res+=bucket_sort(b,bucketSize)
    return res

基数排序

以每一位作为基数进行排序，以十进制数值为例，先取个位，根据数值放到相应的“桶”里，再从“桶”里拿出来放回原数组，这样个位就是有序的了；再取十位，根据数值放到相应的“桶”里，再从“桶”里拿出来放回原数组，这样十位就有序了，以此类推，直到最高位也有序。
因为数值的比较是先从最高位比较，最后比较个位，所以这样从个位到最高位依次进行“放”和“拿”的操作，最后得到的数组是根据数值从小到大排序的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def radix_sort(nums: List[int]) -> List[int]:
    _min=50000                     #排序数组的最大值
    _max=-50000                    #排序数组的最小值
    for n in nums:
        _min=min(n,_min)
        _max=max(n,_max)
    maxDigit = len(str(_max-_min))
    buckets = [[] for _ in range(10)]
    div, mod = 1, 10
    for _ in range(maxDigit):
        for n in nums:
            buckets[(n-_min) % mod // div].append(n-_min)
        i = 0
        for j in range(10):
            for n in buckets[j]:
                nums[i] = n+_min
                i += 1
            buckets[j].clear()
        div *= 10
        mod *= 10
    return nums

图片出处：
https://www.cnblogs.com/guoyaohua/p/8600214.html
https://makeagif.com/gif/how-to-bucket-sort-a7ppGv