剑指Offer --- C++ 栈，队列，排序算法_剑指offer 深度优先 堆栈

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<int> st1;
    stack<int> 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<int> st;
    stack<int> min_st;

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

for(int i = 0; i < size-1; ++i)
{
    int tag = true;
    for(int j = 0; j<size-1-i; ++j)
    {   
       if(arr[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<size; i++)
    {
        int j = i-gap;
        int val = arr[i];
        for(; j>=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<int> 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];
            }
            else
                break;
 
            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;  
}