[关闭]
@snail-lb 2017-02-28T23:17:28.000000Z 字数 12095 阅读 786

经常查询的代码

代码

一、二叉树

  1. package com.cn;
  3. import java.lang.reflect.Array;
  4. import java.util.ArrayList;
  5. import java.util.List;
  7. public class BinaryTree<E> {
  8.     /** 根节点 **/
  9.     Node<E> rootNode;
  10.     /** 树深度 **/
  11.     int depth;
  13.     class Node<E> {
  14.         /** 节点数据 **/
  15.         E date;
  16.         /** 左子树 **/
  17.         Node<E> left;
  18.         /** 右子树 **/
  19.         Node<E> right;
  21.         Node(E date) {
  22.             this.date = date;
  23.             this.left = null;
  24.             this.right = null;
  25.         }
  27.         Node(E date, Node<E> left, Node<E> right) {
  28.             this.date = date;
  29.             this.left = left;
  30.             this.right = right;
  31.         }
  32.     }
  34.     public BinaryTree() {
  35.     }
  37.     /**
  38.      * 使用数组构造一个完全二叉树
  39.      * 
  40.      * @param o
  41.      */
  42.     public BinaryTree(E[] o) {
  43.         this();
  44.         Node<E> root = null;
  45.         this.rootNode = createFullBinaryTree(root, o, 0);
  46.     }
  48.     /**
  49.      * 创建满二叉树函数
  50.      * 
  51.      * @param root
  52.      * @param o
  53.      * @param index
  54.      * @return
  55.      */
  56.     private Node<E> createFullBinaryTree(Node<E> root, E[] o, int index) {
  57.         if (index >= o.length) {
  58.             return null;
  59.         }
  60.         root =  new Node<E>(o[index]);
  61.         // 数组是从0开始的，所以左节点的序号为父节点的两倍多一个，右节点为父节点的两倍多两个
  62.         root.left = createFullBinaryTree(root.left, o, 2 * index + 1);
  63.         root.right = createFullBinaryTree(root.right, o, 2 * index + 2);
  64.         return root;
  65.     }
  67.     /**
  68.      * 前序遍历输出数组
  69.      * 
  70.      * @return E[]
  71.      */
  72.     public E[] preorderTraversal(Node<E> node) {
  73.         List<E> list = new ArrayList<E>();
  74.         preorderTraversalRealize(node,list);
  75.         @SuppressWarnings("unchecked")
  76.         E[] e = (E[])Array.newInstance(node.date.getClass(), 0);//使用泛型数组进行记录
  77.         return list.toArray(e);
  78.     }
  80.     /**
  81.      * 前序遍历输出实现
  82.      * 
  83.      * @param node
  84.      */
  85.     private void preorderTraversalRealize(Node<E> node,List<E> list) {
  86.         if (node != null) {
  87.             list.add(node.date);
  88.             preorderTraversalRealize(node.left,list);
  89.             preorderTraversalRealize(node.right,list);
  90.         }
  91.     }
  93.     /**
  94.      * 前序遍历输出数组(非递归实现)
  95.      * 
  96.      * @return E[]
  97.      */
  98.     public E[] preorderTraversalNoRecursion(Node<E> node) {
  99.         if(node == null)
  100.             return null;
  101.         @SuppressWarnings("unchecked")
  102.         E[] e = (E[])Array.newInstance(node.date.getClass(), 0);//使用泛型数组进行记录
  103.         Stack<Node<E>> stack = new Stack<Node<E>>();
  104.         List<E> list = new ArrayList<E>();
  105.         stack.push(node);
  106.         while(!stack.empty()){
  107.             node = stack.pop();
  108.             list.add(node.date);
  109.             if(node.right != null){
  110.                 stack.push(node.right);
  111.             }
  112.             if(node.left != null){
  113.                 stack.push(node.left);
  114.             }
  115.         }
  116.         return list.toArray(e);
  117.     }
  120.     /**
  121.      * 中序遍历输出数组
  122.      * 
  123.      * @return E[]
  124.      */
  125.     public E[] inorderTraversal(Node<E> node) {
  126.         List<E> list = new ArrayList<E>();
  127.         inorderTraversalRealize(node,list);
  128.         @SuppressWarnings("unchecked")
  129.         E[] e = (E[])Array.newInstance(node.date.getClass(), 0);//使用泛型数组进行记录
  130.         return list.toArray(e);
  131.     }
  133.     /**
  134.      * 中序遍历输出实现
  135.      * 
  136.      * @param node
  137.      */
  138.     private void inorderTraversalRealize(Node<E> node,List<E> list) {
  139.         if (node != null) {
  140.             inorderTraversalRealize(node.left,list);
  141.             list.add(node.date);
  142.             inorderTraversalRealize(node.right,list);
  143.         }
  144.     }
  146.     /**
  147.      * 中序遍历输出，非递归实现
  148.      * @return
  149.      */
  150.     public E[] inorderTraversalNoRecursion(Node<E> node){
  151.         if(node == null)
  152.             return null;
  153.         @SuppressWarnings("unchecked")
  154.         E[] e = (E[])Array.newInstance(node.date.getClass(), 0);//使用泛型数组进行记录
  155.         Stack<Node<E>> stack = new Stack<Node<E>>();
  156.         List<E> list = new ArrayList<E>();
  157.         while(node != null || !stack.empty()){
  158.             //存在左子树时
  159.             while(node != null){
  160.                 stack.push(node);
  161.                 node = node.left;
  162.             }
  163.             //栈非空时
  164.             if(!stack.empty()){
  165.                 node = stack.pop();
  166.                 list.add(node.date);
  167.                 node = node.right;
  168.             }
  169.         }
  170.         return list.toArray(e);
  171.     }
  173.     /**
  174.      * 后序遍历输出数组
  175.      * 
  176.      * @return E[]
  177.      */
  178.     public E[] postorderTraversal(Node<E> node) {
  179.         List<E> list = new ArrayList<E>();
  180.         postorderTraversalRealize(node,list);
  181.         @SuppressWarnings("unchecked")
  182.         E[] e = (E[])Array.newInstance(node.date.getClass(), 0);//使用泛型数组进行记录
  183.         return list.toArray(e);
  184.     }
  186.     /**
  187.      * 后序遍历输出实现
  188.      * 
  189.      * @param node
  190.      */
  191.     private void postorderTraversalRealize(Node<E> node,List<E> list) {
  192.         if (node != null) {
  193.             postorderTraversalRealize(node.left,list);
  194.             postorderTraversalRealize(node.right,list);
  195.             list.add(node.date);
  196.         }
  197.     }
  199.     /**
  200.      * 后续遍历（非递归输出）
  201.      * @param node
  202.      * @return
  203.      */
  204.     public E[] postorderTraversalNoRecursion(Node<E> node){
  205.         if(node == null)
  206.             return null;
  207.         @SuppressWarnings("unchecked")
  208.         E[] e = (E[])Array.newInstance(node.date.getClass(), 0);//使用泛型数组进行记录
  209.         Stack<Node<E>> stack = new Stack<Node<E>>();
  210.         List<E> list = new ArrayList<E>();
  211.         Node<E> prv = node; //记录之前遍历的右结点  
  212.         while(node != null || !stack.empty()){
  213.             //存在左子树时
  214.             while(node != null){
  215.                 stack.push(node);
  216.                 node = node.left;
  217.             }
  218.             //栈非空时
  219.             if(!stack.empty()){
  220.                 Node<E> nodeRight = stack.peek().right;
  221.                 /*如果右结点为空，或者右结点之前遍历过，获取根结点数据*/  
  222.                 if(nodeRight == null || nodeRight == prv ){
  223.                     node = stack.pop();
  224.                     list.add(node.date);
  225.                     prv = node;
  226.                     node = null;
  227.                 }else{
  228.                     node = nodeRight;
  229.                 }
  230.             }
  231.         }
  232.         return list.toArray(e);
  233.     }
  235.     /**
  236.      * 广度优先搜索(分层遍历二叉树): 使用队列实现。队列初始化，将根节点压入队列。当队列不为空，
  237.      * 进行如下操作：弹出一个节点，访问，若左子节点或右子节点不为空，将其压入队列。
  238.      * 
  239.      * @param node
  240.      * @return
  241.      */
  242.     public E[] layerTraversing(Node<E> node) {
  243.         List<E> list = new ArrayList<E>();
  244.         layerTraversingRealize(node, list);
  245.         @SuppressWarnings("unchecked")
  246.         E[] e = (E[])Array.newInstance(node.date.getClass(), 0);//使用泛型数组进行记录
  247.         return list.toArray(e);
  248.     }
  249.     /**
  250.      * 分层遍历辅助函数
  251.      * @param node
  252.      * @param list
  253.      */
  254.     private void layerTraversingRealize(Node<E> node, List<E> list) {
  255.         Queue<Node<E>> queue = new Queue<Node<E>>();
  256.         queue.add(node);
  257.         while (!queue.empty()) {
  258.             Node<E> n = queue.poll();
  259.             list.add(n.date);
  260.             if (n.left != null) {
  261.                 queue.add(n.left);
  262.             }
  263.             if (n.right != null) {
  264.                 queue.add(n.right);
  265.             }
  266.         }
  267.     }
  269.     /**
  270.      * 使用深度优先搜索遍历二叉树,这个结果和前序遍历是一样的
  271.      * 
  272.      * @param node
  273.      * @return
  274.      */
  275.     public E[] depthTraversing(Node<E> node) {
  276.         List<E> list = new ArrayList<E>();
  277.         depthTraversingRealize(node, list);
  278.         @SuppressWarnings("unchecked")
  279.         E[] e = (E[])Array.newInstance(node.date.getClass(), 0);//使用泛型数组进行记录
  280.         return list.toArray(e);
  281.     }
  283.     private void depthTraversingRealize(Node<E> node, List<E> list) {
  284.         if (node != null) {
  285.             list.add(node.date);
  286.             depthTraversingRealize(node.left, list);
  287.             depthTraversingRealize(node.right, list);
  288.         }
  289.     }
  291.     /**
  292.      * 计算二叉树节点的个数
  293.      * 
  294.      * @param node
  295.      * @return 二叉树节点的个数
  296.      */
  297.     public int getNodeNumber(Node<E> node) {
  298.         if (node == null) {
  299.             return 0;
  300.         }
  301.         return getNodeNumber(node.left) + getNodeNumber(node.right) + 1;
  302.     }
  304.     /**
  305.      * 求二叉树深度
  306.      * 
  307.      * @return 二叉树深度
  308.      */
  309.     public int getDepth(Node<E> node) {
  310.         if (node == null) {
  311.             return 0;
  312.         }
  313.         int leftDepth = getDepth(node.left);
  314.         int rightDepth = getDepth(node.right);
  315.         return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
  316.     }
  318.     /**
  319.      * 求二叉树第K层的节点个数 递归解法： （1）如果二叉树为空或者k<1返回0 （2）如果二叉树不为空并且k==1，返回1
  320.      * （3）如果二叉树不为空且k>1，返回左子树中k-1层的节点个数与右子树k-1层节点个数之和
  321.      * 
  322.      * @param k
  323.      * @return 二叉树第K层的节点个数
  324.      */
  325.     public int getNodeNumberInLay(Node<E> node, int k) {
  326.         if (node == null || k < 1) {
  327.             return 0;
  328.         }
  329.         if (k == 1) {
  330.             return 1;
  331.         }
  332.         int leftNodeNum = getNodeNumberInLay(node.left, k - 1);
  333.         int rightNodeNum = getNodeNumberInLay(node.right, k - 1);
  334.         return leftNodeNum + rightNodeNum;
  335.     }
  337.     /**
  338.      * 求二叉树中叶子节点的个数
  339.      * 
  340.      * @param node
  341.      * @return
  342.      */
  343.     public int getNodeNumberLeaf(Node<E> node) {
  344.         if (node == null) {
  345.             return 0;
  346.         }
  347.         if (node.left == null && node.right == null) {
  348.             return 1;
  349.         }
  350.         int leftNodeNum = getNodeNumberLeaf(node.left);
  351.         int rightNodeNum = getNodeNumberLeaf(node.right);
  352.         return leftNodeNum + rightNodeNum;
  353.     }
  355.     /**
  356.      * 判断两棵二叉树是否结构相同 不考虑数据内容。结构相同意味着对应的左子树和对应的右子树都结构相同。 递归解法： （1）如果两棵二叉树都为空，返回真
  357.      * （2）如果两棵二叉树一棵为空，另一棵不为空，返回假 （3）如果两棵二叉树都不为空，如果对应的左子树和右子树都同构返回真，其他返回假
  358.      * 
  359.      * @param node1
  360.      * @param node2
  361.      * @return
  362.      */
  363.     public boolean isStructureCmp(Node<E> node1, Node<E> node2) {
  364.         if (node1 == null && node2 == null) {
  365.             return true;
  366.         } else if (node1 == null || node2 == null) {
  367.             return false;
  368.         } else {
  369.             boolean leftCmp = isStructureCmp(node1.left, node2.left);
  370.             boolean rightCmp = isStructureCmp(node1.right, node2.right);
  371.             return leftCmp && rightCmp;
  372.         }
  373.     }
  375.     /**
  376.      * 判断是否是平衡二叉树
  377.      * 
  378.      * @param node
  379.      * @return
  380.      */
  381.     public boolean isAVL(Node<E> node) {
  382.         if (node == null) {
  383.             return true;
  384.         }
  385.         int leftHeight = getDepth(node.left);
  386.         int rightHeight = getDepth(node.right);
  387.         if (Math.abs(leftHeight - rightHeight) > 1) {
  388.             return false;
  389.         } else {
  390.             return isAVL(node.left) && isAVL(node.right);
  391.         }
  392.     }
  394.     /**
  395.      * 判断是否完全二叉树 1.当发现有一个节点的左子树为空，右子树不为空时 直接返回false.
  396.      * 2.当发现有一个节点的左子树不为空，右子树为空时，置标志位为1。 3.当发现有一个节点的左右子树均为空时，置标志位为1。
  397.      * 
  398.      * @param node
  399.      * @return
  400.      */
  401.     public boolean isCompleteBinaryTree(Node<E> node) {
  402.         if (node == null) {
  403.             return true;
  404.         }
  405.         Queue<Node<E>> queue = new Queue<Node<E>>();
  406.         queue.add(node);
  407.         int flag = 0;// 标记此节点以下的节点均应为叶子节点（没有左右孩子），否则此树为一棵非完全二叉树。
  408.         while (!queue.empty()) {
  409.             Node<E> n = queue.poll();
  410.             if (n.left != null) {
  411.                 if (flag == 1) {
  412.                     return false;
  413.                 }
  414.                 queue.add(n.left);
  415.                 if (n.right != null) {
  416.                     queue.add(n.right);
  417.                 } else {
  418.                     flag = 1;
  419.                 }
  420.             } else {
  421.                 if (n.right != null) {
  422.                     return false;
  423.                 }
  424.                 flag = 1;
  425.             }
  426.         }
  427.         return true;
  428.     }
  430.     /**
  431.      * 根据前序遍历结果和中序遍历结果重建二叉树
  432.      * 
  433.      * @param preorderTraversalArray
  434.      *            前序遍历结果
  435.      * @param inorderTraversalArray
  436.      *            中序便利结果
  437.      * @return 二叉树
  438.      */
  439.     public BinaryTree<E> reBuildBinaryTree(E[] preorderTraversalArray, E[] inorderTraversalArray) {
  440.         if (preorderTraversalArray == null || inorderTraversalArray == null) {
  441.             return null;
  442.         }
  443.         Node<E> root = reBuildBinaryTreeRealize(preorderTraversalArray, 0, preorderTraversalArray.length - 1,
  444.                 inorderTraversalArray, 0, inorderTraversalArray.length - 1);
  445.         BinaryTree<E> bt = new BinaryTree<E>();
  446.         bt.rootNode = root;
  447.         bt.depth = getDepth(root);
  448.         return bt;
  449.     }
  450.     /**
  451.      *  前序遍历的第一个节点一定是二叉树的根节点（以a记录），中序遍历以a为分界线，a左边的一定是左子树一边的（记录下左边的个数为x），且为左子树的中序遍历结果，
  452.      * a右边的一定是右子树一边的（记录下右边的个数为y），且为右子树中序遍历的结果。再把前序遍历结果a后面x个数作为左子树的前序遍历，剩下的y个作为右子树的前序遍历，
  453.      * 再一次进行递归建立，直到完全建立二叉树
  454.      * 
  455.      * @param preOrder 前序遍历
  456.      * @param startPreIndex 前序遍历起始位置
  457.      * @param endPreIndex 前序遍历结束为止
  458.      * @param inOrder   后序遍历
  459.      * @param startInIndex  后续遍历起始位置
  460.      * @param endInIndex 后序遍历结束位置
  461.      * @return
  462.      */
  463.     public Node<E> reBuildBinaryTreeRealize(E[] preOrder, int startPreIndex, int endPreIndex, E[] inOrder,
  464.             int startInIndex, int endInIndex) {
  466.         Node<E> root = new Node<E>(preOrder[startPreIndex]);
  467.         // 只有一个元素
  468.         if (startPreIndex == endPreIndex) {
  469.             if (startInIndex == endInIndex && preOrder[startPreIndex] == inOrder[startInIndex]) {
  470.                 return root;
  471.             } else {
  472.                 throw new RuntimeException("出错");
  473.             }
  474.         }
  476.         // 在中序遍历中找到根结点的索引
  477.         int rootInIndex = startInIndex;
  479.         while (rootInIndex <= endInIndex && inOrder[rootInIndex] != preOrder[startPreIndex]) {
  480.             ++rootInIndex;
  481.         }
  483.         if (rootInIndex == endInIndex && inOrder[rootInIndex] != preOrder[startPreIndex]) {
  484.             throw new RuntimeException("出错");
  485.         }
  487.         int leftLength = rootInIndex - startInIndex;
  489.         int leftPreOrderEndIndex = startPreIndex + leftLength;
  491.         if (leftLength > 0) {
  492.             // 构建左子树
  493.             root.left = reBuildBinaryTreeRealize(preOrder, startPreIndex + 1, leftPreOrderEndIndex, inOrder, startInIndex,
  494.                     rootInIndex - 1);
  495.         }
  497.         if (leftLength < endPreIndex - startPreIndex) {
  498.             // 右子树有元素,构建右子树
  499.             root.right = reBuildBinaryTreeRealize(preOrder, leftPreOrderEndIndex + 1, endPreIndex, inOrder, rootInIndex + 1,
  500.                     endInIndex);
  501.         }
  502.         return root;
  503.     }
  504. }

二、排序

  1. package com.cn;
  3. import java.util.Arrays;
  5. /**
  6.  * 经典排序复习
  7.  * @author lvbiao
  8.  *
  9.  */
  10. public class Sort {
  13.     /**
  14.      * 交换数组中两个指定位置的数据
  15.      * @param array
  16.      * @param i
  17.      * @param j
  18.      */
  19.     private void swap(int[] array, int i, int j) {
  20.         int var;
  21.         var = array[i];
  22.         array[i] = array[j];
  23.         array[j] = var;
  24.     }
  26.     public void display(int[] array){
  27.         System.out.println(Arrays.toString(array));
  28.     }
  30.     /**
  31.      * 冒泡排序
  32.      * @param array
  33.      */
  34.     public void bubbleSort(int[] array){
  35.         for(int i = 0; i < array.length; i++){
  36.             for(int j = array.length-1; j > i; j--){
  37.                 if(array[j-1] > array[j]){
  38.                     swap(array,j-1,j);
  39.                 }
  40.             }
  41.         }
  42.     }
  44.     /**
  45.      * 选择排序
  46.      * @param array
  47.      */
  48.     public void selectSort(int[] array){
  49.         int min;
  50.         for(int i = 0; i < array.length; i++){
  51.             min = i;
  52.             for(int j = i+1; j < array.length; j++){
  53.                 if(array[min] > array[j]){
  54.                     min = j;
  55.                 }
  56.             }
  57.             if(min != i){
  58.                 swap(array, i, min);
  59.             }
  60.         }
  61.     }
  63.     /**
  64.      * 插入排序
  65.      * @param array
  66.      */
  67.     public void insertSort(int[] array){
  68.         int j;
  69.         for(int i = 1; i < array.length; i ++){
  70.             if(array[i] < array[i-1]){
  71.                 int var = array[i];
  72.                 j = i - 1;
  73.                 while(j >= 0 && var < array[j]){
  74.                     array[j+1] = array[j];
  75.                     j--;
  76.                 }
  77.                 array[j+1] = var;
  78.             }
  79.         }
  80.     }
  82.     /**
  83.      * 希尔排序
  84.      * @param array
  85.      */
  86.     public void shellSort(int[] array){
  87.         int length = array.length;
  88.         int j;
  89.         do{
  90.             length = length/3 + 1;
  91.             for(int i = length; i < array.length; i ++){
  92.                 if(array[i] < array[i-length]){
  93.                     int var = array[i];
  94.                     j = i -length;
  95.                     while(j >= 0 && var < array[j]){
  96.                         array[j+length] = array[j];
  97.                         j-=length;
  98.                     }
  99.                     array[j+length] = var;
  100.                 }
  101.             }
  102.         }while(length > 1);
  103.     }
  106.     /**
  107.      * 推排序
  108.      * @param array
  109.      */
  110.     public void headSort(int[] array){
  111.         //将整个数组构建成一个大顶堆
  112.         for(int i = (array.length-1)/2; i >= 0; i--){
  113.             headBig(array,i,array.length-1);
  114.         }
  115.         //将大顶堆树根上的数据与数组末尾的交换，再将数组除开最后一个再构成一个大顶堆，一次循环知道完成排序
  116.         for(int i = array.length-1; i > 0; i--){
  117.             swap(array,0,i);
  118.             headBig(array,0,i-1);
  119.         }
  120.     }
  122.     /**
  123.      * 将array调整为一个大顶堆
  124.      * @param array
  125.      * @param i
  126.      * @param j
  127.      */
  128.     private void headBig(int[] array, int start, int stop) {
  129.         int i;
  130.         int var = array[start];
  131.         for(i = 2*start; i <= stop; i*=2){
  132.             if(i+1 >= array.length){
  133.                 if(array[i/2] < array[i]){
  134.                     array[i/2] = array[i];
  135.                     start = i;
  136.                     break;
  137.                 }else{
  138.                     break;
  139.                 }
  140.             }
  141.             if(array[i] < array[i+1] && i < stop){
  142.                 ++i;
  143.             }
  144.             if(var >= array[i]){
  145.                 break;
  146.             }
  147.             array[start] = array[i];
  148.             start = i;
  149.         }
  150.         array[start] = var;
  151.     }
  153.     /**
  154.      * 归并排序
  155.      * @param array
  156.      */
  157.     public void mergeSort(int[] array){
  158.         int[] temp = new int[array.length];
  159.         mSort(array, temp, 0, array.length-1);
  161.     }
  162.     //msort函数是将list数组进行分割，merge函数是将分割后的list数组进行排序在组合
  163.     private void mSort(int[] list, int[] temp, int left, int right){
  164.         if(left  == right){
  165.             return;   
  166.         }else{
  167.             int mid = (left + right) / 2;
  168.             mSort(list,temp,left,mid);
  169.             mSort(list,temp,mid+1,right);
  170.             merge(list,temp,left,mid+1,right);
  171.         }
  172.     }
  173.     private void merge(int[] list,int[] temp,int left,int mid,int right){
  174.         int j = 0;
  175.         int leftTemp = left;
  176.         int midTemp = mid - 1;
  177.         int n = right - left + 1;  //当前temp数组中数的个数
  178.         //左右数组第一个数进行比较  把较小的数如到temp数组中
  179.         while(left <= midTemp &&  mid <= right){   
  180.             if(list[left] < list[mid]){
  181.                 temp[j++] = list[left++];
  182.             }else{
  183.                 temp[j++] = list[mid++];
  184.             }
  185.         }
  186.         //如果左边的数比右边的数多，就将剩下的入到temp数组中    j
  187.         while(left <= midTemp){    
  188.             temp[j++] = list[left++];
  189.         }
  190.         //如果右边打数比左边的数多，就将右边剩下的数加入到temp数组当中去
  191.         while(mid <= right){    
  192.             temp[j++] = list[mid++];
  193.         }
  194.         //将得到的temp数组加到list数组中    
  195.         for(j = 0; j < n; j++){ 
  196.             list[leftTemp+j] = temp[j];
  197.         }         
  198.     }
  201.     /**
  202.      * 快速排序
  203.      * @param array
  204.      */
  205.     public void quickSort(int[] array){
  206.         qSort(array, 0, array.length-1);
  207.     }
  208.     private void qSort(int[] array, int left, int right) {
  209.         if(left < right){
  210.             int mid = partition(array, left, right);
  211.             qSort(array, left, mid-1);
  212.             qSort(array, mid+1, right);
  213.         }
  214.     }
  215.     //返回一个关键字，使得这个关键字左边的数都比他小，右边的数都比它大
  216.     private int partition(int[] array, int left, int right) {
  217.         int result =  array[left];
  218.         while(left < right){
  219.             while(left < right && array[right] >= result){
  220.                 right--;
  221.             }
  222.             swap(array, left, right);
  223.             while(left < right && array[left] <= result){
  224.                 left++;
  225.             }
  226.             swap(array, left, right);
  227.         }
  228.         array[left] = result;
  229.         return left;
  230.     }
  231. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注