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]
- 第一步:
1
和3
比较,插入到3
的前面,得到[1, 3, 4, 5, 2]
。 - 第二步:
4
已经比3
大,不动,继续处理下一步。 - 第三步:
5
也不用动,处理下一步。 - 第四步:
2
和前面数依次比较,插入到1
和3
之间,得到[1, 2, 3, 4, 5]
。
3. 冒泡排序(Bubble Sort)
冒泡排序的名字很形象,想象气泡从水底浮到水面。每次比较两个相邻的数,如果它们的顺序错了,就交换位置,把较大的数"冒"到后面。经过一次遍历,最大的数会被冒到最后一个位置。这样重复操作,直到所有数都排好。
步骤:
- 从头开始,依次比较每对相邻的数,较大的往后移动。
- 完成一轮比较后,最后一个数是最大的。
- 再从头开始,对前面的数重复这个过程,每次让一个数冒到它正确的位置。
- 直到没有数需要交换。
举个例子:
排序数组 [3, 1, 4, 5, 2]
- 第一次:
3
和1
比较,交换,得到[1, 3, 4, 5, 2]
;接着4
和5
不动;最后5
和2
交换,得到[1, 3, 4, 2, 5]
。 - 第二次:再来一遍,
3
和2
交换,得到[1, 2, 3, 4, 5]
。 - 数组已经排好序了。
总结:
- 选择排序:每次选择最小的放到前面。
- 插入排序:像整理扑克牌一样,每次把新牌插入到已排好的部分。
- 冒泡排序:两两比较,把大的数“冒”到后面。
这三种排序算法都属于简单排序算法,适合小规模数据的排序。它们的时间复杂度都是 (O(n^2)),随着数据量的增加,效率会降低。