1.用两个栈实现队列

思路：一个栈用来负责入队，一个栈用来负责出队

    //入队void appendTail(int value) {st1.push(value); }//出队int deleteHead() {if(st2.empty() && !st1.empty()){while(!st1.empty()){st2.push(st1.top());st1.pop();}}if(!st2.empty()){int val = st2.top();st2.pop();return val;}return -1;}private:stack st1;stack st2;

2.包含min函数的栈

思路：借助辅助栈，辅助栈存放当前栈里的最小值，与栈进行同步操作，同时入，同时出

如果入栈元素，大于辅助栈的栈顶元素，则将将自己的栈顶元素再入一次，否则直接入要

入栈的元素

    void push(int x) {if(st.empty()){st.push(x);min_st.push(x);return;}st.push(x);if(x>min_st.top()){min_st.push(min_st.top());}else{min_st.push(x);}}void pop() {st.pop();min_st.pop();}int top() {return st.top();}int min() {return min_st.top();}stack st;stack min_st;

3.冒泡排序 O(n^2)   交换次数太多   稳点排序

for(int i = 0; i < size-1; ++i)
{int tag = true;for(int j = 0; j arr[j+1]){swap(arr[j],arr[j+1]);tag = false;}}   if(tag) break;
}

4.选择排序 O(n^2)  交换次数少  不稳定的排序

for(int i = 0; i < size-1; ++i)
{int min = nums[i];int idx = i;for(int j = i+1; j < size; ++j){//记录一趟中最小的元素和下标if(nums[j] < min){min = nums[j];idx = j; }    }if(idx != i){swap(nums[idx],nums[i]);}
} 

5.插入排序 （数据越有序，效率越高）

//认为只有1个元素时，有序
for(int i = 1; i < size; ++i)
{   int val = arr[i]; //要插入的元素int j = i - 1;    //0---i-1 中插入//如果比第一个位置的元素还要小，则退出for(; j>=0; --j){//已经找到合适的位置if(arr[j] >= val){break;}arr[j+1] = arr[j];  //向后移动}arr[j+1] = val;
}

插入排序  > 选择排序 > 冒泡排序

插入排序：没有交换，比较次数比较少，稳定的排序

6.希尔排序

for(int gap = size/2; gap != 0; gap/=2)
{for(int i = gap; i=0; j -= gap){if(arr[j] >= val){break;}arr[j+gap] = arr[j];}arr[j+gap] = val;} }

7.快排(n*log(n)  不稳定)

void QuickSort(int arr[],int begin,int end)
{  if(begin >= end){return;}//优化if(begin - end <= 50){Insert(arr,begin,end);return;}int pos = Partation(arr,begin,end);QuickSort(arr,begin,pos-1);QuickSort(arr,pos+1,end);     
}int Partation(int arr[],int left,int right)
{//三数取中//arr[left]   arr[right]  arr[(left+right)/2]int val = arr[left];while(left < right){while(left < right && arr[right] > val){--right;}if(left < right){arr[left] = arr[right];++left;}while(left < right && arr[left] < val){++left;}if(left < right){arr[right] = arr[left];--right;         }       }  arr[left] = val; return left;
}void InsertSort(int arr[],int left,int right)
{for(int i =  left+1; i < right; ++i){int val = arr[i];int j = i - 1;for(;j>=0;--j){if(arr[j]>=val)break;arr[j+1] = arr[j];  }arr[j+1] = val;}
}

8.归并排序（稳定排序，O(n) + log(n)）

vec.resize(sizeof(arr),0);void MerageSort(int arr[],int begin,int end)
{if(begin <= end){return;}int mid = begin + ((end - begin)>>1);MerageSort(arr,begin,mid);MerageSort(arr,mid+1,end);Merage(arr,begin,mid,end);
}void Merage(int arr[],int begin,int mid,int end)
{int i = begin;int j = mid+1;int idx = 0;while(i<=mid && j<=end){if(arr[i] <= arr[j]){vec[idx] = arr[i];++i;}else{vec[idx] = arr[j];++j;}++idx;}while(i<=mid){vec[idx] = arr[i];++i;++idx;}while(j<=end){vec[idx] = arr[j];++j;++idx;}idx = 0;for(;begin <= end; ++begin,++idx){arr[begin] = vec[idx];}
}
private:vector vec; 

9. 优先级队列

思路：将数组中存储的元素看成一个完全二叉树

第一个非叶节点下标：(n-1)/2     n表示数组最后一个元素的下标

0 <= i  && i <= (n-1)/2   所有的非叶子结点 

小根堆：arr[i] < arr[2i+1]  && arr[i] < arr[2i+2]

大根堆：arr[i] > arr[2i+1]  && arr[i] > arr[2i+2]

求一个结点的双亲结点：(chid-1)/2 

//大根堆
//size_  表示数组中已有元素的个数
int top()
{if(size_ == 0)throw "container is empty";       return arr[0];
}bool empty()
{return size_ == 0;
}void push(int val)
{if(size_ == 0){arr[size_] = val;}else{//要插入元素的下标和值upShift(size_,val);}++size_;
}void pop()
{if(empty()){return;}else{--size_;       //删除元素后，最后一个元素的下标，和第一个元素的值downShift(0,arr[size_]);}
}private:void upShift(int i,int val){      while(i>0){int parent = (i-1)/2;if(arr[parent] < val){arr[i] = arr[parent];}elsebreak;i = parent;}   arr[i] = val;}void downShift(int i,int val){while(i <= (size_-1-1)/2){int child = 2*i+1;if(child+1 < size_ && arr[child] < arr[child+1]){child = child + 1;}if(val < arr[child]){arr[i] = arr[child];}else{break;}i = child;}arr[i] = val;}

10.堆排   O(logn)*O(n)  不稳定

1.从第一个非叶子节点开始，把二叉堆调整成一个大根堆

从(n-1)/2号位元素开始到堆顶元素(0)，进行下沉操作

将数组的元素调整成一个大根堆

2.每次将堆顶元素与最后一个叶子结点交换，每次排出一个堆内的最大值

void HeapSort(int arr[],int size)
{//调整成大根堆for(int i = (size-1-1)/2; i >=0 ; --i){downShift(arr,i,size);}//交换堆顶和最后一个叶子结点，进行调整for(int n = size-1; n>0; --n){swap(arr[n],arr[0]);downShift(arr,0,n);}
}void downShift(int arr[],int i,int size)
{int val = arr[i];while(i<=(size-1-1)/2){int child = 2*i+1;if(child + 1 < size && arr[child] < arr[child+1]){child = child+1;}if(arr[child] > val){arr[i] = arr[child];i = child;}else{break;}}arr[i] = val;  
}