大家好，我是老三，一个刷不动算法的程序员。排序算法相关题目尽管在力扣中不是很多，但是面试中动不动要手撕一下。接下来，我们看一下十大基本排序，
排序基础 排序算法的稳定性什么是排序算法的稳定性呢？
当待排序记录的关键字均不相同时，排序结果是惟一的，否则排序结果不惟一[1]。
在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的：
若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。
排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，那么这种排序算法就是不稳定的。
排序的分类按在排序过程中是否涉及数据的内、外存交换来分类，排序大致分为两类：内部排序和外部排序。
按照是否通过比较来决定元素间的相对次序，排序可以分为比较类排序和非比较类排序。
柿子挑软的捏，先从最简单的开始。
冒泡排序有着好听的名字，也有着最好理解的思路。
冒泡排序的基本思想是，从一端到另一端遍历，两两比较相邻元素的大小，如果是反序则交换。
动图如下（来源参考[4]）：
先简单实现以下，很简单，两层循环，相邻元素比较：
public void sort(int[] nums) { for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { //升序 if (nums[i] > nums[j]) { //交换 int temp = nums[i]; nums[j] = nums[i]; nums[i] = temp; } } } } 冒泡排序优化上面的代码实现还存在一个问题，什么问题呢？
哪怕数组有序，它还是会接着遍历。
所以可以用一个标志位来标志数组是否有序，假如有序，就跳出遍历。
public void sort(int[] nums) { //标志位 boolean flag = true; for (int i = 0; i < nums.length; i++) { for (int j = 0; j < nums.length - i - 1; j++) { //升序 if (nums[j] > nums[j + 1]) { //交换 int temp = nums[j]; nums[j] = nums[j + 1]; nums[j + 1] = temp; } } //如果是有序的,结束循环 if (flag) { break; } } } 冒泡排序性能分析大小相同的元素没有交换位置，所以冒泡排序是稳定的。
算法名称 最好时间复杂度 最坏时间复杂度 平均时间复杂度 空间复杂度 是否稳定冒泡排序 O(n) O(n²) O(n²) O(1) 稳定
选择排序 选择排序原理
选择排序为什么叫选择排序？原理是怎么样的呢？
它的思路：首先在未排序的序列中找到最小或者最大的元素，放到排序序列的起始位置，然后再从未排序的序列中继继续寻找最小或者最大元素，然后放到已经排序序列的末尾。以此类推，直到所有元素排序完毕。
动图如下(来源参考[4])：
来看一个例子，用选择排序的方式排序数组 [2,5,4,1,3]。
第一趟，找到数组中最小的元素1，将它和数组的第一个元素交换位置。
第二趟，在未排序的元素中找到最小的元素2，和数组的第二个元素交换位置。
第三趟，在未排序的元素中找到最小的元素3，和数组的第三个元素交换位置。
第四趟，在未排序的元素中找到最小的元素4，和数组的第四个元素交换位置。
那么到这，我们的数组就是有序的了。
