冒泡排序

原理： 从前往后（或从后往前）两两比较相邻元素的值，若为逆序（即 a[i]>a[i + 1] ），则交换它们，直到序列比较完。每一轮结束时会在待排序元素中，将最大（或最小）的元素排序至正确的位置。

//将数组 a 从中的 n（1-n）个元素从小大升序排序 
void bubble_sort(int a[], int n) {
	for (int i = 1; i < n; i++) { // 仅需 n - 1轮 
		bool flag = true; // 可以提前结束 
		for (int j = 1; j <= n - i; j++) { // 每轮仅需 n - i 次比较 
			if (a[j] > a[j + 1]) {
				swap(a[j], a[j + 1]);
				flag = false;
			}
		}
		if (flag)	return ;
	}
	return ; 
}

选择排序

原理：在待排序序列中头至尾找出最小的一个关键字，与待排序序列中第一个关键字进行交换，重复此操作，最终使序列有序。

//将数组 a 从中的 n（1-n）个元素从小大升序排序 
void select_sort(int a[], int n) {
	for (int i = 1; i < n; i++) {
		int k = i; // 最小元素的位置 
		for (int j = i + 1; j <= n; j++) {
			if (a[j] < a[k]) {
				k = j; // 找出最小元素的位置 
			} 
		}
		swap(a[i], a[k]);
	}
	return ; 
}

插入排序

原理：每次将一个待排序的关键字按大小插入前面已排好的序列中，直到全部关键字插入结束。

//将数组 a 从中的 n（1-n）个元素从小大升序排序 
void insert_sort(int a[], int n) {
	for (int i = 2; i <= n; i++) {
		int t = a[i], j = i - 1;
		while (a[j] > t && j >= 1) { //判断是否可以插入到第 j 个元素之后 
			a[j + 1] = a[j];
			j--; // 继续向前比较 
		}
		a[j + 1] = t;
	}
	return ; 
}

计数排序

原理：计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

计数排序不是基于比较的排序算法

#include<bits/stdc++.h>
using namespace std;  
  
int main()  
{  
    int a[1005]={0}; // 初始化一个大小为 1005 的数组，用于计数，元素初始值设为 0  
    int n,t; // n 代表待排数的数量，t 用于临时存储输入的数字  
    cin>>n; // 输入待排数的数量  
      
    for(int i=1;i<=n;i++)   
    {  
        cin>>t; // 输入一个数字   
        a[t]++; // 将该数字的计数加 1，实现“投票”  
    }  
      
    // 从第 0 个桶遍历到最后 1000 个桶
    for(int i=0;i<=1000;i++)   
    {  
        // 当当前桶中有数（即计数不为 0）时  
        while(a[i])   
        {  
            cout<<i<<" "; // 输出桶对应的数字  
            a[i]--; // 减少计数，相当于从这个桶中取出一个数  
        }  
    }  

    return 0;  
}

总结

将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程叫做排序。为了查找方便，计算机中的数据表都希望是按照关键字有序的，一般按照递增或递减方式排列。

衡量标准

1.时间复杂度

2.空间复杂度

3.稳定性

(不稳定：希尔选择快速堆)