猫史档案馆

上个帖子我们学了排序和冒泡排序的基本思路

这次要学习另外两个基础的排序：选择排序和插入排序 （本次所有排序皆为从小到大排序）    

 

 

选择排序 

首先，我们来分析一下冒泡排序的缺点 

首先它遍历整个数组，依次比较两个相邻的元素，如果顺序不一致就交换

打个比方

体育课上，老师要根据学生的身高来排队

体育老师：一号你比二号高，你和他换一下！

[3,1,4,5,1]

体育老师：二号你比三号矮，不用换了！

[1,3,4,5,1]

体育老师：三号你比4号矮，不用换了！

[1,3,4,5,1]

体育老师：4号你比五号高，你和他换一下！

[1,3,4,5,1]

[1,3,4,1,5]

而这仅仅只是冒泡排序的第一轮 

要是按照冒泡排序进行四轮的话，那学生会不会想：“这老师是不是有什么那个？”（会被猫站屏蔽成“喵”）

所以说，冒泡排序的缺点是交换次数太多

 

我们拿上个例子举例选择排序 

体育老师：4号你是前五个人里最高的，你和五号换一下！

[3,1,4,5,1]

体育老师：三号你是前四个人里最高的，你和4号（原五号）换一下！

[3,1,4,1,5]

体育老师：一号你是前三个人里最高的，你和三号（原五号）换一下！

[3,1,1,4,5]

体育老师：你已经是前两个人里最高的，不用换了！（这里认为1<1也就是如果两个相等，后一个大于前面的一个）

[1,1,3,4,5]

[1,1,3,4,5]

这就是选择排序的基本思路

一共执行(n-1)轮

在第x轮时在前(n-x+1)个元素里找最大的数，然后与最后一个元素(n-x+1)互换。

从上面的举例我们还能分析出

选择排序是不稳定排序

在3和1互换的时候，后面的1在一开始的数组里表示五号，但是结束的时候跑到了一号位

原二号位的1在原五号的1的后面

所以选择排序是不稳定排序  

至于选择排序的时间复杂度和空间复杂度

空间复杂度因为选择排序是原地排序，没有借助任何的空间来辅助排序

所以选择排序的空间复杂度是O(1)

时间复杂度，看起来就交换了(n-1)次，事实上，在前(n-x+1)个元素里找最大的数也是一次遍历 所以他的时间复杂度还是O(n^2)（n的平方）      

 

插入排序

 

 

插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法

 

大家应该玩过扑克牌吧（或者麻将）

在排列扑克牌时，大家大多数是在合适的地方直接插入进去

什么是合适的地方呢？

比如[10,J,K]进来一个Q

因为Q比K小并且比J大，所以把他插入进J与K之间

插入排序的基本思路跟这差不多  

 

插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的

现将第n个数插入前面已经排好的序列中，然后找到合适自己的位置

使得插入第n个数的这个序列也是排好顺序的 按照此法对所有元素进行插入

直到整个序列排为有序的过程，称为插入排序（这里偷懒了，直接复制百度）  

打个比方

[1,4,6,5,1]

首先进行第一轮

[1,4,6,5,1]

比较4和1，发现4比1大，所以他们俩不互换

第二轮

[1,4,6,5,1]

比较6和4，发现6比4大，所以他们俩不互换

第三轮

[1,4,6,5,1]

比较5和6，发现5比6小，所以他们俩互换

[1,4,5,6,1]

然后比较4和5，发现5比4大，所以他们俩不互换

第四轮

[1,4,5,6,1]

比较1和6，发现1比6小，所以他们俩互换

[1,4,5,1,6]

然后比较1和5，发现1比5小，所以他们俩互换

[1,4,1,5,6]

然后比较1和4，发现1比4小，所以他们俩互换 [1,1,4,5,6] 最后比较1和1，发现1和1相等，所以他么俩不互换

[1,1,4,5,6]

那么插入排序到这里就排序完了  

插入排序的空间复杂度和选择冒泡一样，是O(1)

时间复杂度在最好的情况下是O(n),最坏的情况下是O(n^2)    

 

 

好了，有关插入、选择的内容我就讲到这里了

感兴趣的朋友可以去翻我之前的教学帖 也可以翻翻评论区看我有没有写代码）

这次的代码我把冒泡、选择、插入写在一起，可以复制其中一个

再见awa      

 

#include<iostream>
using namespace std;
int a[1000],n;
void print(){
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
    cout<<endl;
}
void bubble(){//冒泡
    for(int i=0;i<n-1;i++){
        for(int j=0;j<n-i-1;j++){
            if(a[j]>a[j+1])swap(a[j],a[j+1]);
        }
    }
}
void select(){//选择
    for(int i=0;i<n-1;i++){
        int max=a[i],maxindex=i;
        for(int j=n-1;j>i+1;j--){
            if(max>a[j]){
                max=a[j];
                maxindex=j;
            }
        }
        swap(a[i],a[maxindex]);
    }
}
void insert(){//插入
    for(int i=1;i<n;i++){
        for(int j=i;j>0;j--){
            if(a[j-1]>a[j])swap(a[j-1],a[j]);
        }
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    // bubble();
    select();
    // insert();
    print();
    return 0;
}