手动实现排序算法:插入排序与选择排序的比较
插入排序和选择排序都是简单且经典的排序算法,适合用来排序小规模数据。虽然两者都属于O(n^2)时间复杂度的排序算法,但它们的工作原理有一些不同。下面是对这两种算法的比较及其手动实现。
插入排序 (Insertion Sort)
工作原理:
插入排序的思想是将数组分为已排序和未排序两部分。初始时,认为第一个元素是已排序的,从第二个元素开始,逐个将未排序的元素插入到已排序的部分中,保持已排序部分的有序性。
算法步骤:
1. 从第二个元素开始遍历数组。
2. 取出当前元素作为关键值,和已排序部分的元素从右向左比较。
3. 如果已排序元素大于关键值,则将已排序元素右移。
4. 将关键值插入到合适的位置。
5. 重复直到数组末尾。
代码实现:
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
# 将已经排序好的元素位置右移,直到找到比key小的位置
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
选择排序 (Selection Sort)
工作原理:
选择排序每次从待排序的数据中选出最小(或最大)的元素,放在序列的起始位置,直到所有的元素均被处理完成。
算法步骤:
1. 从数组的第一个元素开始,遍历整个数组,找出最小元素。
2. 将该最小元素与未排序部分的第一个元素交换。
3. 继续遍历剩余未排序部分,重复步骤1和2,直到整个数组有序。
代码实现:
def selection_sort(arr):
for i in range(len(arr)):
# 假设当前i位置为最小值位置
min_idx = i
# 找到最小的值
for j in range(i + 1, len(arr)):
if arr[j] < arr[min_idx]:
min_idx = j
# 将找到的最小值与i位置的值交换
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
比较与总结
- 时间复杂度:两者的时间复杂度都是O(n^2),但插入排序通常在序列部分有序的时候表现更好。
- 空间复杂度:两者都是原地排序算法,空间复杂度O(1)。
- 稳定性:插入排序是稳定的,即相等的元素排序后相对位置不变。而选择排序是不稳定的,因为最小元素的调换可能会打破相同元素的相对顺序。
- 适用场景:插入排序更适合部分有序的数据集,选择排序则在额外交换较少要求下可以使用,但整体上应用较少。
两种算法都比较适合用于教学或处理小规模数据,但在实际工程中,更多地使用快速排序、归并排序等高级排序算法。