提示信息

手动实现排序算法:插入排序与选择排序的比较

不哭 已关注

插入排序和选择排序都是简单且经典的排序算法,适合用来排序小规模数据。虽然两者都属于O(n^2)时间复杂度的排序算法,但它们的工作原理有一些不同。下面是对这两种算法的比较及其手动实现。

插入排序 (Insertion Sort)

工作原理
插入排序的思想是将数组分为已排序和未排序两部分。初始时,认为第一个元素是已排序的,从第二个元素开始,逐个将未排序的元素插入到已排序的部分中,保持已排序部分的有序性。

算法步骤
1. 从第二个元素开始遍历数组。
2. 取出当前元素作为关键值,和已排序部分的元素从右向左比较。
3. 如果已排序元素大于关键值,则将已排序元素右移。
4. 将关键值插入到合适的位置。
5. 重复直到数组末尾。

代码实现

  1. def insertion_sort(arr):
  2. for i in range(1, len(arr)):
  3. key = arr[i]
  4. j = i - 1
  5. # 将已经排序好的元素位置右移,直到找到比key小的位置
  6. while j >= 0 and arr[j] > key:
  7. arr[j + 1] = arr[j]
  8. j -= 1
  9. arr[j + 1] = key
  10. return arr

选择排序 (Selection Sort)

工作原理
选择排序每次从待排序的数据中选出最小(或最大)的元素,放在序列的起始位置,直到所有的元素均被处理完成。

算法步骤
1. 从数组的第一个元素开始,遍历整个数组,找出最小元素。
2. 将该最小元素与未排序部分的第一个元素交换。
3. 继续遍历剩余未排序部分,重复步骤1和2,直到整个数组有序。

代码实现

  1. def selection_sort(arr):
  2. for i in range(len(arr)):
  3. # 假设当前i位置为最小值位置
  4. min_idx = i
  5. # 找到最小的值
  6. for j in range(i + 1, len(arr)):
  7. if arr[j] < arr[min_idx]:
  8. min_idx = j
  9. # 将找到的最小值与i位置的值交换
  10. arr[i], arr[min_idx] = arr[min_idx], arr[i]
  11. return arr

比较与总结

  1. 时间复杂度:两者的时间复杂度都是O(n^2),但插入排序通常在序列部分有序的时候表现更好。
  2. 空间复杂度:两者都是原地排序算法,空间复杂度O(1)。
  3. 稳定性:插入排序是稳定的,即相等的元素排序后相对位置不变。而选择排序是不稳定的,因为最小元素的调换可能会打破相同元素的相对顺序。
  4. 适用场景:插入排序更适合部分有序的数据集,选择排序则在额外交换较少要求下可以使用,但整体上应用较少。

两种算法都比较适合用于教学或处理小规模数据,但在实际工程中,更多地使用快速排序、归并排序等高级排序算法。

    遇到难题? "AI大模型GPT4.0、GPT" 是你的私人解答专家! 点击按钮去提问......
不哭 关注 已关注

最近一次登录:2024-11-20 20:36:13   

暂时还没有签名,请关注我或评论我的文章
×
免费图表工具,画流程图、架构图