事先说明，本篇博客的数组都是从下标为1开始使用的，实现的都是升序

第一种:插入排序

思想是从左向右逐一排入下一个要添加进数组有序部分的数组元素，如有待排入有序部分的元素（记为key)比前面有序部分的元素的值小，就让这部分大于key的元素右移一个位置，最后会遇到有序部分比key的值小的元素，因为是有序的数组，所以此时数组前面的元素肯定都比key的值小，所以不需要再向前比较，把key的值方在当前空出来的位置就行了

比方说数组是a[]={0,5,6,4,7,1}，从i为2开始（只有一个数默认有序），定义一个j=i-1,表示key当前比较的元素的下标，key=a[2]=6>a[1]因为6大于5，所以不需要移动，完成一次排入，i++，i变为3，key=a[3]=4,a[3]<a[6],所以要把a[6]向右移动一位，即a[j+1]=a[j],执行一次j--，此时j=1（其实就是元素5的下标）,因为a[1]>key,a[1]也执行一次右移，此时j=0，不满足循环条件，停止循环，但是还要把key放进空出来的位置，执行a[j+1]=key，就是a[0+1]=key,此时数组变为a[]={0,4,5,6,7,1},有序部分是{0,4,5,6}，接下来只要继续按这个逻辑完成剩余的排序就行了

#include <iostream>
using namespace std;
const int N=1e5+10;
int a[N],n;

void insert_sort(){
	int i,j;
	for(i=2;i<=n;i++){
		int key=a[i];
		
		for(j=i-1;j>=1;j--){
			if(a[j]>key)a[j+1]=a[j];
			else break;
		}
		a[j+1]=key;
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	insert_sort();
	for(int i=1;i<=n;i++)cout<<a[i]<<' ';
	return 0;
}

第二种：选择排序

思想就是每次选择数组待排序部分的最小元素依次放在排好序的部分的下一个位置，第一轮排序时排好序的的部分没有元素，下一个位置为1，在未排序的部分找到最小的元素的下标，然后将最小元素与a[1]交换，排好序的部分的下一个位置为2，在后面待排序的元素里继续寻找此时的最小元素，这个最小元素其实就是整个数组的第二小的元素，找到后，交换a[pmin]和a[2]，就尤完成了一轮排序，就这样下去，完成整个数组的排序

#include <iostream>
using namespace std;
const int N=1e5+10;
int a[N],n;
void selection_sort(){

	for(int i=1;i<=n;i++){
			int pmin=i;//待排序部分最小元素的下标索引
		for(int j=i;j<=n;j++){
		if(a[j]<a[pmin])pmin=j;	
		}
		swap(a[i],a[pmin]);
		
	} 
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	selection_sort();
	for(int i=1;i<=n;i++)cout<<a[i]<<' ';
	return 0;
}

第三种：冒泡排序

不懂原理的可以看这篇博客https://mp.csdn.net/mp_blog/creation/editor/151195641

#include <iostream>
using namespace std;
const int N=1e5+10;
int a[N],n;
void bubble_sort()
{
	
	for(int i=1;i<n;i++){
		bool flag=false;
		for(int j=1;j<=n-i;j++){
			if(a[j]>a[j+1]){
				int t=a[j];
				a[j]=a[j+1];
				a[j+1]=t;
				flag=true;
				
			}
		}
		if(!flag)return;
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	bubble_sort();
	for(int i=1;i<=n;i++)cout<<a[i]<<' ';
	
	return 0;
}

第四种：堆排序

堆排序的思想就是，先建立一个最大堆，让父节点都大于等于子节点，这样以来节点1永远是整棵树的最大值，只要每次把堆顶和末尾元素交换，然后让排序元素个数减一，就相当于在数组的有伴部分先排序好大元素，这就实现一轮排序了，下一次只要先继续调成最大堆，就能找到当前待排序部分的最大元素了，又执行交换，以此类推

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], n;
void down(int parent, int len) {
	int child = parent * 2;
	while (child <= len) {
		if (child + 1 <= len && a[child + 1] > a[child])child++;
		if (a[parent] >= a[child])return;
		swap(a[child], a[parent]);
		parent = child;
		child = parent * 2;
	}
}
void heap_sort() {
	//先建最大堆 
	for (int i = n / 2; i >= 1; i--) {
		down(i, n);
	}
	//排序
	for (int i = 1; i < n; i++) {
		
		
		swap(a[1], a[n - i + 1]);
		down(1, n - i);
	}
}
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)cin >> a[i];
	heap_sort();
	for(int i=1;i<=n;i++)cout<<a[i]<<' ';


	return 0;
}

第五种：快速排序

快速排序的实现思想就是每轮排序选择一个基准p，让数组元素中小于p的元素放在基准的左侧，等于p的元素放在中间，大于p的元素放在右侧。当分成小于p和大于p区间的元素个数不为一时，就继续选基准分区间，直到只剩下一个元素，肯定是有序的

放一张图来更好理解，这里的p是随机的

#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
const int N = 1e5 + 10;
int a[N], n;
int get_random(int left, int right) {
	return rand() % (right - left + 1) + left;
}
void quick_sort(int left, int right)
{
	if (left >= right)return;
	
		int p = a[get_random(left, right)];
		int begin = left, end = right, current = left;
		//分成小于p区，等于p区，大于p区
			while (current <= end) {

				if (a[current] < p)swap(a[current++], a[begin++]);
				else if (a[current] == p)current++;
				else swap(a[current],a[end--]);

			}
			quick_sort(left,begin-1);//小于p区
			quick_sort(end+1, right);//大于p区
			
		
	


}
int main()
{
	srand((unsigned int)time(NULL));
	cin >> n;
	for (int i = 1; i <= n; i++)cin >> a[i];
	quick_sort(1, n);
	for (int i = 1; i <= n; i++)cout << a[i] << ' ';

	return 0;
}

第六种：归并排序

放一张图来辅助说明，每次把一个数组分成两个区间，直到每个区间只剩下一个元素，就开始合并区间，左区间定义一个curr1，右区间定义一个curr2，表示当前区间内的索引，因为区间内的元素排序是有序的，（一开始只有一个元素也是有序），所以每次归并时只需要比较左区间的curr1指向的元素和右区间的curr2指向的元素哪个更小，把小的元素放进临时创建的t数组就行了，可能出现一个区间的元素都放完了但另一个区间的元素还没放完的情况，此时只需要在设置一层循环，把剩余元素也放进t数组就行了

#include <iostream>
using namespace std;
const int N=1e5+10;
int a[N],n,t[N];//创建一个临时数组t,用来存放归并的元素
void merge_sort(int left,int right){
	if(left>=right)return ;//即区间只剩一个元素就return
	int mid=(left+right)/2;
	merge_sort(left,mid);
	merge_sort(mid+1,right);
	int curr1=left,curr2=mid+1,index=left;//inex是t的索引
	while(curr1<=mid&&curr2<=right){
		if(a[curr1]<a[curr2])t[index++]=a[curr1++];
		else t[index++]=a[curr2++];
	}
	while(curr1<=mid)t[index++]=a[curr1++];
//有可能t中存完了其中一个区间的元素，但另一个区间的元素没有存完
	while(curr2<=right)t[index++]=a[curr2++];
	for(int i=left;i<=right;i++)a[i]=t[i];
//再把t中存的排好序的元素放回a中
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	merge_sort(1,n);
	for(int i=1;i<=n;i++)cout<<a[i]<<' ';
	return 0;
}