【专题】算法
一、排序
冒泡、选择、插入、快速、归并、堆排序
https://www.cnblogs.com/eniac12/p/5329396.html#s32
冒泡排序
- 分类：内部比较排序
- 最差时间复杂度：O(n^2)
- 最优时间复杂度：如果能在内部循环第一次运行时,使用一个旗标来表示有无需要交换的可能,可以把最优时间复杂度降低到O(n)
- 平均时间复杂度：O(n^2)
- 所需辅助空间：O(1)
- 稳定性：稳定
public static int[] bubbleSort(int[] array){
if (array == null || array.length <= 1) {
return array;
}
for (int i = 0; i < array.length - 1; i++) {
for (int j = 0; j < array.length-1-i; j++) {
if(array[j] > array[j+1]){
swap(array, j, j+1);
}
}
}
return array;
}
选择排序
// 分类 -------------- 内部比较排序
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- O(n^2)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 不稳定
public static int[] selectSort(int[] array){
if (array == null || array.length <= 1) {
return array;
}
for (int i = 0; i < array.length - 1; i++) {
int min = i;
for (int j = i+1; j < array.length; j++) {
if(array[min] > array[j]){
min = j;
}
}
swap(array,i,min);
}
return array;
}
插入排序
// 分类 ------------- 内部比较排序
// 最差时间复杂度 ---- 最坏情况为输入序列是降序排列的,此时时间复杂度O(n^2)
// 最优时间复杂度 ---- 最好情况为输入序列是升序排列的,此时时间复杂度O(n)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定
public static int[] insertSort(int[] array){
if (array == null || array.length <= 1) {
return array;
}
for (int j = 1; j < array.length; j++) {
int get = array[j];
int i = j-1;
while(i >= 0 && array[i] > get){
array[i+1] = array[i];
i--;
}
array[i+1] = get;
}
return array;
}
快速排序
// 分类 ------------ 内部比较排序
// 数据结构 --------- 数组
// 最差时间复杂度 ---- 每次选取的基准都是最大（或最小）的元素，导致每次只划分出了一个分区，需要进行n-1次划分才能结束递归，时间复杂度为O(n^2)
// 最优时间复杂度 ---- 每次选取的基准都是中位数，这样每次都均匀的划分出两个分区，只需要logn次划分就能结束递归，时间复杂度为O(nlogn)
// 平均时间复杂度 ---- O(nlogn)
// 所需辅助空间 ------ 主要是递归造成的栈空间的使用(用来保存left和right等局部变量)，取决于递归树的深度，一般为O(logn)，最差为O(n)
// 稳定性 ---------- 不稳定
public static int[] quickSort(int[] array, int start, int end){
if (array == null || array.length <= 1) {
return array;
}
if (start >= end){
return array;
}
int pivotIndex = partArray(array,start,end);
quickSort(array,start,pivotIndex-1);
quickSort(array,pivotIndex+1,end);
return array;
}
private static int partArray(int[] array, int start, int end){
int pivot = array[end];
int tail = start;
for (int i = start; i < end; i++) {
if (array[i] <= pivot){
swap(array,tail++,i);
}
}
swap(array,tail,end);
return tail;
}
二、查找
keng
三、实战中遇到的题目
- 一个小球从100米空中落下，每次反弹一半高度，问小球第10次落地时总共经过多少米？
要点解析：
1、第一次落地走的路程是单程，之后的落地路程是往返双程；
2、每次反弹高度减半，路程可能出现小数，所以用float类型定义路程变量；
// 递归解法
public static float sumPath(int sumCount, int curCount, float curHeight){
if(sumCount <= 0 || curCount <= 0 || curHeight <= 0){
return 0;
}
//第一次落地是单程
int n = (curCount==1) ? 1 : 2;
if (sumCount < curCount){
return 0;
} else if (sumCount == curCount){
return n * curHeight;
} else {
return n * curHeight + sumPath(sumCount, curCount+1, curHeight/2);
}
}
// 循环解法
public static float sumPath(int sumCount, float initHeight){
if(sumCount <= 0 || initHeight <= 0){
return 0;
}
float sum = 100;
float hn = initHeight / 2;
for (int i = 1; i < sumCount; i++) {
sum += (hn * 2);
hn /= 2;
}
return sum;
}
- 有一对兔子，从出生后第三个月起每个月都生一对兔子，小兔子长大后到第三个月后每个月又生一对兔子，假如兔子都不死，问第13个月的兔子总量是多少？
要点解析：
解算法题主要是找到规律，这道题目可以先穷举出前几项观察规律，1、1、2、3、5、8... ，仔细观察会发现就是一个斐波拉切数组。
public static int sum (int month){
if(month < 0){
return 0;
}else if(month < 2){
return 1;
}else{
return sum(month-1) + sum(month-2);
}
}
- 判断链表是否有环。
要点解析：
1、快慢指针法：慢指针前进1，快指针前进2，如果相遇则有环；
2、在慢指针到底循环点之前一定会相遇；
3、寻找循环交叉点，从头指针到交叉点距离和从相遇点到交叉点距离相等。
public static boolean isLoop(Node head){
if (head == null) {
return false;
}
boolean isLoop = false;
Node slowPoint = head;
Node fastPoint = head;
while (fastPoint != null && fastPoint.next != null){
slowPoint = slowPoint.next;
fastPoint = fastPoint.next.next;
if(slowPoint == fastPoint){
return true;
}
}
return isLoop;
}
