经典排序
MJX2023/10/31其他算法 排序
冒泡排序
- 共
n-1趟 - 从第一个开始往上无序区两两比较
- 一直重复直到有序
def bubble_sort(nums):
for i in range(len(nums) - 1):
for j in range(len(nums) - 1 - i):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
# 检验
nums = [3, 5, 1, 1, 7, 9, 4]
bubble_sort(nums)
print(nums)
# 如果某趟没有发生交换，那么就已经有序了
def bubble_sort_pro(nums):
for i in range(len(nums) - 1):
change_flag = 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]
change_flag = False
if change_flag: break
选择排序
- 共
n-1趟 - 第
i趟时，第i个待比较 - 从无序区选出最小数，和
i比较 - 交换直到有序
def select_sort(nums):
for i in range(len(nums) - 1):
min_loc = i
for j in range(i + 1, len(nums)):
if nums[j] < nums[min_loc]:
min_loc = j
nums[i], nums[min_loc] = nums[min_loc], nums[i]
插入排序
- 第一个数有序，共
n-1趟 - 从无序区选出拿出第一个数
- 从有序区最后开始遍历并往后移动一位，直到遇到第一个比它小的数
- 放在这个数后面
- 循环直到有序
def insert_sort(nums):
for i in range(1, len(nums)):
temp = nums[i]
j = i - 1
while j >= 0 and temp < nums[j]:
nums[j + 1] = nums[j]
j -= 1
nums[j + 1] = temp
快速排序
- 确定划分边界 x
- 将数组分为
<=x和>=x的两个小数组 - 分别递归两个数组
def quick_sort(nums, l, r):
if l >= r: return
i, j = l - 1, r + 1
x = nums[l + r >> 1] # 取中间值
while i < j:
i += 1 # 交换完一趟后还能往后走
while nums[i] < x:
i += 1
j -= 1
while nums[j] > x:
j -= 1
if i < j:
nums[i], nums[j] = nums[j], nums[i]
quick_sort(nums, l, j)
quick_sort(nums, j + 1, r)
void quick_sort(int nums[], int l, int r) {
if (r <= l) return;
int i = l - 1, j = r + 1, x = nums[l + r >> 1];
while (i < j) {
do i++; while (nums[i] < x);
do j--; while (nums[j] > x);
if (i < j) swap(nums[i], nums[j]);
}
quick_sort(nums, l, j);
quick_sort(nums, j + 1, r);
归并排序
- 将待排序的序列分成两部分(递归地)
- 将排好序的两部分合并起来
def merge_sort(nums, l, r):
if l >= r: return
mid = l + r >> 1
merge_sort(nums, l, mid)
merge_sort(nums, mid + 1, r)
i, j, tmp = l, mid + 1, []
while i <= mid and j <= r:
if nums[i] < nums[j]:
tmp.append(nums[i])
i += 1
else:
tmp.append(nums[j])
j += 1
tmp += nums[i: mid + 1]
tmp += nums[j: r + 1]
nums[l: r + 1] = tmp
- 分成子问题
- 递归处理子问题
- 子问题合并