排序是个十分重要的事情，老手们直接用sort，但是新手们不会怎么办，那就先学排序，排序都没学还想学sort

1.选择排序

选择排序的原理，就是每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

就是这样

• 1
• 5
• 2
• 4
• 0 ←选择最小的
• 128
• 435
• 12
• 3

放入列表第一位0

接着找

• 1 ←选择最小的
• 5
• 2
• 4
• 128
• 435
• 12
• 3

再放入列表后0 1

以此类推

代码如何实现呢？

先寻找最小的数

int minn;
for(int j=1;j<=n;j++){
    minn=min(minn,a[i]);
}

在放入新列表中

b[i]=minn;

代码如下

for(int i=1;i<=n;i++){
    int minn=2100000000;
    for(int j=1;j<=n;j++){
        minn=min(a[j],minn);
    }
    b[i]=minn;
}

这个排序的时间复杂度为 $O(n^2)$ , 空间复杂度为$O(n)$

2.冒泡排序

冒泡排序就是重复“从序列右边开始比较相邻两个数字的大小，再根据结果交换两个数字的位置”这一操作的算法。

说白了就是往上比，比他大就换了他。

代码如下

for(int i=1;i<n;i++){ 
		for(int j=i;j<=n;j++){ 
			if(a[i]>a[j]){ 
				swap(a[i],a[j]); 
			} 
		} 
} 

3.插入排序

算法步骤：将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。

像打扑克整牌一样

动图如下

代码如下

#include<iostream>
#include <climits>
using namespace std;
int main(){
    int n;
    cin>>n;
    int a[n+1];
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        int g=INT_MAX,m=0;
        for(int j=i;j<=n;j++){
            if(a[j]<g){
                g = a[j];
                m = j;
            }
        }
        swap(a[i],a[m]);
    }
    for(int i=1;i<=n;i++){
        cout<<a[i]<<" ";
    }
    return 0;
}