直接插入排序
第一个结点默认已序，从第二个结点开始，即i=1。每次使用一个tmp报错第i个结点，然后依次将tmp与第[i-1 ~ 0]的元素进行比较，如果tmp小于其元素，则依次后移。直到找打插入位置。
void InsertionSort(vector<int> &data){
for(int i = 1;i<data.size();++i){
int tmp = data[i];
for(int j = i;j>0&&tmp<data[j-1];--j){
data[j]=data[j-1]; //向后覆盖
}
data[j]=tmp;
}
}
折半插入排序（稳定的）
思路与直接插入相同，只是查找插入位置的方法不同，这里使用折半查找法查找插入点。查找到之后，一次性将所有元素后移以为，然后插入元素。
这里有个疑问：为什么取low<=high？
void InsertionSort(vector<int> &data){
for(int i = 1;i<data.size();++i){
int tmp = data[i];
int low = 0,high=i-1;
while(low<=high){//为什么取等号？
int mid = (low+high)/2;
if(data[mid]>tmp) high=mid-1;
else low=mid+1;
}
for(j = i-1;j>=high+1;--j){
data[j+1]=data[j];
}
data[high+i]=tmp;
}
}
希尔排序（不稳定）?
希尔排序是直接插入排序的优化版
void ShellSort(vector<int> &data){
int len = data.size();
for(int dk = len/2;dk>=1;dk=dk/2){
for(int i = dk+1;i<n;++i){
if(data[i]<data[i-dk]){
int tmp = data[i];
for(int j = i-dk;j>=0&&tmp<data[j];j-=dk){
data[j+dk] = data[j];
}
data[j+dk] = tmp;
}
}
}
}
冒泡排序
i从0开始到n-2;
j从n-1开始到i+1,运行条件为j>i或者flag = false
遇到data[j]<data[j-1]不断交换，每一趟都能过把最元素放到最终的位置
void BubbleSort(vector<int> &data){
bool flag = true;
for(int i = 0;i<data.size()-1 && flag;++i){ //若flag为false，停止，表示上一趟没有交换
for(int j = data.size()-1,flag=false;j>i;--j){
if(data[j]<data[j-1]){
swap(data[i],data[j-1]);//小的往前移动，每次最小的都能过到最后的位置
flag = true; //只要有交换，就设置成true
}
}
}
}
快速排序
#python实现
def quik_sort(data):
if len(num)<2: //包含[],[x]的情况
return data
else:
pivot = data[0]
less = [x for x in data[1:] if x <=pivot]
greater = [x for x in data[1:] if x >pivot]
return quik_sort(less)+pivot+quik_sort(greater)
#C++实现
//划分（主要）
int Partition(vector<int> &data,int low,int high){
int pivot = data[low];
while(low<high){
while(low<high&&data[high]>=pivot) --high;
data[low]=data[high];//此时low空出来了
while(low<high&&data[low]<=pivot) ++low;
data[high]=data[low];//此时high空出来了
}
data[low] = pivot; //排序
return low;
}
void QuikSort(vector<int> &data,int low,int high){
if(low<high){
int pivot_pos = Partition(data,low,high);
QuikSort(data,pivot_pos+1,high);
QuikSort(data,low,pivot_pos-1);
}
}
简单选择排序
void SelectSort(vector<int> &data){
for(int i = 0;i<n-1;++i){
int min = i;
for(int j = i;j<n;j++){
if(data[j]<data[min])
min = j;
}
if(i!=min) swap(data[i],data[min]);
}
}
归并排序
void Merge(vector<int> &data,int left,int mid,int right){
auto beg = data.begin();
vector<int> Left(beg+left,beg+m); //开辟一个辅助空间，存储左边的元素
int i = 0; //index of Left
int j = m,k = 0;
while(i<Left.size()&&j<=right){
if(Left[i] <= data[j]) data[k++] = Left[i++];
else data[k++] = data[j++];
}
while(i<Left.size()) data[k++] = data[i++];
}
void MergeSort(vector<int> &data,int left,int right){
if(left<right){
int mid = left+(right-1)/2;
MergeSort(data,left,mid);
MergeSort(data,mid+1,right);
Merge(data,left,mid,right);
}
}
堆排序
void Heapify(vector<int> &data,int n,int i){
int largest = i;
int left = 2*i+1; //左孩子
int right = 2*i+2; //右孩子
if(left<n && data[right]>data[largest]){ //左孩子与父节点比较大小，取大
largest = left;
}
if(right<n && data[right]>data[largest]){ //右孩子与父节点比较大小，取大
largest = right;
}
if(largest != i) {
swap(data[largest],data[i]); //交换使得父节点最大
Heapify(data,n,largest); //递归建堆
}
}
void HeapSort(vector<int> &data){
int len = data.size();
//建初始堆
for(int i = len/2-1;i>=0;i--){//从最后一个父节点往前建立堆
Heapify(data,len,i);
}
//堆排序
for(int j = n-1;j>=0;--j){
data[j] = data[0]; //排序
Heapify(data,j,0);
}
}
基数排序（来自力扣）
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。排序过程是将所有待比较数值统一为同样的数位长度，数位较短的数前面补零，然后从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
int getMax(int arr[], int n)
{
int mx = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i];
return mx;
}
void countSort(int arr[], int n, int exp)
{
int output[n];
int i, count[10] = {0};
for (i = 0; i < n; i++)
count[ (arr[i]/exp)%10 ]++;
for (i = 1; i < 10; i++)
count[i] += count[i - 1];
for (i = n - 1; i >= 0; i--)
{
output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];
count[ (arr[i]/exp)%10 ]--;
}
for (i = 0; i < n; i++)
arr[i] = output[i];
}
void radixsort(int arr[], int n)
{
int m = getMax(arr, n);
for (int exp = 1; m/exp > 0; exp *= 10)
countSort(arr, n, exp);
}
