选择排序选择排序算法。选择什么？但是最少数量！！！
算法的时间复杂度– O(n2)
该算法的工作原理如下：
- 我们从左到右循环遍历数组，记住当前的起始索引和索引处的数字，我们称之为数字 A
- 在循环内，我们运行另一个循环从左到右，寻找小于 A 的内容
- 当我们找到较小的那个时，我们会记住索引，现在较小的那个就变成了数字A
- 当内循环结束时，交换起始索引处的数字和数字A
- 完成上层循环后，我们得到一个排序数组
算法执行示例：
(29, 49, 66, 35, 7, 12, 80)
29 > 7
(7, 49, 66, 35, 29, 12, 80)
Round 1 ENDED
Round 2
(7, 49, 66, 35, 29, 12, 80)
49 > 35
35 > 29
29 > 12
(7, 12, 66, 35, 29, 49, 80)
Round 2 ENDED
Round 3
(7, 12, 66, 35, 29, 49, 80)
66 > 35
35 > 29
(7, 12, 29, 35, 66, 49, 80)
Round 3 ENDED
Round 4
(7, 12, 29, 35, 66, 49, 80)
(7, 12, 29, 35, 66, 49, 80)
Round 4 ENDED
Round 5
(7, 12, 29, 35, 66, 49, 80)
66 > 49
(7, 12, 29, 35, 49, 66, 80)
Round 5 ENDED
Round 6
(7, 12, 29, 35, 49, 66, 80)
(7, 12, 29, 35, 49, 66, 80)
Round 6 ENDED
Sorted: (7, 12, 29, 35, 49, 66, 80)
尚未在 Rosetta 代码上找到 Objective-C 实现 ，我自己写道：
#include <Foundation/Foundation.h>
@implementation SelectionSort
- (void)performSort:(NSMutableArray *)numbers
{
NSLog(@"%@", numbers);
for (int startIndex = 0; startIndex < numbers.count-1; startIndex++) {
int minimalNumberIndex = startIndex;
for (int i = startIndex + 1; i < numbers.count; i++) {
id lhs = [numbers objectAtIndex: minimalNumberIndex];
id rhs = [numbers objectAtIndex: i];
if ([lhs isGreaterThan: rhs]) {
minimalNumberIndex = i;
}
}
id temporary = [numbers objectAtIndex: minimalNumberIndex];
[numbers setObject: [numbers objectAtIndex: startIndex]
atIndexedSubscript: minimalNumberIndex];
[numbers setObject: temporary
atIndexedSubscript: startIndex];
}
NSLog(@"%@", numbers);
}
@end Собрать и запустить можно либо на MacOS/Xcode, либо на любой операционной системе поддерживающей GNUstep, например у меня собирается Clang на Arch Linux.
Скрипт сборки:
main.m \
-lobjc \
`gnustep-config --objc-flags` \
`gnustep-config --objc-libs` \
-I /usr/include/GNUstepBase \
-I /usr/lib/gcc/x86_64-pc-linux-gnu/12.1.0/include/ \
-lgnustep-base \
-o SelectionSort \Links
https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/selectionSort
Sources
https://rosettacode.org/wiki/Sorting_algorithms/Selection_sort
https://ru.wikipedia.org/wiki/Сортировка_выбором
https://en.wikipedia.org/wiki/Selection_sort
https://www.youtube.com/watch?v=LJ7GYbX7qpM
