通俗解释选择、插入和冒泡排序

发布于:2024-10-18 ⋅ 阅读:(7) ⋅ 点赞:(0)

1. 选择排序(Selection Sort)

选择排序的过程就像我们选最小(或最大)的东西一样。它的操作逻辑是不断从未排序的部分中选出一个最小(或最大)的数,放到前面的已排序部分。想象一下,你有一堆扑克牌,想从小到大排列,每次你都从剩下的牌里选出最小的,放到前面。

步骤:

  • 首先,找到数组中最小的那个数,把它放到第一个位置。
  • 接着,忽略第一个数,再从剩下的数里找出最小的,把它放到第二个位置。
  • 依次类推,直到所有的数都放到了它应该的位置。

举个例子:
排序数组 [3, 1, 4, 5, 2]

  • 第一次:找到最小的 1,跟第一个数 3 交换,得到 [1, 3, 4, 5, 2]
  • 第二次:在剩下的 [3, 4, 5, 2] 里找到 2,交换到第二位,得到 [1, 2, 4, 5, 3]
  • 继续操作,直到数组有序。

2. 插入排序(Insertion Sort)

插入排序就像我们整理手里的扑克牌一样。每次拿一张新牌,都要把它插入到手里已经排好的牌中正确的位置。这个过程从小规模的已经排好的部分开始,逐渐扩大到整个数组。

步骤:

  • 从第二个数开始,跟前面排好的数比较,找到它应该插入的位置,把它插进去。
  • 每插入一个数,前面的部分就一直保持有序。
  • 继续处理后面的数,直到所有的数都插入到正确位置。

举个例子:
排序数组 [3, 1, 4, 5, 2]

  • 第一步:13 比较,插入到 3 的前面,得到 [1, 3, 4, 5, 2]
  • 第二步:4 已经比 3 大,不动,继续处理下一步。
  • 第三步:5 也不用动,处理下一步。
  • 第四步:2 和前面数依次比较,插入到 13 之间,得到 [1, 2, 3, 4, 5]

3. 冒泡排序(Bubble Sort)

冒泡排序的名字很形象,想象气泡从水底浮到水面。每次比较两个相邻的数,如果它们的顺序错了,就交换位置,把较大的数"冒"到后面。经过一次遍历,最大的数会被冒到最后一个位置。这样重复操作,直到所有数都排好。

步骤:

  • 从头开始,依次比较每对相邻的数,较大的往后移动。
  • 完成一轮比较后,最后一个数是最大的。
  • 再从头开始,对前面的数重复这个过程,每次让一个数冒到它正确的位置。
  • 直到没有数需要交换。

举个例子:
排序数组 [3, 1, 4, 5, 2]

  • 第一次:31 比较,交换,得到 [1, 3, 4, 5, 2];接着 45 不动;最后 52 交换,得到 [1, 3, 4, 2, 5]
  • 第二次:再来一遍,32 交换,得到 [1, 2, 3, 4, 5]
  • 数组已经排好序了。

总结:

  • 选择排序:每次选择最小的放到前面。
  • 插入排序:像整理扑克牌一样,每次把新牌插入到已排好的部分。
  • 冒泡排序:两两比较,把大的数“冒”到后面。

这三种排序算法都属于简单排序算法,适合小规模数据的排序。它们的时间复杂度都是 (O(n^2)),随着数据量的增加,效率会降低。