java实现基数排序和堆排序

基数排序

package com.csw.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @Auther: 行路
 * @Date: Created on 2020/4/22 16:27 星期三
 * @Description: com.csw.sort 基数排序(目前只能排序正数)
 * @version: 1.0
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {53, 3, 542, 748, 14, 214};
        radixSort(arr);
        testTime(); //测试时间
    }

    /**
     * 基数排序
     */
    public static void radixSort(int[] arr) {
        System.out.println("基数排序~~~~");
        //1.得到数组中最大的数的位数
        int max = arr[0];//假设第一数就是最大值
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        //得到最大数是几位数
        int maxLength = (max + "").length();

        int[][] bucket = new int[10][arr.length];
        int[] bucketElementCounts = new int[10];

        //使用循环将代码处理
        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
            //争对每个元素对应位进行判断,第一次是个位,第二次是十位 ,第三次是百位
            for (int j = 0; j < arr.length; j++) {
                //取出每个元素的对应的值
                int digitOfElement = arr[j] / n % 10;
                //放入到对应的桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++;

            }
            //按照这个桶的顺序(一维数组的下标依次取出数据,放入原来的数组)
            int index = 0;
            //遍历每一个桶,并将桶中是数据,放入到原数组中
            for (int k = 0; k < bucketElementCounts.length; k++) {
                //如果桶中有数据,才放入到原数组中
                if (bucketElementCounts[k] != 0) {
                    //循环该桶即第k个桶,放入
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        //取出元素放入到arr
                        arr[index++] = bucket[k][l];
                    }
                }
                //第i+1论处理后,需要将每个bucketElementCounts[k]=0!!!!1
                bucketElementCounts[k] = 0;
            }
           // System.out.println("第" + (i + 1) + "轮,对个位的排序处理arr=" + Arrays.toString(arr));
        }
    }

    /**
     * 测试时间
     */
    public static void testTime() {
        int[] arr = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arr[i] = (int) (Math.random() * 8000000);
        }

        Date date1 = new Date();
        SimpleDateFormat simpleDateFormatter = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormatter.format(date1);

        System.out.println("排序前的时间是=" + date1Str);
        long l1 = System.currentTimeMillis();
        radixSort(arr);

        Date date2 = new Date();
        //   SimpleDateFormat simpleDateFormatter = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date2Str = simpleDateFormatter.format(date2);
        System.out.println("排序后的时间是=" + date2Str);
        long l2 = System.currentTimeMillis();
        System.out.println("耗时毫秒数为:" + (l2 - l1));
    }


    /**
     * 基数排序方法 思路分析得到推论
     * @param arr
     */
    public static void radixSortTest(int[] arr) {
        //第一轮排序(针对每个元素的各位进行排序处理)

        //定义一个二维数组,表示10个桶,每个桶就是一个二维数组
        //1.二维数组包含10个一维数组
        //2.为了防止在放数的时候数据溢出,则每个一位数组(桶),大小位arr.length
        //3.名明确,基数排序是使用空间换时间
        int[][] bucket = new int[10][arr.length];

        //为了记录每个桶中,实际存放了多少数据,我们定义一个一维数组记录各个桶的每次放入的数据个数
        //bucketElementCounts[0],记录的就是bucket[0]桶的放入数据个数
        int[] bucketElementCounts = new int[10];

        //第一轮
        for (int j = 0; j < arr.length; j++) {
            //取出每个元素的个位的值
            int digitOfElement = arr[j] % 10;
            //放入到对应的桶中
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            bucketElementCounts[digitOfElement]++;

        }
        //按照这个桶的顺序(一维数组的下标依次取出数据,放入原来的数组)
        int index = 0;
        //遍历每一个桶,并将桶中是数据,放入到原数组中
        for (int k = 0; k < bucketElementCounts.length; k++) {
            //如果桶中有数据,才放入到原数组中
            if (bucketElementCounts[k] != 0) {
                //循环该桶即第k个桶,放入
                for (int l = 0; l < bucketElementCounts[k]; l++) {
                    //取出元素放入到arr
                    arr[index++] = bucket[k][l];
                }
            }
            //第1论处理后,需要将每个bucketElementCounts[k]=0!!!!1
            bucketElementCounts[k] = 0;
        }
        System.out.println("第一轮,对个位的排序处理arr=" + Arrays.toString(arr));

        //============================================
        //第二轮 对10位
        for (int j = 0; j < arr.length; j++) {
            //取出每个元素的个位的值
            int digitOfElement = arr[j] / 10 % 10;
            //放入到对应的桶中
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            bucketElementCounts[digitOfElement]++;

        }
        //按照这个桶的顺序(一维数组的下标依次取出数据,放入原来的数组)
        index = 0;
        //遍历每一个桶,并将桶中是数据,放入到原数组中
        for (int k = 0; k < bucketElementCounts.length; k++) {
            //如果桶中有数据,才放入到原数组中
            if (bucketElementCounts[k] != 0) {
                //循环该桶即第k个桶,放入
                for (int l = 0; l < bucketElementCounts[k]; l++) {
                    //取出元素放入到arr
                    arr[index++] = bucket[k][l];
                }
            }
            //第1论处理后,需要将每个bucketElementCounts[k]=0!!!!1
            bucketElementCounts[k] = 0;
        }
        System.out.println("第二轮,对个位的排序处理arr=" + Arrays.toString(arr));


        //============================================
        //第三轮
        for (int j = 0; j < arr.length; j++) {
            //取出每个元素的个位的值
            int digitOfElement = arr[j] / 100 % 10;
            //放入到对应的桶中
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            bucketElementCounts[digitOfElement]++;

        }
        //按照这个桶的顺序(一维数组的下标依次取出数据,放入原来的数组)
        index = 0;
        //遍历每一个桶,并将桶中是数据,放入到原数组中
        for (int k = 0; k < bucketElementCounts.length; k++) {
            //如果桶中有数据,才放入到原数组中
            if (bucketElementCounts[k] != 0) {
                //循环该桶即第k个桶,放入
                for (int l = 0; l < bucketElementCounts[k]; l++) {
                    //取出元素放入到arr
                    arr[index++] = bucket[k][l];
                }
            }
            //第1论处理后,需要将每个bucketElementCounts[k]=0!!!!1
            bucketElementCounts[k] = 0;
        }
        System.out.println("第三轮,对个位的排序处理arr=" + Arrays.toString(arr));
    }
}

堆排序

package com.csw.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @Auther: 行路
 * @Date: Created on 2020/4/26 14:18 星期日
 * @Description: com.csw.sort 堆排序
 * @version: 1.0
 */
public class Heapsort {
    public static void main(String[] args) {
        //要求将数组升序排列
        int arr[]={4,6,8,5,9};
        heapSort(arr);
        testTime();//测试时间

        //System.out.println('0'*'0'/('0'+'0')==24);
    }

    //编写一个堆排序的方法
    public static void heapSort(int arr[]){
        int temp=0;
        System.out.println("堆排序");
        //从堆底开始调整
        for(int i=arr.length/2-1;i>=0;i--){
            adjustHeap(arr,i,arr.length);
        }

        for(int j=arr.length-1;j>0;j--){
            //交换
            temp=arr[j];
            arr[j]=arr[0];
            arr[0]=temp;
            //因为交换后只有栈顶不符合,所以直接调整栈顶
            adjustHeap(arr,0,j);
        }
        System.out.println("数组="+ Arrays.toString(arr));
    }

    //将一个数组(二叉树),调整成一个大顶推

    /** 功能：完成将以i对应的非叶子结点的树,调整成大顶堆
     *  int[] arr={4,6,8,5,9} 调整后i=1 adjustHeap->调整成49856
     *  再次调用adjustHeap传入的是0 调整成96854
     *  调整需要从下至上
     * @param arr   表示待调整的数组
     * @param i     表示非叶子结点在数组中的索引
     * @param length 表示对多少个元素继续调整,length是在主键减少的
     */
    public static void adjustHeap(int[] arr,int i,int length){
        int temp=arr[i]; //取出当前元素的值,保存在临时变量中
        //开始调整 k=i*2+1 k是i结点的左子结点
        for(int k=i*2+1;k<length;k=k*2+1){
            if(k+1<length&&arr[k]<arr[k+1]){
                //说明左子结点小于右子结点的值
                k++;
            }
            if(arr[k]>temp){
                //如果子结点大于父结点
                arr[i]=arr[k]; //把较大的值赋给当前结点
                i=k; //i指向k,继续循环比较
            }else{
                break; //
            }
        }
        //当for循环后,已经将以i为父结点的树的最大值,放在了最顶(局部)
        arr[i]=temp; //将temp值放到调整后的位置
    }
    /**
     * 测试时间
     */
    public static void testTime() {
        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random() * 80000);
        }
        int[] temp=new int[arr.length];
        Date date1 = new Date();
        SimpleDateFormat simpleDateFormatter = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormatter.format(date1);

        System.out.println("排序前的时间是=" + date1Str);
        long l1 = System.currentTimeMillis();
        heapSort(arr);

        Date date2 = new Date();
        //   SimpleDateFormat simpleDateFormatter = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date2Str = simpleDateFormatter.format(date2);
        System.out.println("排序后的时间是=" + date2Str);
        long l2 = System.currentTimeMillis();
        System.out.println("耗时毫秒数为:" + (l2 - l1));
    }
}