首页 > 其他分享 >针对一个数组的排序,面试官会这样问

针对一个数组的排序,面试官会这样问

时间:2023-02-07 22:34:45浏览次数:54  
标签:面试官 String int arr 数组 Integer 排序

问:写一个排序算法,并说明还没有其他的方式,并说明性能优化的方向

举例说明两个算法,一个最慢的一个最快的,并分析其性能

题目:对数组  {1,3,6,1,8,22,0,1}进行排序

答:

    public static void main(String[] args) {
        String[] arr = {"1", "1", "7", "3", "9", "11", "7"};
        Arrays.sort(arr);
        for (String i : arr) {
            System.out.println(i);
        }
    }

问:首先,你上面代码是有问题的,你执行下排序结果,是不对的,既不是升序也不是降序!如果想实现排序你首先需要将字符串数组转成真正的Integer数组,才能使用Arrays.sort

答:好的知道了

问:那我再问你,String类型的和Integer有啥区别,String是通过什么排序的?

答:Integer呢就是通过数字的大小进行排序的,String的比较是通过Compare方法,通过查看Compare源码,我们可以发现,通过将两个字符串存储在char类型数组中,选择最短的一个字符串,然后从第一位遍历两个数组,返回第一个不相同字符的ASCII码(十进制)相减的结果;

   "abcd".compareTo("adef")== -2

   "abc".compareTo("abcdef")== -3

   "abc".compareTo("abc") == 0

问:上面你直接用函数实现的,能不能自己写个算法实现一下?

答:可以的~举例冒泡:

   public static void main(String[] args) {
        int temp;
        Integer[] arr = {1, 1, 7, 3, 9, 11, 7};
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        for (Integer i : arr) {
            System.out.print(i + "->");
        }
    }

快速排序:

 public static void quickSort(int[] a, int l, int r) {
        if (l < r) {
            int i,j,x;

            i = l;
            j = r;
            x = a[i];
            while (i < j) {
                while(i < j && a[j] > x)
                    j--; // 从右向左找第一个小于x的数
                if(i < j)
                    a[i++] = a[j];
                while(i < j && a[i] < x)
                    i++; // 从左向右找第一个大于x的数
                if(i < j)
                    a[j--] = a[i];
            }
            a[i] = x;
            quickSort(a, l, i-1); /* 递归调用 */
            quickSort(a, i+1, r); /* 递归调用 */
        }
    }

    public static void main(String[] args) {
        int i;
        int a[] = {30,40,60,10,20,50};

        System.out.printf("before sort:");
        for (i=0; i<a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.printf("\n");

        quickSort(a, 0, a.length-1);

        System.out.printf("after  sort:");
        for (i=0; i<a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.printf("\n");
    }

问:好的,你真棒,你能说下这两种排序算法的区别吗?或者说在性能上哪种更好?

答:第一种方法(快排)的时间复杂度一般是O(nlogn),而冒泡排序的时间复杂度是O(n^2),所以在排序数据量较大的情况下,快排的性能比冒泡排序更好。快排的优势是更快的速度,更少的比较次数和交换次数。

      在JVM层面,快速排序使用了递归算法,它通过比较数组中的元素,并将数组分为两个子数组,递归排序每个子数组,最后合并结果。因为每次排序只需要比较一个元素,所以快速排序的复杂度是O(nlogn),比冒泡排序(O(n^2))等其他排序算法要快得多。

     JVM会管理内存的使用,并自动执行垃圾回收,以确保快速排序不会因内存不足而停止。因此,在JVM上执行快速排序是一种高效的方法。

 

标签:面试官,String,int,arr,数组,Integer,排序
From: https://www.cnblogs.com/dk1024/p/17100038.html

相关文章

  • drf认证组件/权限/频率 排序组件 分页组件
    Drf认证组件eg:个别接口需要登录后才可以使用局部使用#需要编写一个认证类#在py文件中创建一个认证类的py文件authentication.py通过继承来编写:eg:登录验证from......
  • DRF - 过滤与排序、分页组件
    目录过滤与排序1.drf内置过滤类【继承GenericAPIView】导入内置过滤器-SearchFilterviews.py-搜索方式2.第三方过滤器导入模块这里用到了第三方模块django-filtersviews......
  • DRF - 过滤与排序、分页器
    目录频率组件1.频率限制2.频率认证步骤3.全局使用和局部使用(1)局部权限:对单独的视图类生效(2)全局权限:对于全局的视图类生效(3)全局权限+局部禁用4.代码演示throttling.py-......
  • drf权限组件 频率组件 过滤排序 分页
    1认证组件#以后,有的接口需要登录才能访问,有的接口,不等了就能访问 -登录认证的限制#写一个登录接口,返回token,以后只要带着token过来,就是登陆了,不带就是没有登录#......
  • 多维数组的建立及遍历
    packagecom.test;importjava.util.*;importstaticjava.util.Arrays.fill;publicclassMain{publicstaticvoidmain(String[]args){finalin......
  • 【数组】——有序数组的平方
    【数组】——有序数组的平方暴力解法:先平方后排序时间复杂度\(O(n+nlogn)=O(nlogn)\)#力扣运行出错,但测试可用classSolution(object):defsortedSquares(self,......
  • drf之三大认证、过滤、排序、分页组件
    drf之三大认证、过滤、排序、分页组件本文所介绍的组件,都有着很相似的配置方式,继承组件类,类体中配置参数,视图类中配置参数添加对应的组件类或者全局配置,我们就可以方便的......
  • drf-认证、权限、频率、过滤、排序、分页
    1.认证组件1.1局部认证1.首先写两个接口,一个查询单个一个查询所有,我们利用视图扩展类和视图子类写在一个视图类上:views.py:fromrest_framework.viewsetsimportVie......
  • 认证组件、权限组件、频率组件、过滤排序、分页
    认证组件、权限组件、频率组件、过滤排序、分页认证组件1.认证组件###视图fromrest_framework.genericsimportListAPIView,RetrieveAPIViewfromrest_framework.m......
  • 数组拷贝及排序
    packagecom.test;importjava.util.*;importstaticjava.util.Arrays.fill;publicclassMain{publicstaticvoidmain(String[]args){int[]a=ne......