常见算法

常见的算法 总结，会陆续更新，这些算法可以直接使用

排序算法

1
2
3
4
5
6
7
8
9
10
11
int main()
{
    int data[] = {1,2,6,3,4,7,7,9,8,5};
    //bubble_sort(data,10);
    //select_sort(data,10);
    Insert_Sort(data,10);
    for(int i = 0; i < 10; i++)
        cout << data[i] <<" ";
    cout <<endl;
     return 0;
}

直接插入排序 O(n^2) 稳定



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//插入排序
void Insert_Sort(int *pData, int Count)
{
    int iTmp ;
    int iPos;

    for(int i = 1; i < Count; i++)
    {
        iTmp = pData[i];
        iPos = i-1;
        while(iPos>=0 && pData[iPos]>iTmp)
        {
            pData[iPos+1] = pData[iPos];
            iPos--;
        }
        pData[iPos+1] = iTmp;
    }
 return ;
}


冒泡排序 O(n^2) 稳定



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//*** 冒泡排序 **//
void bubble_sort(int *pData, int count)
{
    for(int i = 0; i < count; i++)
    {
        for(int j = count-1; j >= i; j--)
        {
            if(pData[j] < pData[j-1])
            {
                int tmp;
                tmp = pData[j];
                pData[j] = pData[j-1];
                pData[j-1] = tmp;
            }
        }
    }
}


选择排序 O(n^2) 不稳定



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

//***选择排序***///
void select_sort(int *pData, int count)
{
    int tmp;
    int iPos;
    for(int i = 0; i < count-1; i++ )
    {
       tmp = pData[i];
       iPos = i;
       for(int j = i+1; j < count; j++)
       {
           if(pData[j] < tmp)
           {
               tmp = pData[j];
               iPos = j;
           }
       }
       pData[iPos] = pData[i];
       pData[i] = tmp;
    }

}


快速排序 O(nlog(n)) 不稳定



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//快速排序
void Quick_Sort(int *pData, int low, int hight)
{
      int i = low;
      int j = hight;
      int x = pData[i];
      if(low > hight)
        return;
      while( i < j )
       {
        while( i < j &&  pData[j] >= x) 
             j--;
             pData[i] = pData[j]; 
        while( i < j &&  pData[i] <= x)  
             i++;
             pData[j] = pData[i];
       }
      pData[i] = x;
      Quick_Sort(pData, low, i-1);
      Quick_Sort(pData, i+1, hight);
}


希尔排序 O(nlog(n)) 不稳定



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void Insert_Sort(int *pData, int Count)
{
    int iTmp ;
    int iPos;
    int gap = Count;
   do{
        gap = gap / 3  + 1; //后面一定要有+1 ，不然无法保证最后的间隔为1
       for(int i = gap - 1 ; i < Count; i++)
        {
           iTmp = pData[i];
           iPos = i-gap;
          while( iPos >= 0 && pData[iPos] > iTmp )
          {
              pData[iPos+gap] = pData[iPos];
              iPos -= gap;
          }
          pData[iPos+gap] = iTmp;
        }
      }while(gap > 1);
      return ;
}


归并排序 O(nlog(n)) 稳定



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//归并排序
void Merge_Sort(int *pData, int Count)
{
  if(Count > 1)
    {
       int  *list1 = pData;
       int  list1_size = Count / 2;
       int  *list2 = pData + list1_size;
       int  list2_size = Count - list1_size;

       Merge_Sort(list1,list1_size);
       Merge_Sort(list2,list2_size);
       Merge(list1,list1_size,list2,list2_size);
    }
  return;
}

void Merge(int *list1, int list1_size, int *list2, int list2_size)
{
   int tmp[list1_size+list2_size];
   int i = 0;
   int j = 0;
   int k = 0;
   while (i < list1_size  && j < list2_size )
     {
       if( list1[i] < list2[j])
         tmp[k++] = list1[i++];
       else
         tmp[k++] = list2[j++];
     }

   while (i < list1_size)
       tmp[k++] = list1[i++];

   while (j < list2_size)
       tmp[k++] = list2[j++];

   int m = 0;
   for(; m < (list1_size + list2_size);m++)
     list1[m] = tmp[m];
return;
}


斐波那契

递归



1
2
3
4
5
6
7
long jumpFloor(int number) {
    if(number <= 0)
        return 0;
    else if(number == 1 )
        return 1;
    return  jumpFloor(number-1)+jumpFloor(number-2);
}


非递归



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
long jumpF(int number) {
   int result[2] = {0,1};
   if(number < 2)
        return result[number];
    long long  sum = 0;
    long long tmpOne = 1;
    long long tmpTwo = 0;
    for(unsigned int i = 2; i <= number; i++)
    {
        sum = tmpOne + tmpTwo;
        tmpTwo = tmpOne;
        tmpOne = sum;
    }
    return sum;
}


二叉树层次遍历 非递归



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void  LevelOrder(Tree* T)
{
    if(T == NULL)
       return ;
    queue<Tree *> myqueue;
    myqueue.push(T);
    while(!myqueue.empty())
    {
        Tree *tmp = myqueue.front();
        if(tmp->leftChild != NULL)
            myqueue.push(tmp->leftChild);
        if(tmp->rightChild != NULL)
            myqueue.push(tmp->rightChild);
        cout << tmp.val<<" ";
        myqueue.pop();
    }

}


二叉树前序遍历 递归



1
2
3
4
5
6
7
8
void  PreOrder(Tree* T)
{
    if(T == NULL)
       return ;
    cout << T.val << " ";
    PreOrder(T->leftChild);
    PreOrder(T->rightChild);
}


二叉树中序遍历 递归



1
2
3
4
5
6
7
8
void  InOrder(Tree *T)
{
    if(T == NULL)
       return ;
    InOrder(T->leftChild);
    cout << T.val << " ";
    InOrder(T->rightChild);
}


二叉树后序遍历 递归



1
2
3
4
5
6
7
8
void  PostOrder(Tree* T)
{
    if(T == NULL)
       return ;
    PostOrder(T->leftChild);
    PostOrder(T->rightChild);
    cout << T.val << " ";
}


二叉树的深度 递归



1
2
3
4
5
6
7
8
9
10
11
int DepthOfTree(Node* root)
{
    if(root)
    {
        return DepthOfTree(root->Left)>DepthOfTree(root->Right)?DepthOfTree(root->Left)+1:DepthOfTree(root->Right)+1;
    }
    if( root == NULL )
    {
        return 0;
    }
}


二叉树叶子节点数 递归



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int Leafnum(Node* root)
{
    if(root == NULL)
    {
        return 0;
    }
    else if(  (root->Left == NULL) && (root->Right == NULL) )
    {
        return 1;
    }
    else
    {
        return  (Leafnum(root->Left) + Leafnum(root->Right)) ;
    }
}


判断一棵树是不是平衡二叉树



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        getDepth(pRoot);
        return isBalanced ;
    }
 //判断左右子树是不是都是平衡二叉树   
    private :
      bool isBalanced = true;
    public:
    int getDepth(TreeNode  *root)
    {
        if(root == NULL)
            return 0;
        int left = getDepth(root->left);
        int right = getDepth(root->right);
        if((left-right) >1  || (right-left) > 1)
            isBalanced = false;
        return right > left ? right+1 : left+1;
    }
};


赏

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

icedxu<br><br>只做了一点微小的工作<br>icedxu