2.选择排序

简介: 2.选择排序

【原理】

首先在未排序的数列中找到最小(or最大)元素,然后将其存放到数列的起始位置;接着,再从剩余未排序的元素中继续寻找最小(or最大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。


【复杂度和稳定性】

(1)选择排序时间复杂度

选择排序的时间复杂度是O(N2)。

假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N),需要遍历N-1。因此,选择排序的时间复杂度是O(N2)。


(2)选择排序稳定性

选择排序是稳定的算法,它满足稳定算法的定义。

算法稳定性 -- 假设在数列中存在a[i]=a[j],若在排序之前,a[i]在a[j]前面;并且排序之后,a[i]仍然在a[j]前面。则这个排序算法是稳定的!


【代码】

#include<iostream>
using namespace std;
 
template<class T>//模板的使用
void selection_sort(T Array[],const int size);
 
int main()
{
    int a[10];
    cout<<"please input 10 numbers:"<<endl;
    for(int i=0;i<10;i++)//用于输入内容
    {
        cin>>a[i];
    }
 
    selection_sort(a,sizeof(a)/sizeof(int));//调用函数,要注意sizeof(a)/sizeof(int)的意义
 
    for(int j=0;j<10;j++)//输出数组
    {
        cout<<a[j]<<" ";
    }
    return 0;
}
 
template<class T>
void selection_sort(T Array[],const int size)
{
    int min;//确定最小值的数组下标
    int temp;//中间值
 
    for(int m=0;m<size-1;m++)//外层循环确定边界(即循环的最大值)
    {
        min=m;//确定数组最小值的下标,将之前已排序的固定
        for(int n=m+1;n<size;n++)//内层循环用于判断哪个数据最小
        {
            if(Array[n]<Array[min])//判断最小值
            {
                min=n;//确定最小值的数组下标
            }
        }
 
        if(min!=m)//交换数据
        {
            temp=Array[m];
            Array[m]=Array[min];
            Array[min]=temp;
        }
    }
}

目录
相关文章
|
10月前
|
人工智能 自然语言处理 数据可视化
一键本地部署类GPT大模型,免费!
一键本地部署类GPT大模型,免费!
239 1
|
10月前
48.输入任意正整数,编程判断该数是否为回文数(回文数是指从左到右读与从右到左读一样,如12321)
48.输入任意正整数,编程判断该数是否为回文数(回文数是指从左到右读与从右到左读一样,如12321)
75 0
|
10月前
24.定义一个整型变量,赋予1-100值。要求用户猜这个数,比较两数大小,把结果提示给用户,直到猜对为止
24.定义一个整型变量,赋予1-100值。要求用户猜这个数,比较两数大小,把结果提示给用户,直到猜对为止
92 1
|
10月前
14.输入一个正整数,输出它所有的因子
14.输入一个正整数,输出它所有的因子
57 0
|
10月前
|
C++
【C++基础】类class
【C++基础】类class
58 1
|
10月前
40.验证哥德巴赫猜想:一个大于2的偶数总可以分解成两个素数的和
40.验证哥德巴赫猜想:一个大于2的偶数总可以分解成两个素数的和
101 5
|
10月前
7.求sum=a+aa+aaa+···+a···a(n个a),其中a和n由键盘输入
7.求sum=a+aa+aaa+···+a···a(n个a),其中a和n由键盘输入
37 0
|
10月前
2.任意输入三个数,求最大数
2.任意输入三个数,求最大数
47 0
|
10月前
|
UED iOS开发
「 Sketch超实用教程 」元素基础
「 Sketch超实用教程 」元素基础
85 0
|
10月前
34.设s=1+1/2+1/3+…+1/n,求与8最接近的s的值及与之对应的n值
34.设s=1+1/2+1/3+…+1/n,求与8最接近的s的值及与之对应的n值
141 0