「排序算法」专题 1：选择排序（了解）
这里和大家分享一下我学习的「基础排序算法」的知识点。
我从零基础到真正入门算法，就是从学习排序算法开始的，所以「排序算法」是我的初恋，差不多 3 年了。排序算法作为一项需求，它足够简单，是学习基础算法思想（例如：分治算法、减治思想、递归写法）的很好的学习材料。 如果觉得算法难，无法入手，不妨从写好一个排序算法开始。
如果是面试遇到写排序算法，一般还是先问清楚数据的特点，有的时候可能还会给具体的业务场景，在面试官肯定采用的算法之后再编码，不要一上来就手撕快排。
先说干货：
1、学习算法的可视化网站：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
大家点到 Sorting 这一章节，会看到我这篇题解介绍到的 10 大排序算法，而且还是交互式的，强烈推荐大家去点一下。
建议：先了解算法的思路，再去理解代码是怎么写的。如果看书，看我后面总结的不太清楚的地方，大家自己点一下这个网站，就会非常清楚了，还挺好玩的。
2、《算法 4》、《算法导论》、《阿里巴巴 Java 开发手册》下载
以下介绍的内容来自《算法 4》和《算法导论》，它们介绍的算法思想足够经典，但不是最新研究结果，也并非最快。如果想研究最新排序算法的结论，可以参考最新的学术论文，或者是在互联网上搜索相关资料，或者是查看您当前所使用语言关于排序部分的源代码。
（依然是啰嗦两句：《算法 4》和《算法导论》不是面向笔试和面试的书籍，对于新接触算法的朋友，可以把它们作为在「力扣」刷题的参考书，遇到什么知识点不会了，再去查，除非是专业的研究人员，看这两本书的时候建议忽略其中的数学证明和公式，只挑对自己有用的部分来看）。
「算法」的入门，我们从「排序算法」开始。
希望通过「排序算法」这一部分的学习，能够让我们认识到「算法」的魅力。「算法」不仅仅只存在与我们的面试中（那时只是因为我不知道「算法」而已），「算法」无处不在，「算法」很有用。
选择排序的思路
思路：每一轮选取未排定的部分中最小的那个元素交换到未排定部分的最开头，经过若干个步骤，就能排定整个数组。即：先选出最小的，再选出第二小的，以此类推。
Java 代码：
import java.util.Arrays;
public class Solution {
public int[] sortArray(int[] nums) {
int len = nums.length;
// 循环不变量：[0, i) 有序，且该区间里所有元素就是最终排定的样子
for (int i = 0; i < len - 1; i++) {
// 选择区间 [i, len - 1] 里最小的元素的索引，交换到下标 i
int minIndex = i;
for (int j = i + 1; j < len; j++) {
if (nums[j] < nums[minIndex]) {
minIndex = j;
}
}
swap(nums, i, minIndex);
}
return nums;
}
private void swap(int[] nums, int index1, int index2) {
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
public static void main(String[] args) {
int[] nums = {5, 2, 3, 1};
Solution solution = new Solution();
int[] res = solution.sortArray(nums);
System.out.println(Arrays.toString(res));
}
}Python 代码：
from sorting.sorting_util import SortingUtil
from sorting.examples import GenerateRandomArrayStrategy
class SelectionSort:
# 选择排序：每一轮选择最小的元素排在前面
def __str__(self):
return "选择排序"
@SortingUtil.cal_time
def sort(self, arr):
size = len(arr)
for i in range(size - 1):
min_index = i
for j in range(i + 1, size):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
if __name__ == '__main__':
SortingUtil.test_sorting_algorithm(SelectionSort(), GenerateRandomArrayStrategy(5000))
SortingUtil.test_sorting_algorithm(SelectionSort(), GenerateRandomArrayStrategy(10000))复杂度分析：
- 时间复杂度：$O(N^2)$，这里 $N$ 是数组的长度；
- 空间复杂度：$O(1)$，使用到常数个临时变量。
练习
1、使用「选择排序」完成「力扣」第 912 题：排序数组。
总结
- 算法思想 1：贪心算法
每一次决策只看当前，当前最优，则全局最优。注意：这种思想不是任何时候都适用。
- 算法思想 2：减治思想
外层循环每一次都能排定一个元素，问题的规模逐渐减少，直到全部解决，即「大而化小，小而化了」。运用「减治思想」很典型的算法就是大名鼎鼎的「二分查找」。
- 优点：交换次数最少。
「选择排序」看起来好像最没有用，但是如果在交换成本较高的排序任务中，就可以使用「选择排序」（《算法 4》相关章节课后练习题）。
依然是建议大家不要对算法带有个人色彩，在面试回答问题的时候和看待一个人和事物的时候，可以参考的回答模式是「具体问题具体分析，在什么什么情况下，用什么什么算法」。
（本节完）
