排序算法总结
排序，排序，排序 ( ఠൠఠ )ﾉ
插入排序
核心思想：
- 将待排序的元素插入到已排好序的序列中
- 只有一个元素时视为排好序
直接插入排序
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)
- 选择排序是不稳定的
堆排序
堆是一种类似完全二叉树的结构，可以使用数组或链表存储，同时一个堆必须满足一下性值：
- 子节点的值必须小于父节点的值
- 子节点必须也是一个堆
堆排序的思想是先将待排序序列构造为一个堆，这样整个序列中值最大的元素必然处在堆顶，然后将堆顶元素与堆中最后一个元素交换，最大的值就会被“沉”下去，然后调整除“被沉下去”的元素外的所有元素为一个新的堆，重复直到所有元素被“沉下去”
构造堆的方法：
（图中的元素是下标）
存储堆的数据结构一般是数组，且由于堆是一个完全二叉树，所以我们可以找出堆中元素父子关系与其数组下标之间的函数关系：
下标为 i的元素的左右孩子下标分别为为：
Left(i) = i * 2 + 1
Right(i) = i * 2 + 2
根据上面的公式，加上堆父节点大于子节点的性质，就可以将原来的序列构造为堆:
- 先找到最后一个非叶子节点：UnLafeIndex = len(nums) /2 - 1。
- 判断它是否满足大顶堆，如果满足则去判断前一个非叶子节点，如果不满足就将他与值最大的子节点交换。
- 交换之后又可能造成之前构造的堆被破坏，所以还需要重新构造交换后的子树
如一个待排序序列： nums=[5, 9, 3, 4, 7, 8]
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)