java完成12种排序算法_玖富娱乐主管发布


玖富娱乐是一家为代理招商,直属主管信息发布为主的资讯网站,同时也兼顾玖富娱乐代理注册登录地址。

Java完成的12种排序

2019-01-05

 

 

 

一.冒泡排序及其完成

二.希尔排序及其完成

三.插进去排序及其完成

四.插进去排序及其完成

五.疾速排序及其完成

六.兼并排序及其完成

七.计数排序及其完成

八.基数排序及其完成

九.   桶排序及其完成

 十.    堆排序及其完成

   十一.二叉树排序及有序鸠合

         十二.应用鸠合的4种排序排序体式格局

 

 

一.冒泡排序及其完成

一.home→包

BubbleSort→类

           main→主函数

                      bubbleSort1()→冒泡排序1

                      bubbleSort2()→冒泡排序优化1

                      bubbleSort3()→冒泡排序优化2

 1 package home;
 2 import java.util.Arrays;
 3 
 4 /**
 5  * 冒泡排序的三种写法
 6  * @author Stringer123
 7  * @version 1.0
 8  * 
 9  */
10 public class BubbleSort {
11     
12     public static void main(String[] args) {
13         // TODO Auto-generated method stub
14         int[] arr = { 1, 1, 2, 0, 9, 3, 12, 7, 8, 3, 4, 65, 22 };
15         // int[] b1 = bubbleSort1(arr);
16         // int[] b1 = bubbleSort2(arr);
17         int[] b1 = bubbleSort3(arr);
18 
19         // 遍历体式格局1:java 8新特征(应用Lambda表达式)→经由过程转成流输出数组
20         Arrays.stream(b1).forEach(item -> {
21             System.out.print(item   " ");
22         });
23         System.out.println();
24 
25         // 遍历体式格局2:经由过程传统for轮回遍历
26         for (int i = 0; i < b1.length; i  ) {
27             System.out.print(b1[i]   " ");
28         }
29         System.out.println();
30 
31         // 遍历体式格局3:经由过程增强for轮回遍历(也成for-each轮回)
32         for (int i : b1) {
33             System.out.print(i   " ");
34         }
35         System.out.println();
36 }

(1) 冒泡排序的第一种完成,没有任何优化

private static int[] bubbleSort1(int[] a) {
        System.out.println("bubbleSort1的排序效果:");
        int i, j;
        int n = a.length;
        for (i = 0; i < n; i  ) {
            for (j = 1; j < n - i; j  ) { // 前面的数字大于背面的数字就交流
                if (a[j - 1] > a[j]) { // 交流a[j-1]和a[j]
                    int temp;
                    temp = a[j - 1];
                    a[j - 1] = a[j];
                    a[j] = temp;
                }
            }
        }
        return a;
    }

(2) 冒泡排序的第一种优化完成

下面最先斟酌优化,若是关于一个自身有序的序列,或则序列背面一大局部都是有序的序列,上面的算法就会糟蹋许多的时候开支,这里设置一个标记flag,若是这一趟发作了交流,则为true,不然为false。显着若是有一趟没有发作交流,申明排序已完成。

/**
     * 设置一个标记,若是这一趟发作了交流,则为true,不然为false。显着若是有一趟没有发作交流,申明排序已完成。
     * 
     * @param a
     * @return
     */
    private static int[] bubbleSort2(int[] a) {
        System.out.println("bubbleSort2的排序效果:");
        int j;
        int n = a.length;
        boolean flag = true;// 发作了交流就为true, 没发作就为false,第一次推断时必需标记位true。
        while (flag) {
            flag = false;// 每次最先排序前,都设置flag为未排序过
            for (j = 1; j < n; j  ) {
                if (a[j - 1] > a[j]) {// 前面的数字大于背面的数字就交流
                    // 交流a[j-1]和a[j]
                    int temp;
                    temp = a[j - 1];
                    a[j - 1] = a[j];
                    a[j] = temp;

                    // 透露表现交流过数据;
                    flag = true;
                }
            }
            n--;// 减小一次排序的尾界限
        } // end while
        return a;
    }

(3) 冒泡排序的第一种优化完成

再进一步做优化。好比,如今有一个包罗1000个数的数组,仅前面100个无序,背面900个都已排好序且都大于前面100个数字,那末在第一趟遍历后,末了发作交流的地位一定小于100,且这个地位今后的数据一定已有序了,也就是这个地位今后的数据不须要再排序了,因而纪录下这地位,第二次只要从数组头部遍历到这个地位就能够了。若是是关于上面的冒泡排序算法2来讲,虽然也只排序100次,然则前面的100次排序每次都要对背面的900个数据举行对照,而关于如今的排序算法3,只须要有一次对照背面的900个数据,今后就会设置尾界限,包管背面的900个数据不再被排序。

/**
     * 设置一个标记,若是这一趟发作了交流,则为true,不然为false。显着若是有一趟没有发作交流,申明排序已完成。
     * 
     * @param a
     * @return
     *
     */
    public static int[] bubbleSort3(int[] a) {
        System.out.println("bubbleSort3的排序效果:");
        int j;
        int n = a.length;
        boolean flag = true;// 发作了交流就为true, 没发作就为false,第一次推断时必需标记位true。
        while (flag) {
            flag = false;// 每次最先排序前,都设置flag为未排序过
            for (j = 1; j < n; j  ) {
                if (a[j - 1] > a[j]) {// 前面的数字大于背面的数字就交流
                    // 交流a[j-1]和a[j]
                    int temp;
                    temp = a[j - 1];
                    a[j - 1] = a[j];
                    a[j] = temp;

                    // 透露表现交流过数据;
                    flag = true;
                }
            }
            n--;// 减小一次排序的尾界限
        } // end while
        return a;
    }// end
}

(4) 三种要领console输出显现:

 

二.希尔排序及其完成

1)基础思想

先将全部待排序的纪录序列支解成为多少子序列离别举行直接插进去排序,列中的纪录“基础有序”时,再对全部纪录举行顺次直接插进去排序。

2)操纵要领

1. 挑选一个增量序列t1,t2,…,tk,个中ti>tj,tk=1;

2. 按增量序列个数k,对序列举行k 趟排序;

3. 每趟排序,依据对应的增量ti,将待排序列支解成多少长度为m 的子序列,离别对各子表举行直接插进去排序。仅增量因子为1 时,全部序列作为一个表来处置惩罚,表长度即为全部序列的长度。

3)希尔排序示例

4)希尔排序代码完成

package home;
import java.util.Arrays;

public class ShellSort {
    /**希尔排序的道理:依据需求,若是你想要效果从大到小分列,它会首先将数组举行分组,然后将较大值移到前面,较小值
     * 移到背面,末了将全部数组举行插进去排序,如许比起一最先就用插进去排序减少了数据交流和挪动的次数,能够说希尔排序是增强
     * 版的插进去排序
     * 拿数组5, 2, 8, 9, 1, 3,4来讲,数组长度为7,当increment为3时,数组分为两个序列
     * 5,2,8和9,1,3,4,第一次排序,9和5对照,1和2对照,3和8对照,4和比其下标值小increment的数组值相对照
     * 此例子是依照从大到小分列,以是大的会排在前面,第一次排序后数组为9, 2, 8, 5, 1, 3,4
     * 第一次后increment的值变成3/2=1,此时对数组举行插进去排序,
     *完成数组从大到小排
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub

        int[] arr = { 5, 2, 8, 9, 1, 3,4 };
        int[] b1 = shellSort(arr);

        System.out.println("shellSort排序效果:");

        Arrays.stream(b1).forEach(item -> {
            System.out.print(item   " ");
        });

    }

    private static int[] shellSort(int[] a) {
        // TODO Auto-generated method stub
        int j = 0;
        int temp = 0;
        // 每次将步长收缩为本来的一半,increment为步长
        for (int increment = a.length / 2; increment > 0; increment /= 2) {
            for (int i = increment; i < a.length; i  ) {
                temp = a[i];
                for (j = i; j >= increment; j -= increment) {
                    if (temp > a[j - increment])// 如想从小到大排只需修正这里
                    {
                        a[j] = a[j - increment];
                    } else {
                        break;
                    }

                }
                a[j] = temp;
            }

        }
        return a;
    }

}

5)控制台输出效果:

三.插进去排序及其完成

1)插进去排序代码完成:

package home;

import java.util.Arrays;

public class InsertSort {

    /**
     * 插进去排序
     * 
     * 从第一个元素最先,该元素能够以为已被排序 掏出下一个元素,在已排序的元素序列中从后向前扫描
     * 若是该元素(已排序)大于新元素,将该元素移到下一地位 重复步调3,直到找到已排序的元素小于或许即是新元素的地位 将新元素插进去到该地位中 重复步调2
     * 
     * @param numbers
     *            待排序数组
     */

    public static void main(String[] args) {
        int[] arr = { 1, 1, 2, 0, 9, 3, 12, 7, 8, 3, 4, 65, 22 };
        int[] b1 = insertSort(arr);
        
        System.out.println("insertSort排序效果:");
        Arrays.stream(b1).forEach(item -> {System.out.print(item   " ");});
    }

    private static int[] insertSort(int[] a) {
        int n = a.length;
        int temp = 0;
        int j = 0;

        for (int i = 0; i < n; i  ) {
            temp = a[i];
            // 如果temp比前面的值小,则将前面的值后移
            for (j = i; j > 0 && temp < a[j - 1]; j--) {
                a[j] = a[j - 1];
            }
            a[j] = temp;
        }
        return a;
    }
}

2)控制台输出效果:

四.插进去排序及其完成

 

1)挑选排序代码完成

package home;

public class ChooseSort {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] arr = { 1, 3, 2, 45, 65, 33, 12 };
        int n = arr.length;
        // 挑选排序的优化
        for (int i = 0; i < n - 1; i  ) {// 做第i趟排序
            int k = i;
            for (int j = k   1; j < n; j  ) {// 选最小的纪录
                if (arr[j] < arr[k]) {
                    k = j; // 记下现在找到的最小值地点的地位
                }
            }
            // 在内层轮回终了,也就是找到本轮轮回的最小的数今后,再举行交流
            if (i != k) { // 交流a[i]和a[k]
                int temp = arr[i];
                arr[i] = arr[k];
                arr[k] = temp;
            }
        }
        for (int num : arr) {
            System.out.print(num   " ");
        }
    }
}

2)控制台输出效果:

五.疾速排序及其完成

 

一.疾速排序1//流动的切分体式格局

package home;

public class ChooseSort {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println("chooseSort排序效果:");
        int[] arr = { 1, 3, 2, 45, 65, 33, 12 };
        int n = arr.length;
        // 挑选排序的优化
        for (int i = 0; i < n - 1; i  ) {// 做第i趟排序
            int k = i;
            for (int j = k   1; j < n; j  ) {// 选最小的纪录
                if (arr[j] < arr[k]) {
                    k = j; // 记下现在找到的最小值地点的地位
                }
            }
            // 在内层轮回终了,也就是找到本轮轮回的最小的数今后,再举行交流
            if (i != k) { // 交流a[i]和a[k]
                int temp = arr[i];
                arr[i] = arr[k];
                arr[k] = temp;
            }
        }
        for (int num : arr) {
            System.out.print(num   " ");
        }
    }
}

输出效果:

二.疾速排序的优化

-玖富娱乐是一家为代理招商,直属主管信息发布为主的资讯网站,同时也兼顾玖富娱乐代理注册登录地址。-
package home;

//关于基准地位的拔取:随机切分和三取样切分。流动切分的效力并非太好,随即切分是经常运用的一种切分,效力对照高,最坏情况下复杂度有可能为O(N^2),关于三数取中挑选基准点是最理想的一种.

public class QuickSort1 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println("疾速排序优化算法:");
        int[] a = {12,20,5,16,15,1,30,45,23,9};
        int start = 0;
        int end = a.length-1;
        sort(a,start,end);
        for(int i = 0; i<a.length; i  ){
             System.out.print(a[i] " ");
         }
    }
    public static int partition(int []array,int lo,int hi){
        //三数取中
        int mid=lo (hi-lo)/2;
        if(array[mid]>array[hi]){
            swap(array[mid],array[hi]);
        }
        if(array[lo]>array[hi]){
            swap(array[lo],array[hi]);
        }
        if(array[mid]>array[lo]){
            swap(array[mid],array[lo]);
        }
        int key=array[lo];
        
        while(lo<hi){
            while(array[hi]>=key&&hi>lo){
                hi--;
            }
            array[lo]=array[hi];
            while(array[lo]<=key&&hi>lo){
                lo  ;
            }
            array[hi]=array[lo];
        }
        array[hi]=key;
        return hi;
    }
    
    public static void swap(int a,int b){
        int temp=a;
        a=b;
        b=temp;
    }
    public static void sort(int[] array,int lo ,int hi){
        if(lo>=hi){
            return ;
        }
        int index=partition(array,lo,hi);
        sort(array,lo,index-1);
        sort(array,index 1,hi);
    }
}

输出效果:

六.兼并排序及其完成

1)兼并排序代码完成

package home;

public class MergeSort {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println("兼并排序算法:");
        int[] a = {12,20,5,16,15,1,30,45,23,9};
        int start = 0;
        int end = a.length-1;
        sort(a,start,end);
        for(int i = 0; i<a.length; i  ){
             System.out.print(a[i] " ");
         }
    }

    public static int[] sort(int[] a, int low, int high) {
        int mid = (low   high) / 2;
        if (low < high) {
            sort(a, low, mid);
            sort(a, mid   1, high);
            // 摆布合并
            merge(a, low, mid, high);
        }
        return a;
    }

    public static void merge(int[] a, int low, int mid, int high) {
        int[] temp = new int[high - low   1];
        int i = low;
        int j = mid   1;
        int k = 0;
        // 把较小的数先移到新数组中
        while (i <= mid && j <= high) {
            if (a[i] < a[j]) {
                temp[k  ] = a[i  ];
            } else {
                temp[k  ] = a[j  ];
            }
        }
        // 把左侧盈余的数移入数组
        while (i <= mid) {
            temp[k  ] = a[i  ];
        }
        // 把右边边盈余的数移入数组
        while (j <= high) {
            temp[k  ] = a[j  ];
        }
        // 把新数组中的数掩盖nums数组
        for (int x = 0; x < temp.length; x  ) {
            a[x   low] = temp[x];
        }
    }
}

2)控制台输出效果:

七.计数排序及其完成

1)计数排序代码完成

package home;

import java.util.Arrays;

public class CountingSort {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] arr = { 1, 1, 2, 0, 9, 3, 12, 7, 8, 3, 4, 65, 22 };
        int[] b1 = CountingSort(arr);
        System.out.println("基计数排序效果:");
        Arrays.stream(b1).forEach(item -> {
            System.out.print(item   " ");
        });
    }
    public static int[] CountingSort(int[] array) {
        if (array.length == 0) return array;
        int bias, min = array[0], max = array[0];
        for (int i = 1; i < array.length; i  ) {
            if (array[i] > max)
                max = array[i];
            if (array[i] < min)
                min = array[i];
        }
        bias = 0 - min;
        int[] bucket = new int[max - min   1];
        Arrays.fill(bucket, 0);
        for (int i = 0; i < array.length; i  ) {
            bucket[array[i]   bias]  ;
        }
        int index = 0, i = 0;
        while (index < array.length) {
            if (bucket[i] != 0) {
                array[index] = i - bias;
                bucket[i]--;
                index  ;
            } else
                i  ;
        }
        return array;
    }
}

2)控制台输出效果

八.基数排序及其完成

1)基数排序

基数排序也是非对照的排序算法,对每一位举行排序,从最低位最先排序,复杂度为O(kn),为数组长度,k为数组中的数的最大的位数;

基数排序是依照低位先排序,然后网络;再依照高位排序,然后再网络;顺次类推,直到最高位。有时候有些属性是有优先级递次的,先按低优先级排序,,再按高优先级排序。末了的序次就是高优先级高的在前,高优先级雷同的低优先级高的在前。基数排序基于离别排序,离别网络,以是是稳固的

2)算法形貌

     1.获得数组中的最大数,并获得位数。

     2. arr为原始数组,从最低位最先取每个位构成radix数组。

     3. 对radix举行计数排序(应用计数排序适用于小范围数的特性)。

3)基数排序代码完成

package home;

import java.util.ArrayList;
import java.util.Arrays;

public class RadixSort {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] arr = { 1, 1, 2, 0, 9, 3, 12, 7, 8, 3, 4, 65, 22 };
        int[] b1 = RadixSort(arr);
        System.out.println("基数排序效果:");
        Arrays.stream(b1).forEach(item -> {
            System.out.print(item   " ");
        });
    }
     public static int[] RadixSort(int[] array) {
            if (array == null || array.length < 2)
                return array;
            // 1.先算出最大数的位数;
            int max = array[0];
            for (int i = 1; i < array.length; i  ) {
                max = Math.max(max, array[i]);
            }
            int maxDigit = 0;
            while (max != 0) {
                max /= 10;
                maxDigit  ;
            }
            int mod = 10, div = 1;
            ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();
            for (int i = 0; i < 10; i  )
                bucketList.add(new ArrayList<Integer>());
            for (int i = 0; i < maxDigit; i  , mod *= 10, div *= 10) {
                for (int j = 0; j < array.length; j  ) {
                    int num = (array[j] % mod) / div;
                    bucketList.get(num).add(array[j]);
                }
                int index = 0;
                for (int j = 0; j < bucketList.size(); j  ) {
                    for (int k = 0; k < bucketList.get(j).size(); k  )
                        array[index  ] = bucketList.get(j).get(k);
                    bucketList.get(j).clear();
                }
            }
            return array;
        }
}

4)控制台输出效果

九.桶排序及其完成

 

1)桶排序代码完成

package home;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;


public class BucketSort {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] arr = { 1, 1, 2, 0, 9, 3, 12, 7, 8, 3, 4, 65, 22 };
        ArrayList <Integer> n = new ArrayList<Integer>();
        for(int i=0;i<arr.length;i  ){
            n.add(arr[i]);
        }
        System.out.println("桶排序后的效果");
        ArrayList resultArr=BucketSort(n, arr.length);
        
        //遍历体式格局1
        System.out.println("遍历体式格局1:");
        Iterator it1 = resultArr.iterator();
        while(it1.hasNext()){
            System.out.print(it1.next() " ");
        }
        
       //遍历体式格局2
        System.out.println();
        System.out.println("遍历体式格局2:");
        for(Iterator it2 = resultArr.iterator();it2.hasNext();){
            System.out.print(it2.next() " ");
       }
        
      //遍历体式格局3
        System.out.println();
        System.out.println("遍历体式格局3:");
        for(int i = 0;i < resultArr.size(); i   ){
            System.out.print(resultArr.get(i) " ");
        }
            
    }
    
    public static ArrayList<Integer> BucketSort(ArrayList<Integer> array, int bucketSize) {
        if (array == null || array.size() < 2)
            return array;
        int max = array.get(0), min = array.get(0);
        // 找到最大值最小值
        for (int i = 0; i < array.size(); i  ) {
            if (array.get(i) > max)
                max = array.get(i);
            if (array.get(i) < min)
                min = array.get(i);
        }
        int bucketCount = (max - min) / bucketSize   1;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);
        ArrayList<Integer> resultArr = new ArrayList<>();
        for (int i = 0; i < bucketCount; i  ) {
            bucketArr.add(new ArrayList<Integer>());
        }
        for (int i = 0; i < array.size(); i  ) {
            bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i));
        }
        for (int i = 0; i < bucketCount; i  ) {
            if (bucketSize == 1) { // 若是带排序数组中有重复数字时  
                for (int j = 0; j < bucketArr.get(i).size(); j  )
                    resultArr.add(bucketArr.get(i).get(j));
            } else {
                if (bucketCount == 1)
                    bucketSize--;
                ArrayList<Integer> temp = BucketSort(bucketArr.get(i), bucketSize);
                for (int j = 0; j < temp.size(); j  )
                    resultArr.add(temp.get(j));
            }
        }
        return resultArr;
    }
}

2)控制台输出效果

十.堆排序及其完成

(1)java完成堆排序

堆排序是一种树形挑选排序要领,它的特性是:在排序的过程当中,将array[0,...,n-1]算作是一颗完整二叉树的递次存储组织,应用完整二叉树中双亲节点和孩子结点之间的内涵干系,在以后无序区中挑选症结字最大(最小)的元素。

  1. 若array[0,...,n-1]透露表现一颗完整二叉树的递次存储形式,则双亲节点指针和孩子结点指针之间的内涵干系以下:

恣意一节点指针 i:父节点:i==0 ? null : (i-1)/2

                 左孩子:2*i 1

                 右孩子:2*i 2

  1. 堆的界说:n个症结字序列array[0,...,n-1],当且仅当知足以下请求:(0 <= i <= (n-1)/2)

①        array[i] <= array[2*i 1] 且 array[i] <= array[2*i 2];称为小根堆;

②       array[i] >= array[2*i 1] 且 array[i] >= array[2*i 2]; 称为大根堆

  1. 竖立大根堆:

n个节点的完整二叉树array[0,...,n-1],末了一个节点n-1是第(n-1-1)/2个节点的孩子。对第(n-1-1)/2个节点为根的子树调解,使该子树称为堆

关于大根堆,调解要领为:若【根节点的症结字】小于【摆布子女中症结字较大者】,则交流。

今后向前顺次对各节点((n-2)/2 - 1)~ 0为根的子树举行调解,看该节点值是不是大于其摆布子节点的值,若不是,将摆布子节点中较大值与之交流,交流后可能会损坏下一级堆,因而继承接纳上述要领构建下一级的堆,直到以该节点为根的子树构成堆为止。

重复应用上述调解堆的要领建堆,直到根节点。

  1. 堆排序:(大根堆)

                   ①   将存放在array[0,...,n-1]中的n个元素建成初始堆;

                   ②   将堆顶元素与堆底元素举行交流,则序列的最大值即已放到准确的地位;

                   ③   但此时堆被损坏,将堆顶元素向下调解使其继承连结大根堆的性子,再重复第②③步,直到堆中仅剩下一个元素为止。

空间复杂度:o(1);

时候复杂度:建堆:o(n),每次调解o(log n),故最好、最坏、均匀情况下:o(n*logn);

稳固性:不稳固

2java代码完成

package home;

public class HeapSort {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        HeapSort hs = new HeapSort();
        int[] array = { 87, 45, 78, 32, 17, 65, 53, 9, 122 };
        System.out.print("构建大根堆:");
        hs.toString(hs.buildMaxHeap(array));
        System.out.print("n"   "删除堆顶元素:");
        hs.toString(hs.deleteMax(array));
        System.out.print("n"   "插进去元素63:");
        hs.toString(hs.insertData(array, 63));
        System.out.print("n"   "大根堆排序:");
        hs.toString(hs.heapSort(array));
    }

    // 删除堆顶元素操纵
    private int[] deleteMax(int[] array) {
        // TODO Auto-generated method stub
        // 将堆的末了一个元素与堆顶元素交流,堆底元素值设为-99999
        array[0] = array[array.length - 1];
        array[array.length - 1] = -99999;
        // 对此时的根节点举行向下调解
        adjustDownToUp(array, 0, array.length);
        return array;

    }

    // 将元素array[k]自下往上逐渐调解树形组织
    private void adjustDownToUp(int[] array, int k, int length) {
        // TODO Auto-generated method stub
        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; // 被调解的结点的值放人终究地位
    }

    private void toString(int[] array) {
        // TODO Auto-generated method stub
        for (int i : array) {
            System.out.print(i   " ");
        }
    }

    // 构建大根堆:将array算作完整二叉树的递次存储组织
    private int[] buildMaxHeap(int[] array) {
        // TODO Auto-generated method stub
        // 从末了一个节点array.length-1的父节点(array.length-1-1)/2最先,直到根节点0,重复调解堆
        for (int i = (array.length - 2) / 2; i >= 0; i--) {
            adjustDownToUp(array, i, array.length);
        }
        return array;
    }

    // 插进去操纵:向大根堆array中插进去数据data
    public int[] insertData(int[] array, int data) {
        // TODO Auto-generated method stub
        array[array.length - 1] = data; // 将新节点放在堆的末尾
        int k = array.length - 1; // 须要调解的节点
        int parent = (k - 1) / 2; // 双亲节点
        while (parent >= 0 && data > array[parent]) {
            array[k] = array[parent]; // 双亲节点下调
            k = parent;
            if (parent != 0) {
                parent = (parent - 1) / 2; // 继承向上对照
            } else { // 根节点已调解终了,跳出轮回
                break;
            }
        }
        array[k] = data; // 将插进去的结点放到准确的地位
        return array;
    }

    // 堆排序
    public int[] heapSort(int[] array) {
        // TODO Auto-generated method stub
        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;
    }

}

3)控制台输出效果

十一.二叉树排序及有序鸠合

1)代码完成

BinaryTree类:

package home;

public class BinaryTree {
    class Node { // 声明一个节点类
        private Comparable data; // 节点的数据类型为Comparable
        private Node left; // 生存左子树
        private Node right; // 生存右子树

        public Node(Comparable data) { // 组织函数
            this.data = data;
        }

        public void addNode(Node newNode) {
            // 确定是放在左子树照样右子树
            if (newNode.data.compareTo(this.data) < 0) { // 新节点值小于以后节点
                if (this.left == null) {
                    this.left = newNode; // 左子树为空的话,新节点设为左子树
                } else {
                    this.left.addNode(newNode); // 不然继承向下推断
                }
            } else { // 新节点的值大于或即是以后节点
                if (this.right == null) {
                    this.right = newNode;
                } else {
                    this.right.addNode(newNode);
                }
            }
        }

        public void printNode() { // 接纳中序遍历
            if (this.left != null) { // 若是不为空先输出左子树
                this.left.printNode();
            }
            System.out.print(this.data   "t"); // 输出以后根节点
            if (this.right != null) { // 输出右子树
                this.right.printNode();
            }
        }
    }

    private Node root; // 透露表现根元素

    public void add(Comparable data) { // 向二叉树中插进去元素
        Node newNode = new Node(data);
        if (root == null) { // 没有根节点
            root = newNode;
        } else {
            root.addNode(newNode); // 推断放在左子树照样右子树
        }
    }

    public void print() {
        root.printNode(); // 依据根节点输出
    }
}
BinaryTreeSort类:
package home;
public class BinaryTreeSort {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        BinaryTree bt = new BinaryTree();
        bt.add(3);
        bt.add(5);
        bt.add(4);
        bt.add(8);
        bt.add(7);
        bt.add(8);
        bt.add(1);
        bt.print();
    }
}

2)控制台输出效果

十二.应用鸠合的4种排序排序体式格局

1)代码完成

package home;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.IntSummaryStatistics;
import java.util.Iterator;
import java.util.List;
import java.util.TreeSet;

public class Test {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        int[] b = { 1, 2, 4, 3, 6, 9, 7, 11, 13, 15, 
                18, 19, 23, 34, 56, 1000, 23, 78, 890, 908 };
       
        System.out.println("sort1()效果显现:");
        Sort1(b);
        huanhang();
        
        System.out.println("sort2()效果显现:");
        Sort2(b);
        huanhang();
        
        System.out.println("sort3()效果显现:");
        Sort3(b);
        huanhang();
        
        System.out.println("sort4()效果显现:");
        sort4(b);
        huanhang();

    }
        //换两次行
    private static void huanhang() {
        // TODO Auto-generated method stub
        for(int i=0;i<=2;i  ){
            System.out.println();
        }
    }

    private static void sort4(int[] b) {
        // TODO Auto-generated method stub
        List<Integer> lists = new ArrayList<Integer>();
        for (int i = 0; i < b.length; i  ) {
            lists.add(b[i]);
        }

        // 排序,直接挪用sort要领排序,排序体式格局是天然排序,即升序排序
        System.out.println("应用collections.sort()要领给list排序(默以为升序):");
        Collections.sort(lists);
        
        // 遍历
        for(int i:lists){
            System.out.print(i " ");
        }    
        System.out.println();
        System.out.println("应用collections.sort()要领给list降序排序"
                  "(先升序后用collections.reverse()反转):");
        System.out.print("=============");
        System.out.println("java8运用lamda表达式(forEach要领)对鸠合举行遍历:");
        Collections.reverse(lists);
        
        //java8运用lamda表达式(forEach要领)对鸠合举行遍历
        lists.forEach(obj -> System.out.print(obj "  "));
        
        //java8运用lamda表达式Iterator的forEachRemaining要领)对鸠合举行遍历
        System.out.println("");
        System.out.print("=============");
        System.out.println("java8运用lamda表达式Iterator的forEachRemaining要领)"
                  "对鸠合举行遍历:");
        Iterator<Integer> it =lists.iterator();
        it.forEachRemaining(obj->System.out.print(obj "  "));
    }
     
    private static void Sort3(int[] b) {
        // TODO Auto-generated method stub
        // int数组转化为Integer数组
        int n = b.length;
        Integer[] iarr = new Integer[n];
        for (int i = 0; i < n; i  ) {
            iarr[i] = new Integer(b[i]);
        }

        List<Integer> resultList = new ArrayList<>(iarr.length);
        Collections.addAll(resultList, iarr);

        
        System.out.println("应用collections给list排序:");
        for (int i : resultList) {
            System.out.print(i   " ");
        }

    }

    private static void Sort2(int[] b) {
        // TODO Auto-generated method stub
        @SuppressWarnings("unused")

        TreeSet<Integer> ts = new <Integer>TreeSet<Integer>();
        for (int i = 0; i < b.length; i  ) {
            ts.add(b[i]);
        }

        System.out.println("应用TreeSet方鸠合排序(会去掉重复的元素):");
        Iterator<Integer> it = ts.iterator();
        while (it.hasNext()) {
            System.out.print(it.next()   " ");
        }

    }

    private static void Sort1(int[] b) {
        // TODO Auto-generated method stub
        Arrays.sort(b);
        System.out.println("应用Arrays.sort()要领排序:");
        Arrays.stream(b).forEach(item -> {
            System.out.print(item   " ");
        });
        System.out.println();
    }
}

                 

2)控制台输出效果

 

 

-玖富娱乐是一家为代理招商,直属主管信息发布为主的资讯网站,同时也兼顾玖富娱乐代理注册登录地址。