Sort|选择排序(Selection Sort)

选择排序 (Selection Sort)

简单选择排序是通过不断选择剩余元素中的最小值，并将其放在已排序部分的末尾。

实现步骤

1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置.
2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3. 以此类推，直到所有元素均排序完毕。

时间复杂度是O(n^2)，其中n是数组的长度，优势在于交换次数相对较少，且不受输入数据分布的影响(相对稳定)。

代码实现

template <typename T>
void selectionSort(T arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int minIndex = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        swap(arr[minIndex], arr[i]);
    }
}