排序算法

• 冒泡：由后往前每两个数对比，逆序则交换，否则不动。

    int temp;
    for(int i=0;i<length;i++){
        for(int j=length-1;j>i;j--){
            if(a[j]<a[j-1]){
                //temp交换
            }
        }
    }
  

  • o(n*n)
  • 优化：若未循环完成便排好序：设置flag，若发生交换则继续下一轮比较，否则停止

• 选择排序：遍历后[length-i]个数找出最小值与与第i 个数交换

  • o(n*n)

• 插入排序：由前往后，每轮将第i+1个数与前i个数对比，找到其在前i+1个数中的位置

    int temp;
    for(int i=0;i<length-1;i++){
        for(int j=i+1;j>0;j--){
            if(a[j]<a[j-1]){
                //交换值
            }
        }
    }
  

  • o(n*n)，交换次数与数组初始顺序有关
  • 改进方法：比较后将较大元素右移

• 希尔排序：快速的插入排序，将数组按一定间隔（>N/3）分为若干组，每组内进行插入排序，适用于中等大小数组

    int temp;
    int space = length
    while(space>1){
        space=space/2;
        for(int k=0;k<space;k++){//分组
            //每组内对比循环
            for(int i=k+space;i<length;i+=space){
                for(int j=i;j>k;j-=space){
                    if(a[j]<a[j-space]){//交换}
                }
            }
        }   
    }
  

• 归并排序：将数组一分为二，分别进行排序，然后将结果合并至第三个数组，比较两组第一个值，并取最小值为新数组第一位，并删去原数组中被取的值，然后继续比较原数组第一位并取小值放入新数组。实际中首先分为一个数为一组，进行两两合并直到合并为一个数组。

  • o(NlogN)
  • 原地归并：

• 快速排序：数组中取第一个数作为key值，将比其小的方左边，大的放右边；再在左右两子数组中随机选key值重复排列，直到各区间只有一个数

    public static void quickSort(int a[],int l;int r){
        if(l>=r) return;//左右数组起始位置相同，即每段只有一个数时打破递归
        
        int i=l;int j=r;int key=a[l];
        while(i<j){
            while((a[i] <= key)?true:false)
        }
    }
  

  • 改进：
    • 在小数组中效率不如插入排序，可以在数组到达较小值时不再进行下一步迭代，然后改用插入排序
    • 自数组中部分元素中位数切分数组

队列、栈

• 栈：（栈顶）后进先出，可用数组或链表表示
  • 顺序栈：地址连续的存储单元依次存放自栈底到栈顶顶元素，并设置top指针指向栈顶的位置（top.next 为栈顶元素）,base指针指向栈底（a[length-1]）。初始分配基本容量，空间不足时再扩大
  • 链表栈：栈顶元素作为第一个结点，栈底元素作为最后一个结点
• 队：先进（队尾）先出（队头），只允许在队尾添加队头删除，数组或链表表示
  • 链队列：头指针->头结点->队列结点<-尾指针，队为空时头尾指针均指向头结点
  • 顺序队列：地址连续的存储单元依次存放队头到队尾的元素。初始时pfront->a[0],prear->a[0]。插入时pfront地址加一
  • 双端队列：两头都可以添加删除

数组、链表

• 数组：一块连续空间保存数据，分配内存时大小固定
  • 根据下标访问o(1),查找指定数据o(n)，插入或删除任意位置元素，其后元素都要移动
• 链表：不连续的内存单元中保存数据(data与指针next)，大小不固定。头指针->（头结点->）结点->null
  • 访问第i个元素与查找指定数据o(n)，插入删除o(1)
  • 双向链表：插入与删除
  • 循环列表：最后一个元素指针指向头结点而不是null，遍历条件为元素指针是否等于头指针
  • 双向循环链表
  • 静态列表：数组加指针，由指针指明该数组元素在链表中的结点位置
  • 翻转：

    • 迭代：保证临时指针p指向原链表剩余部分的头，否则原链表将不能遍历

      1.0->1->2->3->null

      2.新增p->2,0-><-1,p->2->3->null

      3.p->3->null,0-><-1<-2

      4.p->null,0-><-1<-2<-3

      5.null<-0<-1<-2<-3

        Node pre = head.next;Node cur = pre.next();Node p;//头结点指向第一个结点，可以包含链表附加信息
        while(cur != null){
            p = cur.next();
            cur.next = pre;
            pre = cur;
            cur = p;
        }
        head.next = pre;
      

    • 递归：递归找到最后一个结点，反回上一层递归，改变翻转下一结点指针，并将当前结点指向null，然后返回新的头结点，保存其在递归中不变

        reverse(Node H){
            //链表为空或H到达尾结点
            if(H==null||H.next==null) return H;
            Node NewHead = reverse(H.next);//递归到链尾
            H.next.next = H;//到达链尾返回上一层递归中
            H.next = null;
            return NewHead;//递归中保持新的第一个结点不变
        }
      

    • 合并:有序链表La,Lb链表合并到Lc，借助3个指针分别指向La、Lb头结点和Lc尾结点

      Node pa = La.head.next;Node pb = Lb.head.next;
      Node pc = Lc.head;
      while(pa!=null && pb!=null){
      if(pa.val <= pb.val){
      pc.next = pa;
      pc = pa;
      pa = pa.next;
      }else{
      pc.next = pb;
      pc = pb;
      pb = pb.next;
      }
      pc.next = (pa == null)?pb:pa;//插入剩余链表
      }

堆排序:

• 无序组排为小顶堆／大顶堆：

  • 从最后一个尾结点（arr.length-1）对应的非叶结点（i=arr.length/2-1）开始，对比该非叶结点与其子树大小并交换

      for(k=i*2+1;k<length;k=k*2+1){ //每层左右子节点遍历完后再便利子节点的子树
          //左右子节点中最大值交换
          if(k+1<length && a[k]<a[k+1]){
              k++; //移到右子节点
          }
          if(a[k]>a[i]){
              //交换
          }else{break;}               
      }   
    

• 将堆顶元素（arr[0]）与堆尾元素（arr[length-1]）交换，移出堆尾最值，并重新排列a[0]到a[length-2]的堆
• 选择排序，时间复杂度o(nlogn),空间复杂度o(1)

广义表：线性表（数组、链表）的推广，结点可以时元素或广义表

查找

• 二分查找：有序表中，取中间的记录作为比较关键字，若给定值与中间记录的关键字相等，则查找成功；若给定的值小于中间记录的关键字，则在中间记录的左半区间继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区间继续查找；不断重复这个过程，直到查找成功。否则查找失败。最好o(1)，最坏o(logn)
• 差值查找
• 顺序查找：遍历o(n)
• 二叉树查找：左分支小于右分支数据
• hash表查找

二叉树遍历

• 先序遍历：根左右

    b_tree(BTree pTree){
        if(pTree){
            sout(pTree.data);
            if(pTree.lChild) b_tree(pTree.lChild);
            if(pTree.rChild) b_tree(pTree.rChild);
        }
    }
  

• 中序遍历：左根右

    b_tree(BTree pTree){
        if(pTree){
            if(pTree.lChild) b_tree(pTree.lChild);
            sout(pTree.data);
            if(pTree.rChild) b_tree(pTree.rChild);
        }
    }   
  

• 后序遍历：左右根

    b_tree(BTree pTree){
        if(pTree){
            if(pTree.lChild) b_tree(pTree.lChild);
            if(pTree.rChild) b_tree(pTree.rChild);
            sout(pTree.data);
        }
    }   
  

二叉树反转（对每一个父结点交换其左右子结点）

      reverse(BTree pTree){
          if (pTree){
              swap(pTree.lChild,pTree.rChild);
              reverse(pTree.lChild);
              reverse(pTree.rChild);
          }
          return pTree;
      }

二叉树相关算法