选择排序(Selection Sort)算法是最基本的排序算法,是学习编程语言最先需要学会的排序算法之一。它可以按照元素值的大小序次,一一将最小值、第二小值等等的元素排入串行中的正确索引位置内。
选择排序法(Selection Sort)
选择排序法的概念
选择排序法是以土法炼钢的方式按照次序走访串行中的每个索引位置,并在每次迭代时去往后选择出剩余的最小元素值,来与目前的索引位置的元素做交换。如此一来,串行中的元素就能以递增的方式来排列。
至于要如何「往后选择出剩余的最大元素值或最小元素值」呢?我们可以先假设目前索引位置的元素值是最小的,然后再去走访之后的所有元素,如果发现有比目前索引位置的元素值还小的元素,就把它的索引值记下来,然后再继续走访,再用其它走访到的元素与目前记下的索引位置的元素值进行比较,如果又发现更小的,就再把索引值记下。如此一来,剩余的元素走访完之后,就知道其中最小值的索引位置了。如果这个索引位置并不是目前走访到的索引位置,就把这两个索引位置的元素做交换。
所以说,在走访到串行的第一个元素,并按照上述方式处理完成之后,串行的第一个元素必定会是最小值。在走访到串行的第二个元素,并按照上述方式处理完成之后,串行的第二个元素必定会是第二小值。
选择排序法的过程
假设现在有个数组数据,内容如下:
索引 0 1 2 3 4 5 6 7 8 9 数值 69 81 30 38 9 2 47 61 32 79
要如何将它递增排列呢?
一开始,要将重点聚焦于数组最前端的位置,因为我们要先将整个数组的最小值交换到数组的最前端。
先假设目前数组最前端的元素为最小值。
●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
→
再与其之后的元素比大小,若找到比目前假设最小元素还小的元素,就记下索引值,如下表:
●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
└┬┘
69 < 81
因为 69 比 81 小,所以再比较下一个索引值的元素的大小,如下表:
●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
└─┬─┘
69 > 30
69 比 30 大,所以目前最小元素的索引位置变成 2。
●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
→
持续向后判断大小并更改当前最小元素的索引位置,直到判断至最尾端:
●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
└┬┘
30 < 38
●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
└─┬─┘
30 > 9
●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
→
●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
└┬┘
9 > 2
●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
→
●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
└┬┘
2 < 47
●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
└─┬─┘
2 < 61
●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
└──┬──┘
2 < 32
●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
└───┬───┘
2 < 79
●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
◎
判断至最尾端后,即可找到最小元素的位置,再将最前端的元素和最小元素交换,如下表:
●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 81 30 38 9 69 47 61 32 79
└─────────┘
接着用同样的方法继续找出第二小的元素,并将其交换至前端第二个位置,再找出第三小的元素,并将其交换至前端第三个位置。直到所有元素位置都被确认过之后,数组就排序完成了!完整过程如下:
●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
→
●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
└┬┘
69 < 81
●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
└─┬─┘
69 > 30
●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
→
●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
└┬┘
30 < 38
●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
└─┬─┘
30 > 9
●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
→
●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
└┬┘
9 > 2
●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
→
●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
└┬┘
2 < 47
●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
└─┬─┘
2 < 61
●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
└──┬──┘
2 < 32
●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
└───┬───┘
2 < 79
●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
◎
●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 81 30 38 9 69 47 61 32 79
└─────────┘
○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 81 30 38 9 69 47 61 32 79
→
○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 81 30 38 9 69 47 61 32 79
└┬┘
81 > 30
○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 81 30 38 9 69 47 61 32 79
→
○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 81 30 38 9 69 47 61 32 79
└┬┘
30 < 38
○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 81 30 38 9 69 47 61 32 79
└─┬─┘
30 > 9
○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 81 30 38 9 69 47 61 32 79
→
○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 81 30 38 9 69 47 61 32 79
└┬┘
9 < 69
○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 81 30 38 9 69 47 61 32 79
└─┬─┘
9 < 47
○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 81 30 38 9 69 47 61 32 79
└──┬──┘
9 < 61
○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 81 30 38 9 69 47 61 32 79
└───┬───┘
9 < 32
○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 81 30 38 9 69 47 61 32 79
└────┬────┘
9 < 79
○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 81 30 38 9 69 47 61 32 79
◎
○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 81 69 47 61 32 79
└─────┘
○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 81 69 47 61 32 79
→
○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 81 69 47 61 32 79
└┬┘
30 < 38
○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 81 69 47 61 32 79
└─┬─┘
30 < 81
○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 81 69 47 61 32 79
└──┬──┘
30 < 69
○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 81 69 47 61 32 79
└───┬───┘
30 < 47
○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 81 69 47 61 32 79
└────┬────┘
30 < 61
○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 81 69 47 61 32 79
└─────┬─────┘
30 < 32
○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 81 69 47 61 32 79
└──────┬──────┘
30 < 79
○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 81 69 47 61 32 79
◎
○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 81 69 47 61 32 79
→
○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 81 69 47 61 32 79
└┬┘
38 < 81
○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 81 69 47 61 32 79
└─┬─┘
38 < 69
○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 81 69 47 61 32 79
└──┬──┘
38 < 47
○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 81 69 47 61 32 79
└───┬───┘
38 < 61
○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 81 69 47 61 32 79
└────┬────┘
38 > 32
○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 81 69 47 61 32 79
→
○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 81 69 47 61 32 79
└┬┘
32 < 79
○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 81 69 47 61 32 79
◎
○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 81 69 47 61 38 79
└─────────┘
○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 81 69 47 61 38 79
→
○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 81 69 47 61 38 79
└┬┘
81 > 69
○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 81 69 47 61 38 79
→
○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 81 69 47 61 38 79
└┬┘
69 > 47
○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 81 69 47 61 38 79
→
○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 81 69 47 61 38 79
└┬┘
47 < 61
○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 81 69 47 61 38 79
└─┬─┘
47 > 38
○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 81 69 47 61 38 79
→
○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 81 69 47 61 38 79
└┬┘
38 < 79
○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 81 69 47 61 38 79
◎
○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 69 47 61 81 79
└───────┘
○ ○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 69 47 61 81 79
→
○ ○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 69 47 61 81 79
└┬┘
69 > 47
○ ○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 69 47 61 81 79
→
○ ○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 69 47 61 81 79
└┬┘
47 < 61
○ ○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 69 47 61 81 79
└─┬─┘
47 < 81
○ ○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 69 47 61 81 79
└──┬──┘
47 < 79
○ ○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 69 47 61 81 79
◎
○ ○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 69 61 81 79
└─┘
○ ○ ○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 69 61 81 79
→
○ ○ ○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 69 61 81 79
└┬┘
69 > 61
○ ○ ○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 69 61 81 79
→
○ ○ ○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 69 61 81 79
└┬┘
61 < 81
○ ○ ○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 69 61 81 79
└─┬─┘
61 < 79
○ ○ ○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 69 61 81 79
◎
○ ○ ○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 81 79
└─┘
○ ○ ○ ○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 81 79
→
○ ○ ○ ○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 81 79
└┬┘
69 < 81
○ ○ ○ ○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 81 79
└─┬─┘
69 < 79
○ ○ ○ ○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 81 79
◎
○ ○ ○ ○ ○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 81 79
→
○ ○ ○ ○ ○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 81 79
└┬┘
81 > 79
○ ○ ○ ○ ○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 81 79
→
○ ○ ○ ○ ○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 81 79
◎
○ ○ ○ ○ ○ ○ ○ ○ ●
※
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 79 81
└─┘
○ ○ ○ ○ ○ ○ ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 79 81
选择排序法的程序实作
选择排序法的复杂度
以 #{{n}}# 来表示要排序的数据笔数。
| 项目 | 值 | 备注 |
|---|---|---|
| 最差时间复杂度 | #{{O(n^2)}}# | |
| 最佳时间复杂度 | #{{O(n^2)}}# | |
| 平均时间复杂度 | #{{O(n^2)}}# | |
| 最差空间复杂度 | #{{O(1)}}# | |
| 是否稳定 | 否 |
交换排序法(Exchange Sort)
交换排序法的概念
交换排序法与上面介绍的选择排序法非常类似,只不过交换排序法不使用额外的空间来保存走访串行时找到的当前最小元素的索引值,而是直接将找到的较小元素进行交换。由于这个算法需要在串行中一直做交换元素的动作,因此在绝大部分情况下会比选择排序法还慢,几乎没有人会想使用这个算法,这也是为什么笔者会将它放到这篇文章的最后来做介绍。
交换排序法的过程
假设现在有个数组数据,内容如下:
索引 0 1 2 3 4 5 6 7 8 9 数值 69 81 30 38 9 2 47 61 32 79
要如何将它递增排列呢?
一开始,要将重点聚焦于数组最前端的位置,因为我们要先将整个数组的最小值交换到数组的最前端。
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
→
再与其之后的元素比大小,若找到比目前走访到的元素还小的元素,就直接进行交换,然后继续往下找;若没找到比目前走访到的元素还小的元素,就不进行交换,然后继续往下找。完整过程如下:
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
→
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
└┬┘
69 < 81
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
└─┬─┘
69 > 30
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
◎
●
索引 0 1 2 3 4 5 6 7 8 9
数值 30 81 69 38 9 2 47 61 32 79
└───┘
●
索引 0 1 2 3 4 5 6 7 8 9
数值 30 81 69 38 9 2 47 61 32 79
└──┬──┘
30 < 38
●
索引 0 1 2 3 4 5 6 7 8 9
数值 30 81 69 38 9 2 47 61 32 79
└───┬───┘
30 > 9
●
索引 0 1 2 3 4 5 6 7 8 9
数值 30 81 69 38 9 2 47 61 32 79
◎
●
索引 0 1 2 3 4 5 6 7 8 9
数值 9 81 69 38 30 2 47 61 32 79
└───────┘
●
索引 0 1 2 3 4 5 6 7 8 9
数值 9 81 69 38 30 2 47 61 32 79
└────┬────┘
9 > 2
●
索引 0 1 2 3 4 5 6 7 8 9
数值 9 81 69 38 30 2 47 61 32 79
◎
●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 81 69 38 30 9 47 61 32 79
└─────────┘
●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 81 69 38 30 9 47 61 32 79
└─────┬─────┘
2 < 47
●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 81 69 38 30 9 47 61 32 79
└──────┬──────┘
2 < 61
●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 81 69 38 30 9 47 61 32 79
└───────┬───────┘
2 < 32
●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 81 69 38 30 9 47 61 32 79
└────────┬────────┘
2 < 79
○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 81 69 38 30 9 47 61 32 79
→
○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 81 69 38 30 9 47 61 32 79
└┬┘
81 > 69
○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 81 69 38 30 9 47 61 32 79
◎
○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 69 81 38 30 9 47 61 32 79
└─┘
○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 69 81 38 30 9 47 61 32 79
└─┬─┘
69 > 38
○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 69 81 38 30 9 47 61 32 79
◎
○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 38 81 69 30 9 47 61 32 79
└───┘
○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 38 81 69 30 9 47 61 32 79
└──┬──┘
38 > 30
○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 38 81 69 30 9 47 61 32 79
◎
○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 30 81 69 38 9 47 61 32 79
└─────┘
○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 30 81 69 38 9 47 61 32 79
└───┬───┘
30 > 9
○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 30 81 69 38 9 47 61 32 79
◎
○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 81 69 38 30 47 61 32 79
└───────┘
○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 81 69 38 30 47 61 32 79
└────┬────┘
9 < 47
○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 81 69 38 30 47 61 32 79
└─────┬─────┘
9 < 61
○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 81 69 38 30 47 61 32 79
└──────┬──────┘
9 < 32
○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 81 69 38 30 47 61 32 79
└───────┬───────┘
9 < 79
○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 81 69 38 30 47 61 32 79
→
○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 81 69 38 30 47 61 32 79
└┬┘
81 > 69
○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 81 69 38 30 47 61 32 79
◎
○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 69 81 38 30 47 61 32 79
└─┘
○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 69 81 38 30 47 61 32 79
└─┬─┘
69 > 38
○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 69 81 38 30 47 61 32 79
◎
○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 38 81 69 30 47 61 32 79
└───┘
○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 38 81 69 30 47 61 32 79
└──┬──┘
38 > 30
○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 38 81 69 30 47 61 32 79
◎
○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 81 69 38 47 61 32 79
└─────┘
○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 81 69 38 47 61 32 79
└───┬───┘
30 < 47
○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 81 69 38 47 61 32 79
└────┬────┘
30 < 61
○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 81 69 38 47 61 32 79
└─────┬─────┘
30 < 32
○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 81 69 38 47 61 32 79
└──────┬──────┘
30 < 79
○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 81 69 38 47 61 32 79
→
○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 81 69 38 47 61 32 79
└┬┘
81 > 69
○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 81 69 38 47 61 32 79
◎
○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 69 81 38 47 61 32 79
└─┘
○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 69 81 38 47 61 32 79
└─┬─┘
69 > 38
○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 69 81 38 47 61 32 79
◎
○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 81 69 47 61 32 79
└───┘
○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 81 69 47 61 32 79
└──┬──┘
38 < 47
○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 81 69 47 61 32 79
└───┬───┘
38 < 61
○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 81 69 47 61 32 79
└────┬────┘
38 > 32
○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 81 69 47 61 32 79
◎
○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 81 69 47 61 38 79
└─────────┘
○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 81 69 47 61 38 79
└─────┬─────┘
32 < 79
○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 81 69 47 61 38 79
→
○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 81 69 47 61 38 79
└┬┘
81 > 69
○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 81 69 47 61 38 79
◎
○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 69 81 47 61 38 79
└─┘
○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 69 81 47 61 38 79
└─┬─┘
69 > 47
○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 69 81 47 61 38 79
◎
○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 47 81 69 61 38 79
└───┘
○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 47 81 69 61 38 79
└──┬──┘
47 < 61
○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 47 81 69 61 38 79
└───┬───┘
47 > 38
○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 47 81 69 61 38 79
◎
○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 81 69 61 47 79
└───────┘
○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 81 69 61 47 79
└────┬────┘
38 < 79
○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 81 69 61 47 79
→
○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 81 69 61 47 79
└┬┘
81 > 69
○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 81 69 61 47 79
◎
○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 69 81 61 47 79
└─┘
○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 69 81 61 47 79
└─┬─┘
69 > 61
○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 69 81 61 47 79
◎
○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 61 81 69 47 79
└───┘
○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 61 81 69 47 79
└──┬──┘
61 > 47
○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 61 81 69 47 79
◎
○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 81 69 61 79
└─────┘
○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 81 69 61 79
└───┬───┘
47 < 79
○ ○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 81 69 61 79
→
○ ○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 81 69 61 79
└┬┘
81 > 69
○ ○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 81 69 61 79
◎
○ ○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 69 81 61 79
└─┘
○ ○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 69 81 61 79
└─┬─┘
69 > 61
○ ○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 69 81 61 79
◎
○ ○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 81 69 79
└───┘
○ ○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 81 69 79
└──┬──┘
61 < 79
○ ○ ○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 81 69 79
→
○ ○ ○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 81 69 79
└┬┘
81 > 69
○ ○ ○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 81 69 79
◎
○ ○ ○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 81 79
└─┘
○ ○ ○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 81 79
└─┬─┘
69 < 79
○ ○ ○ ○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 81 79
→
○ ○ ○ ○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 81 79
└┬┘
81 > 79
○ ○ ○ ○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 81 79
◎
○ ○ ○ ○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 79 81
└─┘
○ ○ ○ ○ ○ ○ ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 79 81
交换排序法的程序实作
交换排序法的复杂度
以 #{{n}}# 来表示要排序的数据笔数。
| 项目 | 值 | 备注 |
|---|---|---|
| 最差时间复杂度 | #{{O(n^2)}}# | |
| 最佳时间复杂度 | #{{O(n^2)}}# | |
| 平均时间复杂度 | #{{O(n^2)}}# | |
| 最差空间复杂度 | #{{O(1)}}# | |
| 是否稳定 | 否 |


