排序算法

• 冒泡：由后往前每兩個數(shù)對比各拷，逆序則交換严蓖，否則不動寞钥。

    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)
  • 優(yōu)化：若未循環(huán)完成便排好序：設(shè)置flag土铺，若發(fā)生交換則繼續(xù)下一輪比較出刷，否則停止

• 選擇排序：遍歷后[length-i]個數(shù)找出最小值與與第i 個數(shù)交換

  • o(n*n)

• 插入排序：由前往后，每輪將第i+1個數(shù)與前i個數(shù)對比姨裸，找到其在前i+1個數(shù)中的位置

    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)秧倾，交換次數(shù)與數(shù)組初始順序有關(guān)
  • 改進(jìn)方法：比較后將較大元素右移

• 希爾排序：快速的插入排序，將數(shù)組按一定間隔（>N/3）分為若干組傀缩，每組內(nèi)進(jìn)行插入排序那先，適用于中等大小數(shù)組

    int temp;
    int space = length
    while(space>1){
        space=space/2;
        for(int k=0;k<space;k++){//分組
            //每組內(nèi)對比循環(huán)
            for(int i=k+space;i<length;i+=space){
                for(int j=i;j>k;j-=space){
                    if(a[j]<a[j-space]){//交換}
                }
            }
        }   
    }
  

• 歸并排序：將數(shù)組一分為二，分別進(jìn)行排序赡艰，然后將結(jié)果合并至第三個數(shù)組售淡，比較兩組第一個值，并取最小值為新數(shù)組第一位瞄摊，并刪去原數(shù)組中被取的值勋又，然后繼續(xù)比較原數(shù)組第一位并取小值放入新數(shù)組。實際中首先分為一個數(shù)為一組换帜，進(jìn)行兩兩合并直到合并為一個數(shù)組。

  • o(NlogN)
  • 原地歸并：

• 快速排序：數(shù)組中取第一個數(shù)作為key值鹤啡，將比其小的方左邊惯驼，大的放右邊；再在左右兩子數(shù)組中隨機(jī)選key值重復(fù)排列，直到各區(qū)間只有一個數(shù)

    public static void quickSort(int a[],int l;int r){
        if(l>=r) return;//左右數(shù)組起始位置相同祟牲，即每段只有一個數(shù)時打破遞歸
        
        int i=l;int j=r;int key=a[l];
        while(i<j){
            while((a[i] <= key)?true:false)
        }
    }
  

  • 改進(jìn)：
    • 在小數(shù)組中效率不如插入排序隙畜，可以在數(shù)組到達(dá)較小值時不再進(jìn)行下一步迭代，然后改用插入排序
    • 自數(shù)組中部分元素中位數(shù)切分?jǐn)?shù)組

隊列说贝、棧

• 棧：（棧頂）后進(jìn)先出议惰，可用數(shù)組或鏈表表示
  • 順序棧：地址連續(xù)的存儲單元依次存放自棧底到棧頂頂元素，并設(shè)置top指針指向棧頂?shù)奈恢茫╰op.next 為棧頂元素）,base指針指向棧底（a[length-1]）乡恕。初始分配基本容量言询，空間不足時再擴(kuò)大
  • 鏈表棧：棧頂元素作為第一個結(jié)點，棧底元素作為最后一個結(jié)點
• 隊：先進(jìn)（隊尾）先出（隊頭）傲宜，只允許在隊尾添加隊頭刪除运杭，數(shù)組或鏈表表示
  • 鏈隊列：頭指針->頭結(jié)點->隊列結(jié)點<-尾指針，隊為空時頭尾指針均指向頭結(jié)點
  • 順序隊列：地址連續(xù)的存儲單元依次存放隊頭到隊尾的元素函卒。初始時pfront->a[0],prear->a[0]辆憔。插入時pfront地址加一
  • 雙端隊列：兩頭都可以添加刪除

數(shù)組、鏈表

• 數(shù)組：一塊連續(xù)空間保存數(shù)據(jù)报嵌，分配內(nèi)存時大小固定
  • 根據(jù)下標(biāo)訪問o(1),查找指定數(shù)據(jù)o(n)虱咧，插入或刪除任意位置元素，其后元素都要移動
• 鏈表：不連續(xù)的內(nèi)存單元中保存數(shù)據(jù)(data與指針next)锚国，大小不固定腕巡。頭指針->（頭結(jié)點->）結(jié)點->null
  • 訪問第i個元素與查找指定數(shù)據(jù)o(n)，插入刪除o(1)
  • 雙向鏈表：插入與刪除
  • 循環(huán)列表：最后一個元素指針指向頭結(jié)點而不是null跷叉，遍歷條件為元素指針是否等于頭指針
  • 雙向循環(huán)鏈表
  • 靜態(tài)列表：數(shù)組加指針逸雹，由指針指明該數(shù)組元素在鏈表中的結(jié)點位置
  • 翻轉(zhuǎn)：

    • 迭代：保證臨時指針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;//頭結(jié)點指向第一個結(jié)點云挟，可以包含鏈表附加信息
        while(cur != null){
            p = cur.next();
            cur.next = pre;
            pre = cur;
            cur = p;
        }
        head.next = pre;
      

    • 遞歸：遞歸找到最后一個結(jié)點梆砸，反回上一層遞歸，改變翻轉(zhuǎn)下一結(jié)點指針园欣，并將當(dāng)前結(jié)點指向null帖世，然后返回新的頭結(jié)點，保存其在遞歸中不變

        reverse(Node H){
            //鏈表為空或H到達(dá)尾結(jié)點
            if(H==null||H.next==null) return H;
            Node NewHead = reverse(H.next);//遞歸到鏈尾
            H.next.next = H;//到達(dá)鏈尾返回上一層遞歸中
            H.next = null;
            return NewHead;//遞歸中保持新的第一個結(jié)點不變
        }
      

    • 合并:有序鏈表La,Lb鏈表合并到Lc沸枯，借助3個指針分別指向La日矫、Lb頭結(jié)點和Lc尾結(jié)點

      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;//插入剩余鏈表
      }

堆排序:

• 無序組排為小頂堆／大頂堆：

  • 從最后一個尾結(jié)點（arr.length-1）對應(yīng)的非葉結(jié)點（i=arr.length/2-1）開始，對比該非葉結(jié)點與其子樹大小并交換

      for(k=i*2+1;k<length;k=k*2+1){ //每層左右子節(jié)點遍歷完后再便利子節(jié)點的子樹
          //左右子節(jié)點中最大值交換
          if(k+1<length && a[k]<a[k+1]){
              k++; //移到右子節(jié)點
          }
          if(a[k]>a[i]){
              //交換
          }else{break;}               
      }   
    

• 將堆頂元素（arr[0]）與堆尾元素（arr[length-1]）交換绑榴，移出堆尾最值哪轿，并重新排列a[0]到a[length-2]的堆
• 選擇排序，時間復(fù)雜度o(nlogn),空間復(fù)雜度o(1)

廣義表：線性表（數(shù)組翔怎、鏈表）的推廣窃诉，結(jié)點可以時元素或廣義表

查找

• 二分查找：有序表中杨耙，取中間的記錄作為比較關(guān)鍵字，若給定值與中間記錄的關(guān)鍵字相等飘痛，則查找成功珊膜；若給定的值小于中間記錄的關(guān)鍵字，則在中間記錄的左半?yún)^(qū)間繼續(xù)查找宣脉；若給定值大于中間記錄的關(guān)鍵字车柠，則在中間記錄的右半?yún)^(qū)間繼續(xù)查找；不斷重復(fù)這個過程塑猖，直到查找成功竹祷。否則查找失敗。最好o(1)萌庆，最壞o(logn)
• 差值查找
• 順序查找：遍歷o(n)
• 二叉樹查找：左分支小于右分支數(shù)據(jù)
• 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);
        }
    }   
  

二叉樹反轉(zhuǎn)（對每一個父結(jié)點交換其左右子結(jié)點）

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

二叉樹相關(guān)算法