直接插入排序
第一個結(jié)點默認已序，從第二個結(jié)點開始躺翻，即i=1鳞芙。每次使用一個tmp報錯第i個結(jié)點眷柔，然后依次將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;
}
}
折半插入排序（穩(wěn)定的）
思路與直接插入相同喳坠，只是查找插入位置的方法不同鞠评，這里使用折半查找法查找插入點。查找到之后壕鹉，一次性將所有元素后移以為剃幌，然后插入元素。
這里有個疑問：為什么取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;
}
}
希爾排序（不穩(wěn)定）?
希爾排序是直接插入排序的優(yōu)化版
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; //只要有交換，就設(shè)置成true
}
}
}
}
快速排序
#python實現(xiàn)
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++實現(xiàn)
//劃分（主要）
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]){ //左孩子與父節(jié)點比較大小础芍，取大
largest = left;
}
if(right<n && data[right]>data[largest]){ //右孩子與父節(jié)點比較大小，取大
largest = right;
}
if(largest != i) {
swap(data[largest],data[i]); //交換使得父節(jié)點最大
Heapify(data,n,largest); //遞歸建堆
}
}
void HeapSort(vector<int> &data){
int len = data.size();
//建初始堆
for(int i = len/2-1;i>=0;i--){//從最后一個父節(jié)點往前建立堆
Heapify(data,len,i);
}
//堆排序
for(int j = n-1;j>=0;--j){
data[j] = data[0]; //排序
Heapify(data,j,0);
}
}
基數(shù)排序（來自力扣）
基數(shù)排序是一種非比較型整數(shù)排序算法数尿，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字仑性，然后按每個位數(shù)分別比較。排序過程是將所有待比較數(shù)值統(tǒng)一為同樣的數(shù)位長度右蹦，數(shù)位較短的數(shù)前面補零诊杆，然后從最低位開始，依次進行一次排序何陆。這樣從最低位排序一直到最高位排序完成以后, 數(shù)列就變成一個有序序列晨汹。
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);
}
