经典排序算法之选择排序（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]前面，下面是稳定和不稳定的排序算法的例子：

也就是说我们首先要确定有相同的元素，排序算法中的任何比较一般来说都是不稳定的，但是可以通过简单的修改改为稳定的算法，例如可以改变关键字比较操作修改为稳定算法。

上面默认的不稳定的选择排序算法，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;
}