选择排序 Selection Sort

原理

选择排序（Selection Sort）是一种简单且直观的排序算法。其基本思想是：每一次从未排序部分中选出最小（或最大）的元素，将其放到已排序部分的末尾。

其具体步骤如下：

1. 寻找最小（或最大）元素：在未排序部分中找到最小（或最大）的元素。
2. 交换位置：将这个元素与未排序部分的第一个元素交换位置。
3. 重复上述步骤：对剩余未排序部分继续执行，直到所有元素都排序完成。

示例

有一组无序数组：

6	2	4	1	9	0	3

选择其中的最小值0与第一个元素6替换。

此时数组为：

	2	4	1	9		3

将0作为有序数组，选择剩余元素中的最小值1与第二个元素6替换。

此时数组为：

		4		9	6	3

将0 1作为有序数组，选择剩余元素中的最小值2与第三个元素4替换。

此时数组为：

				9	6	3

将0 1 2作为有序数组，选择剩余元素中的最小值3与第四个元素9替换。

此时数组为：

				9	6

将0 1 2 3作为有序数组，选择剩余元素中的最小值4与第五个元素9替换。

此时数组为：

						6

将0 1 2 3 4作为有序数组，选择剩余元素中的最小值6与第六个元素9替换。

此时数组为：

剩余一个最大值，排序完成。

实现

C++

#include <iostream>
#include <vector>
using namespace std;

std::vector<int> SelectionSort(std::vector<int> besortedArray);
std::vector<int> myArray = { 6, 2, 4, 1, 9, 0, 3, 10, 15 };

int main()
{
    std::vector<int> testArray = SelectionSort(myArray);
    //输出：0 1 2 3 4 6 9 10 15
    for (int i = 0; i < testArray.size(); i++) {
        cout << testArray[i] << " ";
    }
    return 0;
}

//选择排序
std::vector<int> SelectionSort(std::vector<int> besortedArray)
{
    int length = besortedArray.size();
    for (int i = 0; i < length - 1; i++)
    {
        int index = i;
        for (int j = i+1; j < length; j++)
        {
            if (besortedArray[j] < besortedArray[index]) {
                index = j;
            }
        }
        int t = besortedArray[i];
        besortedArray[i] = besortedArray[index];
        besortedArray[index] = t;
    }
    return besortedArray;
}

可视化

数组长度

动画间隔

数组：

[]