选择排序——直接选择排序-Toy模板网

这篇具有很好参考价值的文章主要介绍了选择排序——直接选择排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1、简述

2、复杂度

3、稳定性

4、例子

直接选择排序：（以重复选择的思想为基础进行排序）

1、简述

顾名思义就是选出一个数，再去抉择放哪里去。

设记录R1，R2…，Rn，对i=1，2，…，n-1，重复下列工作：

(1)在Ri，…，Rn中选最小(或最大)关键字记录Rj；

(2)将Rj与第i个记录交换位置，即将选到的比i小的记录换到第i号位置上。

2、复杂度

时间复杂度： ≈O(n²)

空间复杂度：O(1)

3、稳定性：不稳定排序

在得到最小下标后进行位置交换可能会将相同的元素的原来序列更改。

4、例子

对下面序列进行排序：45, 38, 66, 90, 88, 10, 25, 45

从i=0开始，对比每个元素，记录最小值的下标，第一趟对比中可以得到最小下标为5，和i=0交换位置，也就是10和45换位置;

i=1，对比得到最小下标为5，即38和25交换位置；

以此类推……

排序图示：

选择排序——直接选择排序,算法,算法,数据结构,排序算法

C++代码：

#include <iostream>
using namespace std;
// 选择排序
int main() {
    int arr[8] = {45, 38, 66, 90, 88, 10, 25, 45};
    int arrCount = sizeof(arr) / sizeof(arr[0]);
    
    for (int i = 0; i < arrCount-1; i++) {
        // 从第一个开始，找出最小值的下标
        int minIndex = i, tmp = arr[i];
        
        for (int j = i + 1; j < arrCount; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;  // 找到最小下标，并记录
            }
        }
        // 交换下标位置
        arr[i] = arr[minIndex];
        arr[minIndex] = tmp;

        cout<<i+1<<"次排序后：";
        for (int i = 0;i < arrCount;i++) {
            cout << arr[i] << " ";
        }
        cout<<endl;
    }
    cout<<"最后结果：";
    for (int i = 0;i < arrCount;i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

输出结果：

1次排序后：10 38 66 90 88 45 25 45 
2次排序后：10 25 66 90 88 45 38 45 
3次排序后：10 25 38 90 88 45 66 45 
4次排序后：10 25 38 45 88 90 66 45 
5次排序后：10 25 38 45 45 90 66 88 
6次排序后：10 25 38 45 45 66 90 88 
7次排序后：10 25 38 45 45 66 88 90 
最后结果：10 25 38 45 45 66 88 90

快捷跳转：