算法基础：排序算法：选择排序

阳光穿透心脏的1/2处 2022-12-18 06:55 188阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center]  
选择排序是除冒泡排序之外特别容易被理解的排序算法了，这篇文章介绍一下选择排序的主要要点和实现。

### 目录 ###

*  算法思路
 *  算法要点
 *  模拟实现
 *  结果验证

--------------------

# 算法思路 #

>  *  选择排序和冒泡排序非常相像，都是使用比较和交换作为排序的重要手段，每次外层循环得到一个未排序的最小值，将序列分为已排序和未排序两种。但区别也非常清晰，冒泡排序的交换在内层循环进行，选择排序的交换在外层进行，内层循环只需要获取当次循环最小元素的下标。

--------------------

# 算法要点 #

选择排序的主要要点如下所示(N个元素，数组元素从0开始计数)：

*  外层循环：0 <= i < N - 1 (N-1次循环) 递加方式循环即可
 *  最小值标志：在外层循环开始设定为当前下标，内层循环中确认当前最小元素下标，当前内层循环结束后在外层循环中判断是否需要进行交换，定义此变量的好处在于不必在内层循环中进行交换。
 *  内层循环：将内层循环中的元素（包括当前元素）逐个与当前外层元素比较，以获得此次循环中的最小元素的下标
 *  比较：比较对象为外层循环的当前元素和内层循环的所有元素
 *  交换：在外层循环中直接进行当前元素和进行最小元素的交换

# 模拟实现 #

void select_sort(int* arr, int num) { 
        for (int i=0; i<num-1; i++) { 
            int min_index = i;
            for (int j=i; j<num; j++) { 
                if (arr[j] < arr[min_index]) min_index = j;
            }
            int tmp = arr[i]; arr[i]=arr[min_index]; arr[min_index]=tmp;
        }
    }

--------------------

# 结果验证 #

加上打印和调用的示例代码，可以使用如下方式进行验证

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    void select_sort(int* arr, int num) { 
        for (int i=0; i<num-1; i++) { 
            int min_index = i;
            for (int j=i; j<num; j++) { 
                if (arr[j] < arr[min_index]) min_index = j;
            }
            int tmp = arr[i]; arr[i]=arr[min_index]; arr[min_index]=tmp;
        }
    }
    
    void print_array(int* arr, int num) { 
        for (int i=0; i<num; i++) printf("%d ",arr[i]);
        printf("\n");
    }
    
    int main() { 
        int n = 0;
        while (scanf("%d",&n) != EOF) { 
            int* array = (int *)malloc(sizeof(int)*n);
            memset(array,0,sizeof(int)*n);
            for (int i=0; i<n; i++) { 
                scanf("%d",&array[i]);
            }
            select_sort(array,n);
            print_array(array,n);
            free(array); array= NULL;
        }
    }

执行结果示例

9
    9 8 7 6 5 4 3 2 1
    1 2 3 4 5 6 7 8 9

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221122/760f74073d134351b6ed934850e9e1fe.png