数组的排序算法（部分）
Posted on Wed, 25 Dec 2024 10:13:01 +0800 by LiangMingJian
冒泡排序
冒泡排序要求程序重复地遍历数组，通过相邻元素间的比较与交换，使值较小的元素逐步从后面移到前面，值较大的元素从前面移到后面，这个过程就像水底的气泡一样从底部「冒泡」到水面。
操作时，选择第 1 个和第 2 个数字，如果第 1 个大于第 2 个，则二者交换位置（假设是升序排列）。之后选择第 2个和第 3 个数字，类似交换处理。一轮下来后，最大的数字会冒泡到最后一位。接下来，忽略已经排好的数字，对于剩下的数字再来一轮，直到所有的数字都排列完成。
from typing import List
def bubbleSort(nums: List[int]) -> List[int]:
# 迭代最多需要执行 n - 1 次，所有元素都要被排列
# 第 1 次迭代找到第 1 个，第 2 次找到第 2 个...
# 第 n - 1 次找到第 n - 1 个，又因为算法操作是交换。
# 所以找到第 n - 1 个就找到第 n 个，不必再执行 1 个循环，循环次数 n - 1
for i in range(len(nums) - 1):
# 设置一个交换标志位
# 如果数组没有进行过交换，则表明数组已经提前排序好，可以提前跳出循环
flag = False
# 因为当前元素要和后面的元素比较或交换，所以只需要遍历数组 n - 1 个元素
# 又因为迭代已经执行 i 次，有 i 个元素已经排列好了，所以这些元素不需要再次遍历
# 所以下面循环从数组第 1 个元素开始到第 n - 1 - i 个元素
for j in range(len(nums) - i - 1):
# 相邻两个元素进行比较，如果前者大于后者，则交换位置
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
flag = True
# 此趟遍历未交换任何元素，排序完成，直接跳出
if not flag:
break
return nums
插入排序
插入排序将数组分为有序区间和无序区间两个部分，程序会对无序区间进行循环，每次循环取出一个元素，然后将这个元素插入到有序区间的适当位置，直到排序完成。
操作时，从第一个元素开始，该元素可以认为已经被排序。然后取出下一个元素，在已经排序的元素序列中从后向前扫描，并把取出的元素放到已排序的元素中间的合适位置。重复上述步骤，就像排队一样，依次每次挑一个同学，把该同学插入到已经排好的部分队伍里。
from typing import List
def insertionSort(nums: List[int]) -> List[int]:
# 遍历无序区间
# 循环从列表第 2 个开始，默认第 1 个已经插入完成
for i in range(1, len(nums)):
temp = nums[i]
j = i
# 从右至左遍历有序区间
while j > 0 and nums[j - 1] > temp:
# 将有序区间中插入位置右侧的元素依次右移一位
# 在原数组操作，第 1 次右移，数据覆盖了 temp 原本的位置
# 后续 temp 找到插入位置后，数据重新插入，不会丢失
nums[j] = nums[j - 1]
# 序号减 1，位置往前 1 个
# 当 j = 0 的时候，有序序列被走完
# 当 nums[j - 1] <= temp 的时候，说明这个是插入位置，可以插入了
j -= 1
# 将该元素插入到适当位置
nums[j] = temp
return nums
快速排序
快速排序采用经典的分治策略，选择数组中某个元素作为基准数，通过一趟排序将数组分为独立的两个子数组，其中一个子数组中所有元素值都比基准数小，另一个子数组中所有元素值都比基准数大，然后再按照同样的方式递归的对两个子数组分别进行快速排序，以达到整个数组有序。
操作时，从数列中挑出一个元素，称为基准，然后重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。
在这个分区结束之后，该基准就处于数列的中间位置，接着递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。当递归到最底部时，数列的大小是零或一，此时数列已经排序完毕。
from typing import List
# 哨兵划分：
# 将比基准数小的元素移动到基准数左侧，
# 将比基准数大的元素移动到基准数右侧，
# 最后将基准数放到正确位置上
def partition(nums: List[int], low: int, high: int) -> int:
# 以第 1 位元素为基准数
# 在首次执行，以数组的第 1 位作为基准数，即 nums[0] = 0
# 在递归执行，以子数组的第 1 位作为基准数，即 nums[low]
pivot = nums[low]
i, j = low, high
while i < j:
# 从右向左找到第 1 个小于基准数的元素
while i < j and nums[j] >= pivot:
j -= 1
# 从左向右找到第 1 个大于基准数的元素
while i < j and nums[i] <= pivot:
i += 1
# 交换元素
nums[i], nums[j] = nums[j], nums[i]
# 因为使用第 1 位元素作为基准数，
# 所以这个时候只要将左侧数组（比基准数小的数组）头尾调换就能将基准节点放到正确位置上
nums[i], nums[low] = nums[low], nums[i]
# 返回基准数的索引
return i
def quickSort(nums: List[int], low: int, high: int) -> List[int]:
# 在首次执行，low，high 分别是指向数组首尾的指针
# 在递归执行，low，high 分别是指向各个子数组首尾的指针
if low < high:
# 按照基准数的位置，将数组划分为左右两个子数组
pivot_i = partition(nums, low, high)
# 递归分解：对左右两个子数组分别进行递归快速排序
quickSort(nums, low, pivot_i - 1)
quickSort(nums, pivot_i + 1, high)
return nums
arr = [5,2,3,2,123,23,12,3213,1321,44,3]
res = quickSort(arr, 0, len(arr)-1)
print(res)
————————————