选择排序算法实现&讲解

蒟蒻

【选择排序算法设计】

选择排序算法的原理是，寻找数组中最小的数字，和区域内的第一个数字互换位置，
每进行一次排序，区域就缩小一位
例如在arr和arr[size]中寻找最小的数，并和i对换位置
下一次会在arr[i+1]和arr[size]中寻找最小的数，和i+1兑换位置，以此类推

首先我们需要实现一个GetMinPos函数

[C++] 纯文本查看 复制代码

int GetMinPos(int arr[], int begin, int end)
{
    // 设最小的数字位于begin处
    int minPos = begin;

    for (int i = begin + 1;i <= end;i++) {
        if (arr[i] < arr[minPos]) {
            // 如果i处小于minPos处，则目前minPos为i
            minPos = i;
        }
    }
    return minPos;
}

假设minPos位于begin处，如果arr < arr[minPos]，则把minPos设为i
遍历完成后可获取最小的数的position
为了将数字交换位置，还需要一个swap函数，有许多解法，这里用了最简单的

[C++] 纯文本查看 复制代码

void Swap(int &a, int &b)
{
    // 典型的临时变量交换法
    int tmp;
    tmp = a;
    a = b;
    b = tmp;
}

最后就是SelectionSort函数，个人觉得很好理解

[C++] 纯文本查看 复制代码

void SelectionSort(int arr[], int size)
{
    for (int next = 0;next < size - 1;next++) {
        // 从next处开始的最小值的位置
        int minPos = GetMinPos(arr, next, size - 1);
        // 与next所在的位置交换
        Swap(arr[next], arr[minPos]);
    }
}

附：完整源代码

[C++] 纯文本查看 复制代码

#include <stdio.h>

int GetMinPos(int arr[], int begin, int end)
{
    // 设最小的数字位于begin处
    int minPos = begin;

    for (int i = begin + 1;i <= end;i++) {
        if (arr[i] < arr[minPos]) {
            // 如果i处小于minPos处，则目前minPos为i
            minPos = i;
        }
    }
    return minPos;
}

void Swap(int &a, int &b)
{
    // 典型的临时变量交换法
    int tmp;
    tmp = a;
    a = b;
    b = tmp;
}

void SelectionSort(int arr[], int size)
{
    for (int next = 0;next < size - 1;next++) {
        // 从next处开始的最小值的位置
        int minPos = GetMinPos(arr, next, size - 1);
        // 与next所在的位置交换
        Swap(arr[next], arr[minPos]);
    }
}

void PrintElement(int arr[], int size)
{
    for (int i = 0;i < size;i++) {
        printf("%d ", arr[i]);
    }
}

int main()
{
    int arr[] = {5, 3, 8, 19, 0, 2};
    printf("Before sorting: ");
    PrintElement(arr, 6);
    SelectionSort(arr, 6); // 6个元素
    printf("\nAfter sorting: ");
    PrintElement(arr, 6);
}

faryou

sort快排了解一下

蒟蒻

faryou 发表于 2024-3-31 17:03
sort快排了解一下

got it，在学

faryou

蒟蒻 发表于 2024-3-31 19:32
got it，在学

另外，C++本身就有swap函数