常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。
△ 相关概念&名词解释
△ 排序算法可以分为非线性时间比较类和线性时间非比较类
△ 排序算法可以分为内部排序和外部排序:
# 时间复杂度:最好:O(n) 平均:O(n²) 最差:O(n²)
# 空间复杂度:O(1)
# 稳定性:稳定
def bubble_sort(self, nums: List[int]) -> List[int]:
# 遍历len(nums)-1趟
for i in range(len(nums)):
is_sorted = True
# 已经排序好的部分不用排序
for j in range(len(nums) - i - 1):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
is_sorted = False
if is_sorted:
break
return nums
# 时间复杂度:最好:O(n²) 平均:O(n²) 最差:O(n²)
# 空间复杂度:O(1)
# 稳定性:不稳定
def select_sort(self, nums: List[int]) -> List[int]:
for i in range(len(nums)):
# 默认最小值的索引,默认第一个元素已经排序
min_index = i
for j in range(i + 1, len(nums) - 1):
# 每次遍历的值与最小值进行比较
if nums[j] < nums[min_index]:
min_index = j
# 每一轮选出最小的元素,并放置在有序序列的末尾
if min_index != i:
nums[i], nums[min_index] = nums[min_index], nums[i]
return nums
# 时间复杂度:最好:O(n) 平均:O(n²)最差:O(n²)
# 空间复杂度:O(1)
# 稳定性:稳定
def insert_sort(self, nums: List[int]) -> List[int]:
# 遍历len(nums)-1轮
for i in range(len(nums) - 1):
# curNum 保存待插入元素
curNum, preIndex = nums[i + 1], i
# 如果待插入元素小于当前元素,当前元素值向后移动,同时下标向前移动
while preIndex >= 0 and curNum < nums[preIndex]:
nums[preIndex + 1] = nums[preIndex]
preIndex -= 1
# curNum插入的正确位置
nums[preIndex + 1] = curNum
return nums
# 时间复杂度:最好:O(nlogn) 平均:O(nlogn) 最差:O(n²)
# 空间复杂度:O(nlogn)
# 稳定性:不稳定
# 实现方式1:
def quick_sort(self, nums: List[int]) -> List[int]:
# 递归终止条件
if len(nums) <= 1:
return nums
pivot = nums[0]
# 单层递归逻辑
left = [nums[i] for i in range(1, len(nums)) if nums[i] < pivot]
right = [nums[i] for i in range(1, len(nums)) if nums[i] >= pivot]
return self.quick_sort(left) + [pivot] + self.quick_sort(right)
# 实现方式2:
def quick_sort1(self, nums: List[int], left: int, right: int) -> List[int]:
if left < right:
pivotIndex = self.partition(nums, left, right)
self.quick_sort1(nums, left, pivotIndex - 1)
self.quick_sort1(nums, pivotIndex + 1, right)
return nums
def partition(self, nums: List[int], left: int, right: int) -> int:
"""
分区操作
"""
pivot = nums[left]
# left 向右移动,直至遇到大于等于pivot的元素停止
# right 向左移动,直至遇到小于等于pivot的元素停止
while left < right:
while left < right and nums[right] >= pivot:
right -= 1
nums[left] = nums[right]
while left < right and nums[left] <= pivot:
left += 1
nums[right] = nums[left]
nums[left] = pivot
return left
# 时间复杂度:最好:O(n) 平均:O(n²)最差:O(n²)
# 空间复杂度:O(1)
# 稳定性:不稳定
def shell_sort(self, nums: List[int]) -> List[int]:
# 定义间隔序列
gap = len(nums) // 2
# 当gap = 0时,排序已经全部完成
while gap > 0:
# 遍历的时候加了gap
for i in range(gap, len(nums)):
# curNum保存待插入元素,操作元素之间的间隔为gap
curNum, preIndex = nums[i], i - gap
while preIndex >= 0 and curNum < nums[preIndex]:
# 大的数据往后移动
nums[preIndex + gap] = nums[preIndex]
preIndex -= gap
# curNum插入的正确位置
nums[preIndex + gap] = curNum
# 更新间隔
gap //= 2
return nums
归并排序算法是一个递归过程,边界条件为当输入序列仅有一个元素时,直接返回,具体过程如下:
# 时间复杂度:最好:O(nlogn) 平均:O(nlogn) 最差:O(nlogn)
# 空间复杂度:O(n)
# 稳定性:稳定
def merge_sort(self, nums: List[int]) -> List[int]:
if len(nums) <= 1:
return nums
mid = len(nums) // 2
left = self.merge_sort(nums[:mid])
right = self.merge_sort(nums[mid:])
return self.merge(left, right)
def merge(self, left: List[int], right: List[int]) -> List[int]:
# 存储排序之后的结果
result = []
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# 剩余元素加入到result的结尾
result = result + left[i:] + right[j:]
return result
# 时间复杂度:最好:O(nlogn) 平均:O(nlogn) 最差:O(nlogn)
# 空间复杂度:O(1)
# 稳定性:不稳定
# 堆排序的核心:1.堆初始化 2.调整堆
def heap_sort(self, nums: List[int]) -> List[int]:
# 1.堆初始化,从最后一个非叶子节点创建大顶堆
for i in range(len(nums) // 2)[::-1]:
self.adjust_heap(nums, i, len(nums))
# 2.输出堆顶元素后,剩余元素继续调整为堆
for i in range(len(nums))[::-1]:
# 每次最大的元素在根节点
nums[0], nums[i] = nums[i], nums[0]
# 继续调整堆
self.adjust_heap(nums, 0, i)
return nums
# 调整堆
def adjust_heap(self, nums: List[int], i: int, l: int)->None:
# 左右孩子节点的索引
lchild, rchild = 2 * i + 1, 2 * i + 2
# 最大元素的索引
largest = i
# 从当前节点,左孩子以及右孩子节点选出最大元素的索引
if lchild < l and nums[lchild] > nums[largest]:
largest = lchild
if rchild < l and nums[rchild] > nums[largest]:
largest = rchild
# 如果当前元素不是最大值,则更换最大值,继续调整堆
if largest != i:
nums[largest], nums[i] = nums[i], nums[largest]
# largest调整后的值,大的元素在上面
self.adjust_heap(nums, largest, l)
# 时间复杂度:最佳:O(n+k) 最差:O(n+k) 平均:O(n+k)
# 空间复杂度:O(n+k)
# 稳定性:稳定
def count_sort(self, nums: List[int]) -> List[int]:
# 1.创建一个大小为:最大值-最小值+1的数组,初始值为0
bucket = [0] * (max(nums) - min(nums) + 1)
# 2.统计原数组中每个元素出现的个数,存储在新开辟的数组中
for num in nums:
bucket[num - min(nums)] += 1
# nums的下标
i = 0
# 根据每个元素出现的次数,按照新开辟数组的元素从小到大依次填充到原来的数组中
for j in range(len(bucket)):
while bucket[j] > 0:
nums[i] = j + min(nums)
bucket[j] -= 1
i += 1
return nums
# 时间复杂度:最佳:O(n+k) 最差:O(n²) 平均:O(n+k)
# 空间复杂度:O(n+k)
# 稳定性:稳定
def bucket_sort(self, nums: List[int]) -> List[int]:
# 1.数据分桶
# 定义桶的大小
bucketSize = 4
# 桶的个数
bucketCount = (max(nums) - min(nums)) // bucketSize + 1
# 初始化桶,二维数组
buckets = [[] for _ in range(bucketCount)]
# 2.数据入桶,利用函数映射将数据入桶
for num in nums:
buckets[(num - min(nums)) // bucketSize].append(num)
nums.clear() # 清空nums数组
# 3.桶内排序,合并结果
for bucket in buckets:
self.insert_sort(bucket)
# extend() 函数用于在列表末尾一次性追加另一个序列中的多个值
nums.extend(bucket)
return nums
这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异:
# 时间复杂度:最佳:O(n×k) 最差:O(n×k) 平均:O(n×k)
# 空间复杂度:O(n+k)
# 稳定性:稳定
def radix_sort(self, nums: List[int]) -> List[int]:
mod, div = 10, 1
# 最大元素位数的长度决定外循环的次数
mostBit = len(str(max(nums)))
# 初始化一个0-9的桶
buckets = [[] for i in range(mod)]
while mostBit:
# 数据入桶
for num in nums:
buckets[num // div % mod].append(num)
i = 0
# 收集结果,从每个桶中取数
for bucket in buckets:
while bucket:
nums[i] = bucket.pop(0)
i += 1
# 高位
div *= 10
mostBit -= 1
return nums
######################################################################################################