【算法】排序算法总结

Python
390
0
0
2022-11-27

排序算法总结

排序,排序,排序 ( ఠൠఠ )ノ

插入排序

核心思想:

  • 将待排序的元素插入到已排好序的序列中
  • 只有一个元素时视为排好序

直接插入排序

def insert_sort(nums: list) -> list:
    for i in range(1, len(nums)):
        j = i
        while j > 0 and nums[j] < nums[j - 1]:
            nums[j], nums[j -1] = nums[j - 1], nums[j]
            j -= 1 
    return nums

复杂度分析:

  • 最好情况下(本身有序)只需要遍历一遍元素,时间复杂度为 O(n)
  • 最差情况下(完全逆序)每一个元素都要和它前面的每个元素进行交换,退化为冒泡排序,时间复杂度为 O(n^2)
  • 平均时间复杂度:O(n^2)
  • 空间复杂度:不需要额外空间,复杂度为 O(1)
  • 直接插入排序是稳定的

希尔排序

Shell 排序是直接插入排序的改进版, 使用直接插入排序在序列基本有序的情况下可以接近 O(n) 的时间复杂度,相比平均的 O(n^2) 有很大的改进,所以我们可以将待排序序列先进行大致的排序,使之基本有序,然后再使用直接插入进行排序。

具体做法是提供一个步长 S, 一般设为元素数量N的一半, 然后从待排序序列的第 S + 1 位开始依次与其前 N 位元素做比较(直接插入排序),这样一趟排序下来 [0 , S] 和 [S, -1] 位便形成了基本有序的序列,然后折半 S,重复上面的过程,直到 S = 1 时“退化”为直接插入排序。

def shell_sort(nums: list):
    s = len(nums) // 2 
    while s > 1:
        for i in range(s + 1, len(nums)):
            j = i
            while j > 0 and nums[j] < nums[j - s]:
                nums[j], nums[j -s] = nums[j - s], nums[j]
                j -= s
        s = s // 2 
    print(nums)

复杂度分析:

  • 时间复杂度: Shell 排序的稳定性取决于步长的选择,但步长的最佳选择方案涉及一些暂未解决的数学难题,至今没有确切的方案,其平均复杂度为:O(n{\log}^2n)
  • 空间复杂度: O(1)
  • 由于 Shell 排序进行了多轮步长不一的插入排序,导致其丧失了稳定性

选择排序

核心思想:

  • 每次选择未排序序列中最小的元素放在已排序序列最后面

直接选择排序

     3 9 5 4 7 1
(1). 1 9 5 4 7 3
(2). 1 3 5 4 7 9
(3). 1 3 4 5 7 9
(4). 1 3 4 5 7 9
def select_sort(nums: list):
    for i in range(len(nums)):
        min_index = i
        for j in range(i, len(nums)):
            if nums[j] < nums[min_index]:
                min_index = j
        if min_index !=  i - 1:
            nums[min_index], nums[i] = nums[i], nums[min_index]
    print(nums) 

复杂度分析:

  • 一般情况下,内循环需要执行 n-1次, 所以总的执行次数为\sum_{1}^{n-1}, 故其时间复杂度为 O(n^2)
  • 空间复杂度为 O(1)
  • 选择排序是不稳定的

堆排序

堆是一种类似完全二叉树的结构,可以使用数组或链表存储,同时一个堆必须满足一下性值:

  1. 子节点的值必须小于父节点的值
  2. 子节点必须也是一个堆

堆排序的思想是先将待排序序列构造为一个堆,这样整个序列中值最大的元素必然处在堆顶,然后将堆顶元素与堆中最后一个元素交换,最大的值就会被“沉”下去,然后调整除“被沉下去”的元素外的所有元素为一个新的堆,重复直到所有元素被“沉下去”

构造堆的方法:

img

(图中的元素是下标)

存储堆的数据结构一般是数组,且由于堆是一个完全二叉树,所以我们可以找出堆中元素父子关系与其数组下标之间的函数关系:

下标为 i的元素的左右孩子下标分别为为:

Left(i) = i * 2 + 1

Right(i) = i * 2 + 2

根据上面的公式,加上堆父节点大于子节点的性质,就可以将原来的序列构造为堆:

  1. 先找到最后一个非叶子节点:UnLafeIndex = len(nums) /2 - 1。
  2. 判断它是否满足大顶堆,如果满足则去判断前一个非叶子节点,如果不满足就将他与值最大的子节点交换。
  3. 交换之后又可能造成之前构造的堆被破坏,所以还需要重新构造交换后的子树

如一个待排序序列: nums=[5, 9, 3, 4, 7, 8]

img

img

img

def get_heap(nums: list, start: int, end: int) -> list:
    length = end
    
    for i in range(length // 2 - 1, start - 1, -1):
        max_index = i
        # 如果有左子树
        if i * 2 + 1 < length:
            max_index = i * 2 + 1
        if i * 2 + 2 < length and nums[i * 2 + 2] > nums[i * 2 + 1]:
            max_index = i * 2 + 2
        if nums[i] < nums[max_index]:
            nums[i], nums[max_index] = nums[max_index], nums[i]
            get_heap(nums, max_index, end)
    return nums

得到一个大顶堆后,我们要做的就是把堆顶元素和堆中最后一个元素交换,然后再重构建大顶堆

def heap_sort(nums: list):
    end = len(nums)
    while end > 0:
        heap = get_heap(nums, 0, end)
        heap[0], heap[end - 1] = heap[end - 1], heap[0]
        end -= 1

复杂度分析:

堆排序适用于记录数较多的元素排序,当少量元素排序时,初始建堆和调整新堆要进行反复筛选,可能得不偿失,总体时间复杂度为 O(n\log_2n), 空间复杂度为 O(1), 堆排序不稳定

交换排序

交换排序的思想是对待排序的元素两两比较,如果发现不满足排序要求就交换,直到排序完成。

冒泡排序

def bubble_sort(nums: list):
    for i in range(len(nums)):
        for j in range(i, len(nums)):
            if nums[i] > nums[j]:
                nums[i], nums[j] = nums[j], nums[i]
    print(nums)

复杂度分析:

  • 时间复杂度:比较次数为 \sum_{1}^{n-1} ,故时间复杂度为 O(n^2)
  • 空间复杂度:不需要额外空间,复杂度为 O(1)
  • 冒泡是一种稳定的排序方法

快速排序

快排的思想是以待排序序列中的第一个元素作为标志 flag ,把所有大于 flag 的元素换到其右边,所有小于 flag 的元素放在左边,这样在 flag 的左边和右边就形成了相对有序的序列,再对 flag 左边和右边的元素递归进行快排,直到序列只剩一个元素。

def _get_mid(nums: list, start: int, end: int):
    mid = nums[start]
    while end > start:
        while end > start and nums[end] > mid:
            end -= 1
        nums[start] = nums[end]
        while end > start and nums[start] < mid:
            start += 1
        nums[end] = nums[start]
    nums[start] = mid
    return start

def _quick_sort(nums: list, start: int, end: int):
    if end - start > 1:
        mid = _get_mid(nums, start, end)
        _quick_sort(nums, start, mid)
        _quick_sort(nums, mid + 1, end)

def quick_sort(nums: list):
    _quick_sort(nums, 0, len(nums) - 1)

复杂度分析:

  • 如果在已经排好序的情况下,长度为 n 的序列,每 i 次快排左区间长度为 0, 右区间长度为 n - i,需要比较的次数与区间长度相等,所以最差情况下,快排需要比较的次数为:

\sum_{i=1}^{n- 1}(n-i)= \frac{n(n-1)}{2} = O(n^2)

  • 在一般的情况下,每一次快排都需要把区间一分为二,且前后两部分大小相等,当序列长度为 n 时,设需要的比较次数为 T(n), 可得以下递推方程:

T(n)= \begin{cases} 2T(n/2)+ n, & \text { n = 1} \end{cases}

解得:

T(n) = n\log_2n

故一般情况下,快排时间复杂度为 O(n\log_2n)

  • 快排空间复杂度为 O(n\log_2n)
  • 快排不稳定

归并排序

归并排序用于将两个已经有序的序列合并成一个新的有序序列。

# 1, 3, 7
# 2, 6, 8
def merge(nums1: list, nums2: list) -> list:
    l = r = 0 
    result = []
    while l < len(nums1) and r < len(nums2):
        if nums1[l] < nums2[r]:
            result.append(nums1[l])
            l += 1 
        else:
            result.append(nums2[r])
            r += 1 
    result += nums1[l:]
    result += nums2[r:]
    return result

def sort(nums: list):
    if len(nums) <= 1:
        return nums
    mid_index = len(nums) // 2 
    left = sort(nums[:mid])
    right = sort(nums[mid:])
    return merge(left, right)   

复杂度分析:

  • 时间复杂度: O(n\log_2n)
  • 空间复杂度: O(n)