这才是选择排序正确的打开方式！
The following article is from 景禹 Author 景禹
脚本之家
你与百万开发者在一起
本文经授权转自公众号 景禹（ID：LifeAtaraxia）
如若转载请联系原公众号
选择排序思想
选择排序（Selection Sort）的基本思想是不断地从数组当中未排序的部分选取关键字最小的记录，并将该记录作为已排序部分的最后一个记录（考虑升序排列的情况）。算法主要就是维护一个给定数组的两个子数组：
数组已排序的部分； 数组未排序的部分；
在选择排序的每一次迭代中，从数组中未排序的部分选择出最小元素（升序排列的情况），然后将其移入数组已排序的部分。
初始时，给定一个数组，且将该数组当中的所有元素都被划分为无序部分：
遍历数组 [0,7]，找到下标为 5 最小的关键字 13：
下标为 5 最小的关键字 13 与下标为 0 的关键字 49 进行交换，这样就得到了数组有序部分的第一个关键字 13，而无序部分相应的减少了一个关键：
之后的所有操作和之前一样，在无序部分找到最小的关键字，然后与无序部分的第一个关键字交换，有序部分加一，无序部分减一：
简而言之，选择排序就两步：
选择最小（或最大） 交换
实现代码
C 实现
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
void selectionSort(int arr[], int n)
{
int i, j, min_idx;
// i就相当于将数组划分为有序部分和无序部分的边界，不断地让这个边界后移
for (i = 0; i < n-1; i++)
{
//找到数组中无序部分的最小关键字
min_idx = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
// 将最小关键字与无序部分的第一给关键字交换
swap(&arr[min_idx], &arr[i]);
}
}
Java实现
class SelectionSort
{
void sort(int arr[])
{
int n = arr.length;
for (int i = 0; i < n-1; i++)
{
int min_idx = i;
for (int j = i+1; j < n; j++){
if (arr[j] < arr[min_idx])
min_idx = j;
}
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
}
Python实现
def SelectionSort(A):
for i in range(len(A)):
min_idx = i
for j in range(i+1, len(A)):
if A[min_idx] > A[j]:
min_idx = j
A[i], A[min_idx] = A[min_idx], A[i]
return A
复杂度分析
时间复杂度
上面的循环中的 if 语句最坏情况下一共计算了多少次？
当 i == 0 的时候，j 的取值范围是从 1 到 n -1，内循环的判断一种执行了 n - 1 次；
当 i == 1 的时候，j 的取值范围是从 2 到 n -1，内循环的判断一种执行了 n - 2 次；
以此类推......
当 i 取最大值 n - 2 时，j 的取值为 n -1，内循环的判断执行了1 次；
所以，整体内循环的判断语句执行次数就是：1 + 2 + 3 + ... + (n - 2) + (n - 1) 。
这种计算一个高斯公式搞定，则 if 执行了就是 次，时间复杂度为 量级。
空间复杂度
选择排序属于原地排序（In-place Sorting），因为选择排序没有使用任何额外的空间，仅使用了数组自身所占用的空间，所以空间复杂度就是 。你也可以认为原地排序算法就是空间复杂度为 的算法。
稳定性分析
关于排序算法的稳定性问题，景禹在之前的一篇文章 排序算法的稳定性 中有分享，这里我们就直接分析选择排序的稳定性问题。
我可以直接告诉你选择排序的默认实现方式是不稳定的，具体为神马，我们接着看一个例子：
给定上面一个数组，我们按照前面的实现方式进行排序。
第一步：在数组中找到最小的关键字 1 ，并与数组中的第一个元素（红色色块 4）交换位置：
第二步：在数组中无序部分 [5，3，2，4，4] 找到最小的关键字 2 与无序部分的第一个关键字 5 交换位置：
第三步：在数组中无序部分 [3，5，4，4] 中找到最小的关键字 3 和无序部分的第一个关键字 3 交换，和之前一样：
第四步：在数组中无序部分 [5，4，4] 中找到最小的关键字 4（注意是蓝色色块的4） 和 5 交换：
第五步：在数组中无序部分 [5，4] 中找到最小的关键字 4（注意是红色色块的4） 和 5 交换：
此时我们得到一个有序数组，但是与原始的数组相比，两个 4 的相对位置发生了变化。即，本来红色色块的 4 在蓝色色块的 4 的前面，而排序后蓝色的在红色的前面，这就是我们之前所说的不稳定（两个值相同的关键字排序前后的相对位置发生了变化）。也就是说目前的实现方式下的选择排序是不稳定的。
稳定的选择排序
不稳定的选择排序结果：
目标 -- 实现一个稳定的选择排序：
为了实现现在这一目标，我们分析一下原始的选择排序为什么不稳定？
答案就是交换操作造成了不稳定。选择排序的工作原理就是在未排序的部分找到关键字最小的元素，然后将该元素与未排序部分的第一个元素进行交换位置。也就是这个交换操作导致其不稳定，比如前面分析的时候，第一次交换就是的 4 得相对位置发生了变化。
因此可以考虑对这里的交换操作进行修改使得选择排序变得稳定。
要想每一次将最小元素放置在其位置而不进行交换，可以通过将每一次选择出的最小关键字前面的无序数组元素都向后移动一个位置，使选择排序稳定。简单来说，就是利用类似于插入排序的技术将最小的元素插入正确的位置。
第一步：找到最小元素是 1 ，此时 不再 是将红色色块 4 和最小元素 1 进行交换，而是将 1 插入到正确的位置，然后将 1 之前的每一个元素都向后移动一个位置：
第二步：找到数组无序部分的最小元素 2 ，将 2 之前的 [4，5，3] 的每一个元素向后移动一个位置：
第三步：找到数组无序部分的最小元素 3 ，将 3 之前的 [4，5] 的每一个元素向后移动一个位置：
第四步：找到数组无序部分的最小元素 4（红色色块） ，其前面没有无序元素，什么都不做；
第五步：找到数组无序部分的最小元素 4（蓝色色块） ，将其前面的元素 5 向后移动，我们得到了一个稳定的有序数组：
稳定的选择排序的实现
Java实现
class JingYuSorting
{
static void stableSelectionSort(int[] a, int n)
{
// 与默认的实现方式相同
for (int i = 0; i < n - 1; i++)
{
// a[i - 1] 之前的元素为数组的有序部分
// 从 arr[i] 到 arr[n - 1] 找到最小元素的下标保存到min中
int min = i;
for (int j = i + 1; j < n; j++)
if (a[min] > a[j])
min = j;
// 将最小的元素移动到当前的位置 i.
int key = a[min];
// 将从 i 到 min - 1 的元素都向后移动一个位置
while (min > i)
{
a[min] = a[min - 1];
min--;
}
// 将当前选择的最小元素放到正确的位置
a[i] = key;
}
}
}
复杂度分析
时间复杂度
时间复杂度为 ，整体依旧是两层 for 循环嵌套。但是稳定的选择排序需要移动元素，每一次选择出一个最小元素，就需要对其前面无序的元素向后移动，最坏的情况是，第一次移动 n-1 次，第二次移动 n - 2 次，......，第 n-1 次移动 1 次，总共移动 ，这并不会影响到整个实现的时间复杂度的量级。
空间复杂度
稳定的选择排序依旧没有使用任何额外的空间，所有操作都是在数组内进行的，所以空间复杂度为 .
实战演练
给定一个字符串数组，使用选择排序对数组进行排序。
输入: paper true soap floppy flower 输出: floppy, flower, paper, soap, true
我们前面所讲的所有例子都是用整数进行说明的，这里要使用选择排序对字符串数组进行排序，我们仅需要对原始的实现中整型的比较操作和拷贝操作转化为字符串的比较和拷贝操作。
java 中字符串的比较操作使用 compareTo() 函数即可；C++/C 的比较操作可以使用 strcmp() 函数进行比较，拷贝可以使用 strcpy() 函数进行拷贝。这里就给大家提供 Java 的参考代码。
题外话：面试中，好多面试官会考察函数 strcmp() 与 strcpy() 的底层实现，对这个点不太熟悉的小禹禹可以了解一下，觉得没时间，希望景禹解析的，评论区留下你的足迹。
// 使用选择排序对字符串数组进行排序
static void selectionSort(String arr[],int n)
{
// 将有序部分和无序部分的界限 i 不断向后移动
for(int i = 0; i < n - 1; i++)
{
// 在数组未排序部分找到最小的字符串
int min_index = i; //保存最小的字符串的下标
String minStr = arr[i]; //保存最小的字符串
for(int j = i + 1; j < n; j++)
{
if(arr[j].compareTo(minStr) < 0)
{
minStr = arr[j];
min_index = j;
}
}
// 将最小字符串与 位置为 i 的字符串进行交换
if(min_index != i)
{
String temp = arr[min_index];
arr[min_index] = arr[i];
arr[i] = temp;
}
}
}
网站推荐
给大家推荐一个可视化网站：https://visualgo.net/zh/sorting
我们以今日的选择排序给大家讲一下使用的方法。
输入网址后，进入如下界面：
但看着密密麻麻的英文，我们直接按 ESC 键。
紧接着选择 zh ，中文模式：
导航栏中分别为：冒泡排序、选择排序（SEL）、插入排序（INS）、归并排序（MER）、
快速排序（QUI）、随机快速排序（R-Q）、计数排序（COU）、基数排序（RAD）。
我们点击 SEL，即选择排序：
默认提供了一组输入数组，你也可以通过下图中几种方式自己生成：
我们输入我们的示例输入 [4,5,3,2,4,1] :
然后就是进行选择排序了，依次点击排序→执行：
紧接着你就可以看到下面的执行动画了：
就到这里了，记得一定要自己去探索一下奥~~
（更多精彩值得期待……）