经典排序算法之选择排序（Selection Sort）实现原理和代码实现及其应用详解 _数据结构和算法

选择排序算法简单的实现为：通过重复从待排序数组中找出最小元素（升序），将该最小元素放在首位置。给定一个待排序的数组，该排序算法需要操作两个子数组：已排序数组和未排序数组，实际操作中这两个数组可以在同一个数组上实现。
选择排序的每次遍历都从一个未排序的数组中找出最小元素（升序），然后将该最小元素放在已排序的数组中，即可完成排序，下面是选择排序算法的一个操作实例：

文章图片
由上面可以看出，选择排序的元素互换次数不超过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]前面，下面是稳定和不稳定的排序算法的例子：

文章图片
也就是说我们首先要确定有相同的元素，排序算法中的任何比较一般来说都是不稳定的，但是可以通过简单的修改改为稳定的算法，例如可以改变关键字比较操作修改为稳定算法。
【经典排序算法之选择排序（Selection Sort）实现原理和代码实现及其应用详解】上面默认的不稳定的选择排序算法，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 = http://www.srcmini.com/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; }