算法之排序-选择排序

排序算法之选择排序

选择排序将数组分为两个部分,一部分是已经排好序的子序列,还有未排序的部分。

  1. 在选择排序的每次迭代中,寻找未排序部分的最小值,将其插入到已排序子序列的最后。
  2. 当未排序部分个数为1时,结束算法。
  • 时间复杂度: $O(n^2)$
  • 辅助空间: $O(1)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
arr [] = 64 25 12 22 11
排序部分|未排序部分
|64 25 12 22 11
第一次迭代:
找到arr[0...4]中的最小元素,并将其放在arr[0]
11 |25 12 22 64

第二次迭代:
找到arr[1...4]中的最小元素,并将其放在arr [1]
11 12 |25 22 64

第三次迭代:
找到arr [2...4]中的最小元素,并将其放在arr [2]
11 12 22 |25 64

第四次迭代:
找到arr [3 ... 4]中的最小元素,并将其放在arr [3]
11 12 22 25 |64

此时未排序部分只有64,结束算法

代码实现见SelectionSort

-------------本文结束感谢您的阅读-------------
坚持分享,您的支持将鼓励我继续创作!
0%