1.插入排序 可以联想成打扑克时手里拿牌的一个过程，手里的牌总是有序的，摸的牌依次比较，放入正确的位置。
#include<iostream> #include<vector> using namespace std; void insertsort(vector<int> &arr) { for(int i=1;i<arr.size();i++)//i与之前的进行比较 { int j=i-1; int temp=arr[i]; while(j>=0 && arr[j]>arr[i] ) { arr[j+1]=arr[j]; j--; } arr[j+1]=temp; } } int main() { vector<int> arr; arr.push_back(2); arr.push_back(1); arr.push_back(4); arr.push_back(3); arr.push_back(7); arr.push_back(6); insertsort(arr); for(int i=0;i<arr.size();i++) { cout<<arr[i]<<endl; } }2.归并排序 联想成桌面有两组牌，依旧比较牌面最上面的牌最小的排好序。
void merge(vector<int> &arr,int p,int q,int r) { vector<int> L; vector<int> R; for(int i=p;i<=q;i++) { L.push_back(arr[i]); }; L.push_back(INT_MAX); for(int i=q+1;i<=r;i++) { R.push_back(arr[i]); } int i=0,j=0; R.push_back(INT_MAX); for(int k=p;k<=r;k++) { if(L[i]<=R[j]) { arr[k]=L[i]; i++; } else if(R[j]<=L[i]) { arr[k]=R[j]; j++; } } } void mergesort(vector<int> &arr,int p, int r) { if (p<r) { int q = (p+r)/2; mergesort(arr, p, q); mergesort(arr, q+1, r); merge(arr, p, q, r); } }3.快速排序 快排主要在于一趟快排的过，即从后向前依次寻找比x小的数，找到了交换，同时i增加。使得x的左边小于x，右边大于x。
int partition(vector<int> &A,int p,int r) { int i=p-1; int x=A[r]; for(int j=p;j<r;j++) { if(A[j]<x) { i++; swap(A[i],A[j]); } } swap(A[i+1],A[r]); return i+1; } void quicksort(vector<int> &A,int p,int r) { if(p<r) { int q=partition(A,p,r); quicksort(A,p,q-1); quicksort(A,q+1,r); } }4.堆排序 建立最大堆，联想建立堆首先要想到维护堆的过程，维护堆则需要比较节点i的左右孩子是否大于i，如果大于则交换，同时继续向下维护。 建立堆则是除去叶子节点，对其他节点依次进行维护。 现在堆顶元素是最大的元素，交换堆顶与arr[n],堆的大小减1，则去掉堆顶，最剩余元素进行维护。
void heapify(vector<int> &arr,int heap_size,int i) { int left=2*i+1; int right=2*i+2; int largest; if(left<heap_size &&arr[left]>arr[i]) largest=left; else largest=i; if(right<heap_size &&arr[right]>arr[largest]) largest=right; if(largest!=i) { swap(arr[i],arr[largest]); heapify(arr,heap_size,largest); } } void build_heap(vector<int> &arr) { //除去叶子节点，进行维护 for(int i=(arr.size()-1)/2;i>=0;i--) heapify(arr,arr.size(),i); } void heap_sort(vector<int> &arr) { //先建堆 build_heap(arr); int heap_size=arr.size(); //再维护,A[0]现在是最大的元素，与A[i]交换，再维护 for(int i=arr.size()-1;i>0;i--) { swap(arr[0],arr[i]); heap_size=heap_size-1; heapify(arr,heap_size,0); } }5.选择排序 这个比较简单，其实就是依次比较出最小的数。
void SelectionSort(vector<int> &arr) { for(int i=0;i<arr.size();i++) for(int j=i+1;j<arr.size();j++) { if(arr[j]<arr[i]) swap(arr[j],arr[i]); } }6.冒泡排序 联想鱼吐泡泡的样子，大的泡泡总是在上面，所以需要将相邻的两个数进行比较，将后面的较大数先比较出来
void BubbleSort(vector<int> &arr) { for(int i=0;i<arr.size();i++) for(int j=0;j<arr.size()-i-1;j++) { if(arr[j]>arr[j+1]) { swap(arr[j],arr[j+1]); } } }7.计数排序 联想哈希表，计数排序从名字上记忆就是比x小的有m个，则x应该在m位（数组从0开始）
vector<int> CountingSort(vector<int> arr,int k)//k是arr数组元素的范围，0-k { int len=arr.size(); vector<int> temp(k+1,0); vector<int> res(len,0); for(int i=0;i<len;i++) { temp[arr[i]]=temp[arr[i]]+1; } for(int i=1;i<=k;i++) { temp[i]=temp[i-1]+temp[i]; } for(int i=len-1;i>=0;i--) { res[temp[arr[i]]-1]=arr[i]; temp[arr[i]]=temp[arr[i]]-1; } return res; }8.基数排序
