选择排序

[Ir1d]

https://oi-wiki.org/basic/selection-sort/

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛

[asukaminato0721]

C++ 里面有 std::swap 函数，最后一行直接写 swap(a[i], a[ith]); 就行

[ZG-jian]

里面的for循环迭代条件去掉等于，数组下标越界异常

[asukaminato0721]

C++ 里面有 std::swap 函数，最后一行直接写 swap(a[i], a[ith]); 就行

假如支持 C++17, 可以写 std::tie(a,b) = std::make_tuple(b,a+b); ，用法类似 python 的 a, b = b, a + b

[dst111dst]

只是因为swap操作就说明这是不稳定的吗？为什么？

[for-something]

比如：2 2 1，第一个2会和1交换，所以不稳定

[AsterZC19]

@dst111dst
只是因为swap操作就说明这是不稳定的吗？为什么？

因为可能导致相同数字之间的相对顺序发生变化，所以是不稳定的排序，而冒泡排序不会导致

[tsaihaojiang]

冒泡排序不也會用swap嗎？

[jh233wzb]

python版本的代码那里第一个for,应该是for i in range(n);第二个for，应该是for j in range(i+1,n)才对吧？或者说代码第0位是保留的，从1开始索引？

[JohanRain]

@jh233wzb
python版本的代码那里第一个for,应该是for i in range(n);第二个for，应该是for j in range(i+1,n)才对吧？或者说代码第0位是保留的，从1开始索引？

为了区别是第i个大小的元素吧 是从1开始索引的

[wz-wong]

python 版本 代码有问题, 执行出错

可尝试我这个, 可正常运行

# 选择排序,先确定位置
a = [7,9,3,5,8,6,10]
def selection_sort(a):
    n = len(a)
    for i in range(0,n-1):
        for j in range(i,n):
            if a[i]>a[j]:
                a[i],a[j]=a[j],a[i]            
    return a
selection_sort(a)  

[wz-wong]

又看了些其他的文章, 发现上面我写的是冒泡排序
选择排序应该这样写
非常相似,不过选择排序是借用了一个临时变量min 保存最小值的索引
冒泡排序 | 选择排序

• 对比的次数相同
• 操作数据 选择排序 更优
  对比发现, 冒泡要操作35次,选择仅需操作6次

a = [7,9,3,5,8,6,10]
def selection_sort(a):
    n = len(a)
    for i in range(n-1):
        min = i
        for j in range(i+1,n):
            if a[min]>a[j]:
                min = j
        a[i],a[min]=a[min],a[i]
    return a
selection_sort(a) 

[usaging]

C++错误：runtime error！
给出正确代码
void selectsort1(int arr[], int len)
{
if (len < 2) return; // 数组小于2个元素不需要排序。

int iminpos; // 每趟循环选出的最小值的位置（数组的下标）。

// 44,3,38,5,47,15,36,26,27,2,46,4,19,50,48  
for (int ii = 0; ii < len - 1; ii++)  // 一共进行len-1趟比较。
{
    iminpos = ii;

    for (int jj = ii + 1; jj < len; jj++)  // 每趟只需要比较ii+1......len-1之间的元素，ii之前的元素是已经排序好的。
    {
        // 找出值更小的元素，记下它的位置。
        if (arr[jj] < arr[iminpos])  iminpos = jj;
    }

    // 如果本趟循环的最小的元素不是起始位置的元素，则交换它们的位置。
    if (iminpos != ii) swap(arr[ii], arr[iminpos]);
}

}

[error7chia]

Python代碼錯到離譜了 應該是：

def selection_sort(a, n):
    for i in range(n-1):
        ith = i
        for j in range(i + 1, n):
            if a[j] < a[ith]:
                ith = j
        a[i], a[ith] = a[ith], a[i]

[zhangjialin996]

双向选择排序：每次选出一个最大值和一个最小值
java版

class Solution {
    // 选择排序优化：双向选择排序
    public int[] sortArray(int[] nums) {
        for(int i = 0; i < nums.length / 2; i++ ){
            int minIndex = i, maxIndex = i;
            for(int j = i; j < nums.length - i; j++){
                if(nums[j] > nums[maxIndex]) maxIndex = j;
                if(nums[j] < nums[minIndex]) minIndex = j;
            }
            // 最小值移动到left
            int temp = nums[i];
            nums[i] = nums[minIndex];
            nums[minIndex] = temp;
            // 可能影响maxIndex
            if(maxIndex == i) maxIndex = minIndex;
            temp = nums[nums.length - i - 1];
            nums[nums.length - i - 1] = nums[maxIndex];
            nums[maxIndex] = temp;
        }
        return nums;
    }
}

注意点：将最小值移动到左侧后，不能立即将最大值移动到右侧，因为当最大值在左侧待交换位置时，交换完成后，最大值的索引也应该更新。
比如：55551，最大值是第一个5[索引0]，最小值是1[索引4]，最小值交换完成后【可以看出选择排序不具有稳定性】，最大值索引显然仍然是0，但是这个位置的值是1了，所以错误；应当将最大值索引更新为4

[Ethkuil]

善用 STL，可以像伪代码一样清晰展现选择排序的原理，只要2行：

// begin, end: ForwardIt
for (auto it = begin; it != end; ++it) {
  std::iter_swap(it, std::min_element(it, end));
}

[heathera-Jiang]

外层循环从1开始遍历是因为舍弃了第一项，全程都从数组第二项开始吗。？

[ZhaodongLea]

外层循环从1开始是因为写错了。。 从左到右迭代没道理舍弃第一项，不过可以舍弃最后一项，因为前面n-1项已是有序的。