个性化阅读
专注于IT技术分析

经典排序算法之选择排序(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;
}
赞(0)
未经允许不得转载:srcmini » 经典排序算法之选择排序(Selection Sort)实现原理和代码实现及其应用详解

评论 抢沙发

评论前必须登录!