算法（二）

1、给定一个数组，调整该数组，使其满足堆的性质(初始化建堆)。

//构建大根堆：将array看成完全二叉树的顺序存储结构

private int[] buildMaxHeap(int[] array){

//从最后一个节点array.length-1的父节点（array.length-1-1）/2开始，直到根节点0，反复调整堆

for(int i=array.length-2; i>=0; i--){

adjustDownToUp(array, i , array.length);

}

return array;

}

private void adjustDownToUp(int[] array, int k, int length){      

//将元素array[k]自下往上逐步调整树形结构

private void adjustDownToUp(int[] array,int k,int length){

int temp = array[k];   

for(int i=2*k+1; i<length-1; i=2*i+1){    

//i为初始化为节点k的左孩子，沿节点较大的子节点向下调整

     if(i<length && array[i]<array[i+1]){  //取节点较大的子节点的下标

     i++;   //如果节点的右孩子>左孩子，则取右孩子节点的下标

     }

     if(temp>=array[i]){  //根节点 >=左右子女中关键字较大者，调整结束

         break;

     }else{   //根节点 <左右子女中关键字较大者

         array[k] = array[i];  //将左右子结点中较大值array[i]调整到双亲节点上

            k = i; //【关键】修改k值，以便继续向下调整

     }

    }

    array[k] = temp;  //被调整的结点的值放人最终位置

}    

#堆排序

public int[] heapSort(int[] array){

array = buildMaxHeap(array); //初始建堆，array[0]为第一趟值最大的元素

    for(int i=array.length-1;i>1;i--){  

     int temp = array[0];  //将堆顶元素和堆低元素交换，即得到当前最大元素正确的排序位置

        array[0] = array[i];

        array[i] = temp;

        adjustDownToUp(array, 0,i);  //整理，将剩余的元素整理成堆

     }

     return array;

}

2、给定n个单词，如果单词组成一致但是元素顺序不一致，该对单词为同位词，例如：abc,bca为同位词．求所有同位词的集合输出。

public static ArrayList<ArrayList<String>> Print(String[] rs , int n){     

        ArrayList<ArrayList<String>> arrayListAllWords = new ArrayList<>();

        int length = rs.length;

        for(int i = 0 ; i < n-1 ; i++){

                ArrayList<String> arrayListWord = new ArrayList<>();

                //字符串转成字符串数组

               String[] str_arr1 = stringToArray(rs[i]);

               //把字符串数组排序

               new_str_arr1 = Arrays.sort(str_arr1);

              //把排序好的字符串数组转成字符串

             String f_new_str_arr1 = ArrayToString(new_str_arr1);

            boolean flag = false;

            for(j=i+1; j<n; j++){

                      //字符串转成字符串数组

                      String[] str_arr2 = stringToArray(rs[j]);

                      //把字符串数组排序

                     new_str_arr2 = Arrays.sort(str_arr2);

                     //把排序好的字符串数组转成字符串

                     String f_new_str_arr2 = ArrayToString(new_str_arr2);

                     //判断字符串是否相等

                     if(f_new_str_arr1.equals(f_new_str_arr2)){

                               arrayListWord .add(rs[j]);

                               flag = true;

                     }  

          }

         if(flag){

                  arrayListWord .add(rs[i]);   

          }

          arrayListAllWords.add(arrayListWord);

  }    

  return arrayListAllWords;

}

public static String ArrayToString(int[] int_sort) {

        // TODO Auto-generated method stub

        StringBuilder stringBuilder = new StringBuilder();

        for (int i = 0; i < int_sort.length; i++) {

            if (i==int_sort.length-1) {

                stringBuilder.append(int_sort[i]);

            }else {

                stringBuilder.append(int_sort[i]).append(CONDITION);

            }

        }

        return stringBuilder.toString();

    }