转载

Java 中常见的排序算法

其实小编是不太想写关于Java的相关文章，因为是这个编程语言实在是会用的人太多了，网上的博文数不胜数，没必要在重复造轮子了，但是虽然java这门语言会用的人很多，但是会用、掌握、熟练、和精通可不是闹着玩的，想要达到精通的级别，小编敢说，一个正规的开发公司能过达到精通java的开发人员屈指可数，所以小编这里就跳过关于java哪些简单的API 、语法，直接给大家介绍一些相对提升能力，并且不是那么基础的知识，说不定以后面试就会用到，尤其是排序，真的，不晓得为啥都喜欢在面试的时候出排序的题，实际大数据开发中真正手写排序的还真不多，我想可能是各个面试官想要看到的是，各个应聘者是否能够get到排序算法的精髓吧。

好了，每次写博客都要废话一堆，自我检讨，但是不想改变，接下来小编介绍几种创建的排序算法以及他们的Java实现。

1. 冒泡排序

原理：从第一个元素开始，和它相邻的比较，如果前面一个元素大于后面一个元素，就把他们互换位置。

原理图：

Java 中常见的排序算法

代码实现： 

public static void main(String[] args) {
        int arr[] = { 15, 16, 145, 91, 9, 5, 0 };
        int temp1=0;

        for(int i=0;i<arr.length-1;i++){  //控制循环次数：arr.length-1
            for(int j=0;j<arr.length-i-1;j++){  //控制比较次数：arr.length-i-1
                if(arr[j]>arr[j+1]){
                    temp1=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp1;
                }
            }
        }
}

增强版冒泡排序：

public static void main(String[] args) {
        int arr[] = { 1,0,2,3,4,5,6,7,8 };
        int temp1;
        for(int i=0;i<arr.length-1;i++){  //控制循环次数：arr.length-1
            boolean flag=true;  //判断内层循环是否执行
            for(int j=0;j<arr.length-i-1;j++){  //控制比较次数：arr.length-i-1
                if(arr[j]>arr[j+1]){
                    temp1=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp1;
                    flag=false;
                }
            }
            if(flag){  //如果内层循环的if一次都没有执行，说明已经排序结束
                break;
            }
        }

2.选择排序

原理：从第一个位置开始，将他与后面的所有元素比较，如果前面大于后面的，就交换位置。

原理图：

Java 中常见的排序算法

代码实现： 

public static void main(String[] args) {
    int arr[] = { 45,15,48,9,3,65,22 };
 for(int i=0;i<arr.length-1;i++){  //控制位置，从第一个位置开始，到倒数第二个位置
        for(int j=i+1;j<arr.length;j++){ //当前位置的下一个位置开始，与后面的所有比较
            if(arr[i]>arr[j]){
                int temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
            }
        }
    }

3. 插入排序

原理：从第二个元素位置开始，将他与他之前的元素比较，如果比之前的元素小，就将他插入到，那个元素的前面。

原理图：

Java 中常见的排序算法

代码实现： 

public static void main(String[] args) {
int arr[] = { 45, 15, 48, 9, 3, 65, 22 };
// 插入排序
int temp1;
for (int i = 1; i < arr.length; i++) { //从第二个数开始，一直到最后一个数
    for (int j = 0; j < i; j++) { //i之前的所有数，全部比较
        if (arr[i] < arr[j]) {
            temp1 = arr[i];
            for (int k = i; k > j; k--) { //将前面的数据把后面的覆盖，从j开始，一直到i 
                arr[k] = arr[k - 1];
            }
            arr[j] = temp1;
        }
    }
}

4. 快速排序

原理：先选取一个基准点，作用：基准点左侧小于基准点的数据 基准点右侧放的数据都是大于基准点的数据。基准点：最常用的基准点选第一个,最终一个大数组不停的进行查分 拆分的最终结果每个数组只有一个元素。

原理图：

Java 中常见的排序算法

解释：大循环中有两个循环，一个是从右往左，找比基准点小的，一个是从左往右找比基准点大的（找到之后，与基准点交换位置）。最终大循环，在left>=right时结束。

（2） 快排拆分：

Java 中常见的排序算法

解释：使用递归的方式，将数组左右两边一次次拆分，直到left>=right时，递归结束。

代码实现： 

public class QuickSort {
    public static void main(String[] args) {
        int arr[]= {2,7,1,2,8,1,3,9,415,189,123};
        sort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int [] arr,int left ,int right) {
        //递归的出口，当左侧==右侧
        if(left>=right) {
            return;
        }
        //获取基准点
        int point=getPoint(arr,left,right);
        //左边排序(递归)
        sort(arr,left,point-1);
        //右边排序(递归)
        sort(arr,point+1,right);
    }
    public static  int getPoint(int [] arr,int left ,int right) {
        int key=arr[left];
        while(left<right) {
            //从右向左循环,只要右边的比基准点大，就继续循序
            while(key<=arr[right]&&left<right) {
                //每循环一次，right的索引向左移一个
                right--;
            }
            //交换基准点的位置
            arr[left]=arr[right];
            //从左向右循环,只要左边的比基准点小，就继续循序
            while(arr[left]<=key&&left<right) {
                left++;
            }
            //交换基准点
            arr[right]=arr[left];
        }
        //最后给基准点赋值
        arr[left]=key;
        return left;
    }
}

注意：了解快速排序有助于了解MR的map-reduce过程，因为在MRmap阶段环形缓冲区满了之后，会将数据溢写到文件中，这个过程中就是使用了快速排序。

5. 计数排序

原理：对一个已有数组进行排序，那么就新建一个数组，数组长度为数组中元素的最大值+1。并把已有数组中的元素，对应上新建数组的下标，放入里面，新建数组的元素为，已有数组中元素的出现次数。

原理图：

Java 中常见的排序算法

解释：新创建一个数组，长度为需要排序的数组的最大值+1，遍历数组，将数组中的值分别找到新数组的索引，将索引处的元素+1，最后，遍历输出新数组的下标（只输出相应的值>0的下标，并且值为多少就输出几次）。

代码实现： 

public class CountSort {
    public static void main(String[] args) {
        int arr[]= {2,7,1,2,8,1,3,9,415,189,123};
        sort(arr,415);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int arr[],int max) {
        int index=0;
        int newarr[]=new int [max+1];
        for(int i=0;i<arr.length;i++) {
            newarr[arr[i]]++;
        }
        for(int i=0;i<newarr.length;i++) {
            if(newarr[i]!=0) {
                for(int j=0;j<newarr[i];j++) {
                    arr[index++]=i;
                }
            }
        }
    }
}

注意：了解计数排序，有助于了解hbase的布隆过滤器，布隆过滤器的特点就是，我说没有就没有，我说有不一定有（有一定的误判率）。

6. 归并排序（两路）

原理：针对多个有序的数据集进行排序。（时间复杂度：n*logN）

归并排序有两个阶段：

一个是归：将一个数据集拆分到每一个小的数据集只有一个元素。

实现一个数据集的归： 

public static void chai(int arr[],int first,int last,int [] newarr) {
        if(first>=last) {
            return;
        }
        //找中间点
        int mid=(first+last)/2;
        //左边归
        chai(arr,first,mid,newarr);
        //右侧拆
        chai(arr,mid+1,last,newarr);
        //拆完之后并
        meger(arr,first,last,mid,newarr);
}

一个是并：将两个有序的数据集，合并成为一个有序的大数据集。

实现两个有序数据集的并：

public int[] bing(int arr1[], int arr2[]) {
        //创建一个最终结果的数组：长度为arr1和arr2长度之和
        int newarr[] = new int[arr1.length+arr2.length];
        //新数组的元素标记
        int index=0;
        //记录arr1和arr2的下标
        int arr1_index=0;
        int arr2_index=0;
        //只要有一个数组，遍历结束，就停止循环
        while(arr1_index<arr1.length&&arr2_index<arr2.length) {
            //进行判断，将数据存储在新数组中
            if(arr1[arr1_index]<arr2[arr2_index]) {
                newarr[index++]=arr1[arr1_index++];
            }else {
                newarr[index++]=arr2[arr2_index++];
            }
        }
        //可能是arr1没有遍历完全
        while(arr1_index<arr1.length) {
            newarr[index++]=arr1[arr1_index++];
        }
        //可能是arr2没有遍历完全
        while(arr2_index<arr2.length) {
            newarr[index++]=arr2[arr2_index++];
        }
        return newarr;
    }

完整代码实现：

public class bingSort {
    public static void main(String[] args) {
        int arr[]= {1,8,7,6,11,2,4};
        int newarr[]=new int[arr.length];
        System.out.println(Arrays.toString(arr));
        chai(arr,0,arr.length-1,newarr);
        System.out.println(Arrays.toString(newarr));
    }
    //归
    public static void chai(int arr[],int first,int last,int [] newarr) {
        if(first>=last) {
            return;
        }
        //找中间点
        int mid=(first+last)/2;
        //左边归
        chai(arr,first,mid,newarr);
        //右侧拆
        chai(arr,mid+1,last,newarr);
        //拆完之后并
        meger(arr,first,last,mid,newarr);
    }
    /**
     *  并
     * @param arr 原数组
     * @param first 开始位置
     * @param last 结束位置
     * @param mid 中间位置
     * @param newarr  存放最终结果的数组
     */
    public static void meger(int arr[],int first,int last,int mid,int [] newarr) {
        //第一个数据集的起始下标
        int arr1_start=first;
        //第一个数据集的终止下标
        int arr1_end=mid;
        //第二个数据集的起始下标
        int arr2_start=mid+1;
        //第二个数据集的终止下标
        int arr2_end=last;
        int index=0;
        while(arr1_start<=arr1_end&&arr2_start<=arr2_end) {
            if(arr[arr1_start]<arr[arr2_start]) {
                newarr[index++]=arr[arr1_start++];
            }else {
                newarr[index++]=arr[arr2_start++];
            }
        }
        while(arr1_start<=arr1_end) {
            newarr[index++]=arr[arr1_start++];
        }
        while(arr2_start<=arr2_end) {
            newarr[index++]=arr[arr2_start++];
        }
        /**
         * 因为归并排序，需要使用两个有序的数据集，而arr一开始时无需的，所有每一次归并的时候
         * 需要将归并好之后的那一段数据集，赋值到arr中，使之后的归并仍然有序
         */
        //赋值的循环的次数，是本次归并的元素的个数
        for(int i=0;i<index;i++) {
            //每次赋值的时候，是从first开始
             arr[first+i]=newarr[i];
        }
    }
}

注意：在MR程序中，其中有两个阶段使用到了归并，一个是在缓冲区溢写小文件时，最后会将多个小文件归并成一个大文件，另一个则是在reduce拉去map处理的数据到本地是会生成很多小文件，此时也会做一次归并。

7. 二分法查找数据

原理：在已经排好序的基础上，将数组元素折半查找。

原理图：

Java 中常见的排序算法

代码实现：

public static void main(String[] args) {
        int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
        // 二分法查数据
        int num = new Scanner(System.in).nextInt(); //查找的数
        int start = 0;
        int end = arr.length - 1;
        int middle = (start + end) / 2;
        while (true) {
          //如果end<start说明全部找完也没有找到
            if (end < start) {
                System.out.println(num + "不在此数组中");
                break;
            }
            if (arr[middle] > num) {
                end = middle - 1;
            } else if (arr[middle] < num) {
                start = middle + 1;
            } else {
                System.out.println("这个数的索引下标为" + middle);
                break;
            }
            middle = (start + end) / 2;
        }

试试

原文  https://www.linuxidc.com/Linux/2019-08/159789.htm
正文到此结束
所属分类： 编程技术 Java

热门推荐

相关文章

阿里云首购8折
说给你听

本文目录
随机标签
书籍教程
springboot-demo Java入门教程 bootstrap3 CSS Apache基础教程 php ionic 教程 Python mysql教程 eclipse Ubuntu VPS系统配置 AngularJS 教程 MongoDB教程 Struts2教程 Redis教程 Spring教程 Git教程 Java设计模式 Jenkins进阶系列 openfire参考指南 HBase教程 Maven教程 hibernate教程 Docker 教程 memcached教程 Quartz指南 Hive教程 ANTLR教程 Ant教程 java实例教程 SpringCloud Elastic-Job-Lite XStream教程 深入浅出MyBatis Hazelcast教程 ibaties教程 SVN教程 rabittmq教程 Hadoop教程 solr教程 WebService CXF学习 springcloud-demo JPA教程 ActiveMQ中文指南 Java内存模型 java-demo dubbo教程 Linux入门视频教程
近期评论
  1. 1 Spring Cloud Circuit Breaker快速入门Demo
  2. 2 Spring Cloud Bus快速入门Demo
  3. 3 Spring Cloud Config快速入门Demo
  4. 4 Spring Cloud Function快速入门Demo
  5. 5 SSPanel-Uim搭建教程 2023年全新定制版主题-解决老版本命令失效问题
  6. 6 Spring Boot集成Milvus和deeplearning4j实现图搜图功能
  7. 7 Spring Boot集成Aviator实现参数校验
  8. 8 ACME自动申请免费的通配符https域名证书
  9. 9 wordpress 数据库和文件优化
  10. 10 CentOS安装Docker与Docker-Compose
网站信息
  • 文章总数：82,696 篇
  • 文件总数：284,257 个
  • 标签总数：2,380 个
  • 分类总数：84 个
  • 留言数量：2,560 条
  • 在线人数：667 人
  • 运行天数：4,392天
  • 最后更新：2024年11月05日22点
Loading...

其他链接

关于本站

本站定位：个人技术类博客

本站作用：写博客、记日志、闲聊扯淡鼓捣技术。

问题交流

[HBLOG]公众号 HBLOG HBLOG