3

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

 1 year ago
source link: https://www.cnblogs.com/dk1024/p/17100038.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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

问：你写一个排序算法吧，顺便说一下其他的方式，可以吧？

题目：对数组  {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

答：好的知道了

问：那我再问你，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上执行快速排序是一种高效的方法。


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK