选择排序

概念

选择排序（Selection Sort）是一种简单直观的排序算法，它的基本思想是在待排序的数组中找到最小（或最大）的元素，将其放在已排序数组的末尾，然后继续在未排序的部分中找到最小（或最大）的元素，放在已排序数组的末尾，直到所有元素都排序完毕。

选择排序的具体步骤如下：

遍历整个数组，找到最小（或最大）的元素，记其下标为minIndex。
将找到的最小（或最大）元素与数组的第一个元素交换位置，将最小（或最大）元素放在已排序数组的末尾。
在剩余未排序的部分中，继续执行步骤1和步骤2，直到所有元素都排序完毕。

选择排序的特点是简单直观，实现容易，但是效率相对较低，其时间复杂度为O(n^2)，其中n是待排序数组的长度。选择排序是一种不稳定的排序算法，因为交换操作可能会破坏相同元素的相对位置关系。

优缺点

选择排序优点和缺点如下：

优点：

简单直观：选择排序是一种非常简单直观的排序算法，容易理解和实现，适用于初学者学习排序算法的入门。
原地排序：选择排序是一种原地排序算法，不需要额外的存储空间，只需要一个额外的变量用于交换元素。
稳定性：在实现过程中，如果对于相同元素的排序不做交换，那么选择排序是稳定的，即相同元素的相对位置不会改变。

缺点：

效率低：选择排序的时间复杂度为O(n^2)，其中n是待排序数组的长度。在大规模数据的情况下，效率较低，性能不如一些其他排序算法，如快速排序、归并排序等。
不稳定性：虽然选择排序可以实现稳定性，但是在实际的实现过程中，由于交换操作可能会破坏相同元素的相对位置关系，因此选择排序通常是不稳定的。

代码实现

func SelectionSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        minIndex := i // 假设当前索引的元素为最小值
        // 在剩余未排序的部分中找到最小元素的索引
        for j := i + 1; j < n; j++ {
            if arr[j] < arr[minIndex] {
                minIndex = j
            }
        }
        // 将找到的最小元素与当前位置元素交换位置
        arr[i], arr[minIndex] = arr[minIndex], arr[i]
    }
}

总结

选择排序：依次在未排序序列中选择最小的元素，并将该元素与首位元素交换位置。

复杂度：

平均时间复杂度：O(n²)
最坏时间复杂度：O(n²)
最优时间复杂度：O(n²)
空间复杂度：O(n)

参考：选择排序-维基百科

选择排序 ​

概念 ​

优缺点 ​

代码实现 ​

总结 ​

选择排序

概念

优缺点

代码实现

总结