面试一定会被问到的基础知识。
数组
数组是存放在连续内存空间上的相同类型数据的集合。
概念有两个要点:一个是连续内存,另一个是相同数据类型。
连续内存决定了数组的存取较为方便,通过下标可以方便地进行索引。数组的下标从0开始。连续内存也决定了在特定位置增添数组内元素时,有时需要移动其他元素的地址。数组内的元素无法删除,只能覆盖。
Java中,没有指针的概念,寻址操作完全交给虚拟机。其二维数组每行头节点的排列,没有规则,也就谈不上连续。
排序算法
排序算法按照使用外存与否,可以分为内部排序和外部排序;按照是否依赖于内部元素互相比较与否,可以分为比较排序和非比较排序。
比较排序中,按照比较后进行的不同操作,又可分为交换排序、选择排序、插入排序、归并排序等。比较排序适用于一切需要排序的情况。
非比较排序是通过确定每个元素之前,应该有多少个元素来排序。基数排序是非比较排序。
交换排序
冒泡排序
- 比较相邻的元素,如果前面的大于后面,交换它们
- 循环中,每一对元素都进行比较
- 重复过程,排除上次循环中已经沉到最底部的元素
1 2 3 4 5 6 7 8 9 10 11 12
| for (int i = 0; i < array.length; i++) { boolean exchange = false; for (int j = 0; j < array.length - 1 - i; j++) { if (array[j + 1] > array[j]) { int temp = array[j + 1]; array[j + 1] = array[j]; array[j] = temp; exchange = true; } } if (!exchange) return; }
|
优化:
可以考虑在算法中加入一个布尔值,用来标识该轮有没有进行数据的交换。若在一轮循环中没有进行数据交换,说明无序区已经排好序,可以直接退出循环。
快速排序
基本思想是通过一趟排序将待排序记录分隔成独立的两部分,其中一部分元素都比另一部分关键字小,然后递归地分别对这两部分记录进行排序,以达到整个序列有序的目的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
| public class QuickSort { public static int partition(int[] array, int low, int high) { int pivot = array[high]; int pointer = low; for (int i = low; i < high; i++) { if (array[i] <= pivot) { int temp = array[i]; array[i] = array[pointer]; array[pointer] = temp; pointer++; } System.out.println(Arrays.toString(array)); } int temp = array[pointer ]; array[pointer] = array[high]; array[high] = temp; return pointer; } public static void quickSort(int[] array, int low, int high) { if (low < high) { int position = partition(array, low, high); quickSort(array, low, position -1); quickSort(array, position + 1, high); } } public static void main(String[] args) { int[] array = {6,72,113,11,23}; quickSort(array, 0, array.length -1); System.out.println("排序后的结果"); System.out.println(Arrays.toString(array)); } }
|
选择排序
简单选择排序
- 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置(首个元素)
- 再从剩余未排序元素中继续寻找最小(大)元素,放到已经排序序列的末尾
1 2 3 4 5 6 7 8 9 10 11 12
| for (int i = 0; i < array.length; i++) { int index = i; for (int j = i; j < array.length; j++) { if (array[j] < array[index]) { index = j; } } int temp = array[index]; array[index] = array[i]; array[i] = temp; }
|
插入排序
直接插入排序:通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
1 2 3 4 5 6 7 8
| for (int i = 0; i < array.length - 1; i++) { int index = i, current = array[i + 1]; while (index >= 0 && current < array[index]) { array[index + 1] = array[index]; index--; } array[index + 1] = current; }
|
链表
链表是一种通过指针(或者是对象)串联在一起的线性结构。每一个节点由两部分组成,一个是数据域,一个是指针域(对象域)(存放指向下一个节点的指针(或对象))。最后一个节点的指针域(或对象)为空。
链表的入口节点,称为链表的头节点。链表有以下几种类型:
- 单链表。其指针域只能指向节点的下一节点。
- 双链表。每一个节点有两个指针域,一个指向上一节点,一个指向下一节点。可以向前查询,也可以向后查询。
- 循环链表。循环链表的首尾相连。
链表通过指针域链接在内存中的各个节点。节点在内存中不是连续分布的。
Java中,链表节点的定义可以如下:
1 2 3 4 5 6 7 8 9 10 11 12 13
| class ListNode { int val; ListNode next; public ListNode(){} public ListNode(int val) { this.val = val; this.next = null; } public ListNode(int val, ListNode next) { this.val = val; this.next = next; } };
|
链表操作
删除节点
删除节点 D:
删除后节点 D 仍然留在内存里,由于Java有自己的内存回收机制,可以不用额外处理。
添加节点
在节点 D 的前面添加节点 F:
1 2 3
| ListNode f = new ListNode(); f.next = c.next; c.next = f;
|
性能分析
- 数组长度固定,无法修改。
- 链表长度不固定,可以动态增删。