冒泡排序

数组间相邻两个元素互相比较，将大的交换到两者之前 一次循环让一个数据移动到最终该出现的位置上 最大的放到当前序列的最后一项，序列长度每次减1

#include <iostream>
using namespace std;

int main() {
    int num[] = {5,4,3,2,1};
    int n = 5;
    int temp = 0;
    for(int i = 1;i<=n-1;i++){//进行n-1次排序
        for(int j = 0;j<=n-1-i;j++){//每次排序到倒数第n-i个元素，因为数组下标从0开始，用<=还要再减1
            if(num[j] > num[j+1]){
                temp = num[j];
                num[j] = num[j+1];
                num[j+1] = temp;
            }
        }
    }
    for(auto &i : num){
        cout<<i<<" ";
    }
}

选择排序

时间复杂度$O(n^2)$ 每次循环中找到一个最小值，并把它交换到前面去，并且在下次循环找最小值的时候从交换的数的后一项开始寻找。

int a[5] = {2,5,8,1,4}
int n = 5;

for(int i = 0;i<n-1;i++){
	int k = i;
	for(int j = i+1;j<n;j++){
		if(a[j] < a[k]) k = j;
	}
	int temp = a[i];
	a[i] = a[k];
	a[k] = temp;
}

插入排序

时间复杂度$O(n^2)$ 从数组的第1项（指数组下标）开始检查，把后面比他大的元素挨个往前放，最后把自己放到比自己小的元素的前一项去。 效率相对选择排序来说较高。

#include <iostream>
using namespace std;
int main(int argc, char const *argv[])
{
    int array[] = {5,2,4,6,1,3};
    int len = sizeof(array)/sizeof(array[0]);
    for(int i = 1;i<len;i++){
        int key = array[i];
        int j = i - 1;
        while(j >= 0 && array[j] > key){
            array[j+1] = array[j];
            j--;
        }
        array[j+1] = key;
    }
    for(auto &i:array){
        cout << i << " ";
    }
    return 0;
}

归并排序

OI WIki https://oi-wiki.org/basic/merge-sort 归并可以使用分治思想实现，将每次归并的两个块之间互相比较，一直到整个序列有序，时间复杂度$O(nlogn)$，一般用递归实现。 归并排序的核心是merge归并操作，将两个已排序的序列转换为一个新的已排序的序列，可以使用algorithm库的merge函数实现：merge( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first ); 可以用递归实现也可以用倍增写。

折半排序

快速排序

桶排序