选择排序算法介绍

短命女 2022-06-01 07:23 114阅读 0赞

本文介绍选择排序（Selection sorts）算法的相关知识，并给出选择排序算法的示例代码。

说明：本文中的示例代码是使用 C++ 编程语言编写的。

# 1 算法介绍 #

在选择排序算法中，数字列表可分为两个子列表：**已排序的**和**未排序的**，它们通过假想的一堵墙分隔开。

在排序过程中，**找出（选择）**未排序子列表中的最小（或最大）元素，并把它和未排序列表中的第一个元素进行**交换**，再将假想的这堵墙（根据实际情况朝着对应方向）移动一个元素位置，这样每次排序后，已排序子列表中的元素将增加一个，同时未排序子列表中的元素将减少一个，每次把一个元素从未排序子列表移动到已排序子列表就完成了**一轮排序**。一个含有 n 个元素的数字列表需要 n - 1 轮排序来完成数据的重新排列。

根据上述内容，可总结选择排序算法的一般解题步骤如下：

1.  将假想墙放置在数字列表**最左侧**，墙的左侧为已排序子列表，右侧为未排序子列表；
2.  **找出（选择）**未排序子列表中的最小（或最大）元素；
3.  把选择的元素与未排序列表中第一个元素进行**交换**；
4.  将假想墙**向右移动**一个位置；
5.  反复执行 2 至 4 步操作，直至整个数字列表排序完成（需要 n - 1 轮）。

# 2 示例及分析 #

选择排序算法的示例代码如下：

#include <stdio.h>
    #include <stdlib.h>
    
    int main()
    {
        /* 选择排序函数声明 */ 
        int sort(int array[], int n);
        
        int num[5] = {0};
        int i = 0;
        
        /* 接收用户输入的5个整型数 */
        printf("please input 5 integer numbers: \n");
        for (i = 0; i < 5; i++)
        {
            scanf("%d", &num[i]);
        }
        
        /* 使用选择排序对数组num从小到大进行排序 */
        i = sort(num, 5);
        
        /* 打印排序后的数字顺序 */
        printf("the sorted numbers: \n");
        for (i = 0; i < 5; i++)
        {
            printf("%d ", num[i]);
        }
        
        printf("\n");
        
        return 0;
    }
    
    /* 
    *  选择排序法的函数定义
    *  数组array存放待排序数字
    *  n表示数组array大小
    */
    int sort(int array[], int n)
    {
        int i;
        int j;
        int tmp;
        
        /* n个数字进行排序，共需要进行n-1轮比较 */
        for (i = 0; i < n - 1; i++)
        {
            /* 每次循环选择未排序列表中的最小值，与array[i]交换 */ 
            for (j = i + 1; j < n; j++)
            {
                if (array[i] > array[j])
                {
                    tmp = array[i];
                    array[i] = array[j];
                    array[j] = tmp;
                }
            }
        }
        
        return 0;
    }

上述代码的运行结果如下：

please input 5 integer numbers:
    -11 92 -22 0 100
    the sorted numbers:
    -22 -11 0 92 100

说明：

*  在外层循环中，为变量 i 赋初始值“**0**”，可以更好地对应假想墙的初始位置（**数字列表最左侧**）。同时，通过 i 的**自增**操作，使假想墙的位置**从左向右**移动。
 *  从上述代码可以看出，本文第 1 章“选择排序算法的解题步骤”中的第 2 步和第 3 步，在代码实现时可以合并在一起，而不需要（也没必要）把对应步骤的代码单独实现；
 *  由于上述选择排序函数形参使用的是数组名，在调用该函数时，**是把实参数组的首元素地址传递给形参数组，这样两个数组就共占同一段内存单元了，**所以被调函数中形参数组的改变也导致了实参数组随之改变。

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

补充：

本例是通过**数组名作为函数实参**的方法，实现的选择排序算法。用数组名作函数实参时，不是把数组元素的值传递给形参，而是**把实参数组的首元素地址传递给形参数组，这样两个数组就共占同一段内存单元了**，也就是说，形参数组中各元素的值如果发生变化，也会使实参数组元素的值同时发生变化（这一点与变量作为函数参数是不相同的）。在程序设计时可以有意识地利用这一特点**改变实参数组元素的值**（如排序）。