[ Java面试题 ]算法篇

1、堆和栈在内存中的区别是什么?

概念:

  栈(stack)是为执行线程留出的内存空间。当函数被调用的时候,栈顶为局部变量和一些 bookkeeping 数据预留块。当函数执行完毕,块就没有用了,可能在下次的函数调用的时候再被使用。栈通常用后进先出的方式预留空间;因此最近的保留块通常最先被释放。这么做可以使跟踪堆栈变的简单;从栈中释放块只不过是指针的偏移而已。

  堆(heap)是为动态分配预留的内存空间。和栈不一样,从堆上分配和重新分配块没有固定模式;你可以在任何时候分配和释放它。这样使得跟踪哪部分堆已经被分配和被释放变的异常复杂;有许多定制的堆分配策略用来为不同的使用模式下调整堆的性能。

区别:

内存分配:

    栈:由编译器自动分配和释放,存放函数的参数、局部变量、临时变量、函数返回地址等。

    堆:一般人为分配和释放,对Java而言由系统释放回收,但对于C++等,必须手动释放,如果没有手动释放会引起内存泄漏。

系统响应:

    栈:只要栈的剩余空间大于所申请的空间,系统将为程序提供内存,否则将报异常提示栈溢出。

    堆:在记录空闲内存地址的链表中寻找一个空间大于所申请空间的堆结点,然后将该结点从空闲结点链表中删除,并将该结点的空间分配给程序。

大小限制:

    栈:在Windows下,栈是向低地址扩展的数据结构,是一块连续的内存的区域。这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的,在 windows下,栈的大小是2M,如果申请的空间超过栈的剩余空间时,将提示overflow。因此,能从栈获得的空间较小。     堆:堆是向高地址扩展的数据结构,是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的,自然是不连续的,而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。

结论:堆获得的空间比较灵活,也比较大。

分配效率:     栈:由系统自动分配,速度较快,无法人为控制。 

    堆:由new分配的内存,一般速度比较慢,而且容易产生内存碎片,不过用起来最方便。

存储内容:

    栈:在栈中,第一个进栈的是主函数下一条指令的地址,然后是函数的各个参数,在大多数编译器中,参数是由右往左入栈,然后是函数中的局部变量。注意,静态变量不入栈。出栈则刚好顺序相反。

    堆:一般在堆的头部用一个字节存放堆的大小,具体内容受人为控制。

2、求出1000之内的所有水仙花数

概念:水仙花数指的是一个三位整数,它的各位数字的立方和等于这个数本身.。

解法:

public class NumberOfDaffodils {    
    public static void main(String[] args) {  
        // TODO Auto-generated method stub  
         int hundred, ten, bits;    
         System.out.println("水仙花数为:");    
         for (int i = 100; i <= 999; i++)    
         {    
             hundred = i / 100;    
             ten = i % 100 / 10;    
             bits = i % 10;    
             if (i == hundred * hundred * hundred + ten * ten * ten + bits * bits * bits)    
             {    
                 System.out.print(i + "    ");    
             }    
         }      
    }  
} 

3、比较一下几种常用的排序算法,简单的写一下你知道的几种排序算法?

比较:

1.稳定性比较

  插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排序是稳定的

  选择排序、希尔排序、快速排序、堆排序是不稳定的

2.时间复杂性比较

  插入排序、冒泡排序、选择排序的时间复杂性为O(n2)

  其它非线形排序的时间复杂性为O(nlog2n)

  线形排序的时间复杂性为O(n);

3.辅助空间的比较

  线形排序、二路归并排序的辅助空间为O(n);

  其它排序的辅助空间为O(1);

4.其它比较

  *插入、冒泡排序的速度较慢,但参加排序的序列局部或整体有序时,这种排序能达到较快的速度,但是在这种情况下,快速排序反而慢了。

  *当n较小时,对稳定性不作要求时宜用选择排序,对稳定性有要求时宜用插入或冒泡排序。

  *若待排序的记录的关键字在一个明显有限范围内时,且空间允许是用桶排序。

  *当n较大时,关键字元素比较随机,对稳定性没要求宜用快速排序。

  *当n较大时,关键字元素可能出现本身是有序的,对稳定性有要求时,空间允许的情况下宜用归并排序。

  *当n较大时,关键字元素可能出现本身是有序的,对稳定性没有要求时宜用堆排序。

常见的排序算法:

选择排序

public class SelectionSort {
    public void selectionSort(int[] array) {
       int temp;
       for (int i = 0; i < array.length - 1; i++) {
              for (int j = i + 1; j <= array.length - 1; j++) {
              if (array[i] > array[j]) {    
              // 注意和冒泡排序的区别,这里是i和j比较。
              temp = array[i];
              array[i] = array[j];
              array[j] = temp;
             }
        }            // 打印每趟排序结果
       for (int m = 0; m <= array.length - 1; m++) {
             System.out.print(array[m] + "\t");
       }
          System.out.println();
       }
    }    
    public static void main(String[] args) {
        SelectionSort selectionSort = new SelectionSort(); 
        int[] array = { 5, 69, 12, 3, 56, 789, 2, 5648, 23 };
        selectionSort.selectionSort(array);        
    for (int m = 0; m <= array.length - 1; m++) {
            System.out.print(array[m] + "\t");
        }
    }
}

插入排序

public class InsertSort {
    public void insertSort(int[] array, int first, int last) {        
    int temp, i, j;        
    for (i = first + 1; i <= last - 1; i++) {
            temp = array[i];
            j = i - 1;            
        while (j >= first && array[j] > temp) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = temp;            // 打印每次排序结果
            for (int m = 0; m <= array.length - 1; m++) {
                System.out.print(array[m] + "\t");
            }
            System.out.println();
        }
    }    
     public static void main(String[] args) {
        InsertSort insertSort = new InsertSort();
            int[] array = { 5, 69, 12, 3, 56, 789, 2, 5648, 23 };
        insertSort.insertSort(array, 0, array.length);      
             for (int i = 0; i <= array.length - 1; i++) {
            System.out.print(array[i] + "\t");
        }
    }
}

快速排序

public class QuickSort {    
    public int partition(int[] sortArray, int low, int height) {        
    int key = sortArray[low];        
    while (low < height) {            
        while (low < height && sortArray[height] >= key)
            height--;
            sortArray[low] = sortArray[height];            
            while (low < height && sortArray[low] <= key)
                low++;
                sortArray[height] = sortArray[low];
            }
            sortArray[low] = key;        // 打印每次排序结果
        for (int i = 0; i <= sortArray.length - 1; i++) {
            System.out.print(sortArray[i] + "\t");
        }
        System.out.println();        
        return low;
    }    
    public void sort(int[] sortArray, int low, int height) {        
        if (low < height) {            
            int result = partition(sortArray, low, height);
            sort(sortArray, low, result - 1);
            sort(sortArray, result + 1, height);
        }
    }
    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();        
        int[] array = { 5, 69, 12, 3, 56, 789, 2, 5648, 23 };        
        for (int i = 0; i <= array.length - 1; i++) {
            System.out.print(array[i] + "\t");
        }
        System.out.println();
        quickSort.sort(array, 0, 8);        
        for (int i = 0; i <= array.length - 1; i++) {
            System.out.print(array[i] + "\t");
        }
    }
}

希尔排序

public class ShellSort {
    public void shellSort(int[] array, int n) {
        int i, j, gap;
        int temp;
        for (gap = n / 2; gap > 0; gap /= 2) {
            for (i = gap; i < n; i++) {       
                for (j = i - gap; j >= 0 && array[j] > array[j + gap]; j -= gap) {
                    temp = array[j];
                    array[j] = array[j + gap];
                    array[j + gap] = temp;
                }                // 打印每趟排序结果
                for (int m = 0; m <= array.length - 1; m++) {
                    System.out.print(array[m] + "\t");
                }
                System.out.println();
            }
        }
    } 
     public static void main(String[] args) {
        ShellSort shellSort = new ShellSort();
        int[] array = { 5, 69, 12, 3, 56, 789, 2, 5648, 23 };
        shellSort.shellSort(array, array.length);        
        for (int m = 0; m <= array.length - 1; m++) {
            System.out.print(array[m] + "\t");
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏个人随笔

论 Java 的访问权限

Java中成员访问权限 Java中的访问权限控制符有四个: 作用域_____当前类____同一package___子孙类____其他package publi...

3768
来自专栏Python小屋

Python 3.x中内置函数range()函数的用法

range()是Python开发中非常常用的一个内置函数,语法格式为range([start,] end [, step] ),有range(stop)、ran...

3124
来自专栏Android相关

X86 Assemble指令--MOVS指令簇

该指令簇包括: MOVS mem16,mem16:显式指定源操作数与目的操作数 MOVSB:每次移动一个字节 MOVSW:每次移动一个字 MOVSD:每...

1342
来自专栏Python小屋

学习Python的利器:内置函数dir()和help()

(1)内置函数dir()用来查看对象的成员。在Python中所有的一切都是对象,除了整数、实数、复数、字符串、列表、元组、字典、集合等等,还有range对象、e...

3468
来自专栏日常学python

再有人问什么是元类,就把这篇文章扔给他!

我之前在深入理解python中的类和对象中说过,python中的类也是一个对象,可以说是类对象,可以由 type() 来创建类对象的。有了这个知识我们先看看下面...

1152
来自专栏自动化测试实战

RF自定义系统关键字

3817
来自专栏光变

3.3 ASM-方法-工具类

‘org.objectweb.asm.commons’包含了一些预定义的方法适配器,可以用来定义自己的适配器。 本节介绍三个工具类,并且会展示它们如何和3.2....

2310
来自专栏欧阳大哥的轮子

深入解构objc_msgSend函数的实现

熟悉OC语言的Runtime(运行时)机制以及对象方法调用机制的开发者都知道,所有OC方法调用在编译时都会转化为对C函数objc_msgSend的调用。

1082
来自专栏轮子工厂

一篇文章帮你解决中文乱码问题---JavaWeb中文编码问题全面解析

这就是为什么我们在浏览器的地址栏中能看到中文,但是把地址拷贝出来后中文就变成了一些奇怪的串了。

5904
来自专栏Python小屋

Python处理文本文件案例一则

问题描述:当前文件夹中有一文件data.txt,其中包含一些自然数,每行一个。要求编写程序,读取data.txt中的所有自然数,将其升序排序之后写入新文件dat...

1223

扫码关注云+社区

领取腾讯云代金券