47.选择排序

编程语言 > CPP > CPP基础 > CPP基础语法知识排序编程语言 CPP CPP基础 CPP基础语法知识

发布时间 : 2025-01-25 12:14

字数:1.7k 阅读 :

评论:

47.排序-选择排序

47.排序-选择排序

47.1 知识点

选择排序基本原理

选择排序的基本步骤如下：

新建中间商
依次比较
找出极值（最大或最小）
放入目标位置
比较n轮

代码实现

int arr[] = { 8,7,1,5,4,2,6,3,9 };

// 先写一轮应该怎么排序
// 第一部：新建中间商来记录索引
int index = 0;

// 第二步：依次比较
// 每次一轮比较，从索引1开始，因为默认用于记录索引的中间商是0
// 那么没有必要和自己进行比较
for (int n = 1; n < sizeof(arr) / sizeof(int); n++)
{
    // 第三步：比较找出极值
    if (arr[index] < arr[n])
        index = n; // 记录更大值的索引值（选择最大的数的索引）
}

// 第四步：选择结束后，再放入目标位置
// 数组长度 - 1 - 轮数就是我们的目标位置
// 我们在交换之前应该判断，是否是自己换自己
if (index != sizeof(arr) / sizeof(int) - 1 - 轮数)
{
    int temp = arr[index];
    arr[index] = arr[sizeof(arr) / sizeof(int) - 1 - 轮数];
    arr[sizeof(arr) / sizeof(int) - 1 - 轮数] = temp;
}

// 第五步：比较m轮
for (int m = 0; m < sizeof(arr) / sizeof(int); m++)
{
    // 先写一轮应该怎么排序
    // 第一部：新建中间商来记录索引
    int index = 0;

    // 第二步：依次比较
    // 每次一轮比较，从索引1开始，因为默认用于记录索引的中间商是0
    // 那么没有必要和自己进行比较
    for (int n = 1; n < sizeof(arr) / sizeof(int) - m; n++)
    {
        // 第三步：比较找出极值
        if (arr[index] < arr[n])
            index = n; // 记录更大值的索引值（选择最大的数的索引）
    }

    // 第四步：选择结束后，再放入目标位置
    // 数组长度 - 1 - 轮数就是我们的目标位置
    // 我们在交换之前应该判断，是否是自己换自己
    if (index != sizeof(arr) / sizeof(int) - 1 - m)
    {
        int temp = arr[index];
        arr[index] = arr[sizeof(arr) / sizeof(int) - 1 - m];
        arr[sizeof(arr) / sizeof(int) - 1 - m] = temp;
    }
}

for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
{
    cout << arr[i] << " ";
}
cout << endl;

总结

选择排序的基本概念包括：

新建中间商
依次比较
找出（选择）极值
放入目标位置
比较n轮

选择排序的套路写法如下：

使用两层循环
外层表示轮数 - 初始索引
内层寻找极值并记录
内层循环结束后再进行交换

47.2 知识点代码

Lesson47_排序_选择排序.cpp

#include <iostream>
using namespace std;
int main()
{
    std::cout << "选择排序\n";

    #pragma region 知识点一 选择排序基本原理

    // 8 7 1 5 4 2 6 3 9
    // 新建中间商
    // 依次比较
    // 找出极值（最大或最小）
    // 放入目标位置
    // 比较n轮

    #pragma endregion

    #pragma region 知识点二 代码实现

    int arr[] = { 8,7,1,5,4,2,6,3,9 };

    ////先写一轮应该怎么排序
    ////第一步：新建中间商 来记录索引
    //int index = 0;
    ////第二步：依次比较
    ////每次一轮比较 从索引1开始 因为默认用于记录索引的中间商是0
    ////那么没有必要和自己进行比较
    //for (int n = 1; n < sizeof(arr)/sizeof(int); n++)
    //{
    //    //第三步：比较找出极值
    //    if (arr[index] < arr[n])
    //        index = n;//记录更大值的索引值（选择最大的数的索引）
    //}
    ////第四步：选择结束后 再放入目标位置
    ////数组长度 - 1 - 轮数 就是我们的目标位置
    ////我们在交换之前应该判断 是不是自己换自己
    //if (index != sizeof(arr) / sizeof(int) - 1 - 轮数)
    //{
    //    int temp = arr[index];
    //    arr[index] = arr[sizeof(arr) / sizeof(int) - 1 - 轮数];
    //    arr[sizeof(arr) / sizeof(int) - 1 - 轮数] = temp;
    //}

    //第五步：比较m轮
    for (int m = 0; m < sizeof(arr) / sizeof(int); m++)
    {
        //先写一轮应该怎么排序
        //第一步：新建中间商 来记录索引
        int index = 0;
        //第二步：依次比较
        //每次一轮比较 从索引1开始 因为默认用于记录索引的中间商是0
        //那么没有必要和自己进行比较
        for (int n = 1; n < sizeof(arr) / sizeof(int) - m; n++)
        {
            //第三步：比较找出极值
            if (arr[index] < arr[n])
                index = n;//记录更大值的索引值（选择最大的数的索引）
        }
        //第四步：选择结束后 再放入目标位置
        //数组长度 - 1 - 轮数 就是我们的目标位置
        //我们在交换之前应该判断 是不是自己换自己
        if (index != sizeof(arr) / sizeof(int) - 1 - m)
        {
            int temp = arr[index];
            arr[index] = arr[sizeof(arr) / sizeof(int) - 1 - m];
            arr[sizeof(arr) / sizeof(int) - 1 - m] = temp;
        }
    }

    for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;

    #pragma endregion

}

#pragma region 总结

//基本概念
// 新建中间商
// 依次比较
// 找出(选择)极值
// 放入目标位置
// 比较n轮

//套路写法
//两层循环
//外层轮数 - 初始索引
//内层寻找 - 记录极值
//内层循环结束后再交换

#pragma endregion

47.3 练习题

写一个函数，实现一个数组的排序。可以根据参数决定是升序还是降序，利用函数指针参数实现

bool maxSort(int a, int b)
{
    return a < b;
}

bool minSort(int a, int b)
{
    return a > b;
}

void sort(int array[], int size, bool (*func)(int, int))
{
    //选择排序

    //轮数
    for (int m = 0; m < size; m++)
    {
        //每一轮
        int index = 0;

        for (int n = 1; n < size - m; n++)
        {
            if (func(array[index], array[n]))
                index = n;
        }

        if (index != size - 1 - m)
        {
            int temp = array[index];
            array[index] = array[size - 1 - m];
            array[size - 1 - m] = temp;
        }
    }
}

int arr[] = { 4, 2, 78, 123, 6723, 332, 11, 235345, 234 };
sort(arr, 9, minSort);

for (int i = 0; i < 9; i++)
{
    cout << arr[i] << " ";
}

47.4 练习题代码

Lesson47_练习题.cpp

#include <iostream>
using namespace std;

void sort(int array[], int size, bool (*func)(int, int));
bool maxSort(int a, int b);
bool minSort(int a, int b);

int main()
{
    std::cout << "选择排序 练习题\n";

    #pragma region 练习题

    /*写一个函数，实现一个数组的排序。可以根据参数决定是升序还是降序
    利用函数指针参数实现*/

    int arr[] = { 4,2,78,123,6723,332,11,235345,234 };
    sort(arr, 9, minSort);

    for (int i = 0; i < 9; i++)
    {
        cout << arr[i] << " ";
    }

    #pragma endregion
}

bool maxSort(int a, int b)
{
    return a < b;
}

bool minSort(int a, int b)
{
    return a > b;
}

void sort(int array[], int size, bool (*func)(int, int))
{
    //选择排序
    
    //轮数
    for (int m = 0; m < size; m++)
    {
        //每一轮
        int index = 0;
        
        for (int n = 1; n < size - m; n++)
        {
            if (func(array[index], array[n]))
                index = n;
        }

        if (index != size - 1 - m)
        {
            int temp = array[index];
            array[index] = array[size - 1 - m];
            array[size - 1 - m] = temp;
        }
    }
    
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com