问:写一个排序算法,并说明还没有其他的方式,并说明性能优化的方向
举例说明两个算法,一个最慢的一个最快的,并分析其性能
题目:对数组 {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