选择排序算法简单的实现为：通过重复从待排序数组中找出最小元素（升序），将该最小元素放在首位置。给定一个待排序的数组，该排序算法需要操作两个子数组：已排序数组和未排序数组，实际操作中这两个数组可以在同一个数组上实现。
选择排序的每次遍历都从一个未排序的数组中找出最小元素（升序），然后将该最小元素放在已排序的数组中，即可完成排序，下面是选择排序算法的一个操作实例：
由上面可以看出，选择排序的元素互换次数不超过O(N)，选择排序的辅助空间为O(1)，时间复杂度为O(N^2)。
一、选择排序算法的默认实现
选择排序算法的默认实现是不稳定的，但是可以实现稳定，稳定的选择排序在后面有实现，这里先实现默认版本的选择排序算法，先看一下下图完整的选择排序算法执行流程图：
选择排序的实现源码和调用源码如下：
#define N 7
/**
* 选择排序（升序），时间复杂度为O(N^2)
* 处理两个数组A和B，A数组是待排序的数组，B数组是已排序的数组（实际处理AB都是在同一数组中）
* 从A数组中找出第一个最小元素放在B的第0个中；
* 从A数组中找出第二个最小元素放在B的第1个中；
* 依此类推即可完成排序
* */
int *selection_sort(int array[], int len){
for (int i = 0; i < len - 1; ++i) {
int min_index = i;
for (int j = i + 1; j < len; ++j) {
if(array[j] < array[min_index])
min_index = j;
}
int temp = array[min_index];
array[min_index] = array[i];
array[i] = temp;
}
return array;
}
void print_array(int array[], int len){
for (int i = 0; i < len; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
int main() {
int array[N] = {7, 9, 16, 25, 34, 72, 80};
selection_sort(array, N);
print_array(array, N);
return 0;
}
二、稳定的选择排序算法
一个排序算法的稳定性是说：在待排序的数组中，存在具有相同关键字的记录，经过排序后，这些记录的相对次序保持不变，则该排序算法为稳定排序算法，否则该算法为不稳定。即array[i]==array[j]，排序前array[i]在array[j]前面，排序后array[i]也在array[j]前面，下面是稳定和不稳定的排序算法的例子：
也就是说我们首先要确定有相同的元素，排序算法中的任何比较一般来说都是不稳定的，但是可以通过简单的修改改为稳定的算法，例如可以改变关键字比较操作修改为稳定算法。
上面默认的不稳定的选择排序算法，7A排序后在7B后面，造成了不稳定，这是因为7A和1交换了，现在我们改变关键字比较策略，使用插入操作实现，即将最小元素插入到已排序的数组中，原数组则是删除取出的最小元素（当然还是在同一个数组中操作），下面是稳定的排序算法的实例解释：
下面是稳定的排序算法实现代码和调用实例：
#define N 7
/**
* 稳定选择排序，时间复杂度为O(N^2)
* 和默认选择排序实现不同的是，稳定选择排序使用插入操作来实现稳定
* */
int *stable_selection_sort(int array[], int len){
for (int i = 0; i < len - 1; ++i) {
int min_index = i;
for (int j = 0; j < len; ++j) {
if(array[j] < array[min_index])
min_index = j;
}
int value = array[min_index];
while(i < min_index){
array[min_index] = array[min_index - 1];
min_index--;
}
array[i] = value;
}
return array;
}
void print_array(int array[], int len){
for (int i = 0; i < len; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
int main() {
int array[N] = {7, 9, 16, 25, 34, 16, 80};
stable_selection_sort(array, N);
print_array(array, N);
return 0;
}
稳定选择排序算法的复杂度为O(N^2)，该while循环为删除操作，该操作的复杂度为O(N)。
三、选择排序算法的应用
下面使用选择排序算法排序一个字符串序列，字符串的比较使函数strcmp()，字符串的交换使用函数strcpy()，注意strcmp比较函数若第一个字符串大于第二个则返回正数，小于返回负数，等于返回0，下面是完整的字符串数组选择排序算法以及对应的调用代码：
#define N 7
#define MAX_STR 30
// 使用选择排序对字符串序列进行排序
void str_selection_sort(char array[][MAX_STR], int len){
char min_str[MAX_STR];
for (int i = 0; i < len - 1; ++i) {
int min = i;
strcpy(min_str, array[min]);
for (int j = i + 1; j < len; ++j) {
if(strcmp(min_str, array[j]) > 0)
min = j;
}
if(min != i){
char temp[MAX_STR];
strcpy(temp, array[min]);
strcpy(array[i], temp);
strcpy(array[min], min_str);
}
}
}
int main() {
char array[N][MAX_STR] = {"Java", "Python", "JavaScript", "TypeScript", "C++", "C", "Golang"};
str_selection_sort(array, N);
for (int i = 0; i < N; ++i) {
printf("%s ", array[i]);
}
printf("\n");
return 0;
}
来源：
https://www.srcmini02.com/1358.html
