迭代和递归的特点，并比较优缺点：
（1）定义：
程序调用自身称为递归。
利用变量的原值推出新值称为迭代。
（2）优缺点
递归
优点：大问题转化为小问题，可以减少代码量，同时代码精简，可读性好；
缺点：就是递归调用浪费了空间，而且递归太深容易造成堆栈的溢出。
迭代
优点：代码运行效率好，因为时间只因循环次数增加而增加，而且没有额外的空间开销；
缺点：代码不如递归简洁
排序算法
稳定的排序方式：冒泡排序，归并排序，直接插入排序
快速排序：
思路：
1.从序列中挑出一个元素，作为"基准"(pivot).
2.把所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准的后面（相同的数可以到任一边），这个称为分区(partition)操作。
3.对每个分区递归地进行步骤1~2，递归的结束条件是序列的大小是0或1，这时整体已经被排好序了。
intPartition(intA[],int left, int right)// 划分函数{
int pivot = A[right];// 这里每次都选择最后一个元素作为基准
int tail = left -1; // tail为小于基准的子数组最后一个元素的索引
for(int i = left; i < right; i++)// 遍历基准以外的其他元素 {
if(A[i] <= pivot)// 把小于等于基准的元素放到前一个子数组末尾 {
Swap(A, ++tail, i);
}
}
Swap(A, tail +1, right);// 最后把基准放到前一个子数组的后边，剩下的子数组既是大于基准的子数组
// 该操作很有可能把后面元素的稳定性打乱，所以快速排序是不稳定的排序算法returntail +1;// 返回基准的索引}
voidQuickSort(intA[],int left, int right)
{
if(left >= right)
return;
int pivot_index = Partition(A, left, right);// 基准的索引
QuickSort(A, left, pivot_index -1);
QuickSort(A, pivot_index +1, right);
}
堆排序：
思路：父节点的值大于它子节点的值
1.由输入的无序数组构造一个最大堆，作为初始的无序区
2.把堆顶元素（最大值）和堆尾元素互换
3.把堆（无序区）的尺寸缩小1，并调用heapify(A, 0)从新的堆顶元素开始进行堆调整
4.重复步骤2，直到堆的尺寸为1
void Heapify(intA[],int i, int size)// 从A[i]向下进行堆调整{
int left_child =2* i +1;// 左孩子索引
int right_child =2* i +2;// 右孩子索引
int max = i;// 选出当前结点与其左右孩子三者之中的最大值if(left_child < size && A[left_child] > A[max])
max = left_child;
if(right_child < size && A[right_child] > A[max])
max = right_child;
if(max != i)
{
Swap(A, i, max); // 把当前结点和它的最大(直接)子节点进行交换
Heapify(A, max, size);// 递归调用，继续从当前结点向下进行堆调整 }
}intBuildHeap(intA[],int n)// 建堆，时间复杂度O(n){
int heap_size = n;
for(int i = heap_size /2-1; i >=0; i--)// 从每一个非叶结点开始向下进行堆调整
Heapify(A, i, heap_size);
return heap_size;
}voidHeapSort(intA[],int n)
{
int heap_size = BuildHeap(A, n);// 建立一个最大堆while(heap_size >1)// 堆（无序区）元素个数大于1，未完成排序 {
// 将堆顶元素与堆的最后一个元素互换，并从堆中去掉最后一个元素
// 此处交换操作很有可能把后面元素的稳定性打乱，所以堆排序是不稳定的排序算法
Swap(A,0, --heap_size);
Heapify(A, 0, heap_size);// 从新的堆顶元素开始向下进行堆调整，时间复杂度O(logn) }
}
归并排序：
思路：1452排序
先把1452分开，变为1 4 5 2，第一次结果为14，25，第二次排序结果为1245.递归方式
void MergeSortRecursion(intA[],int left, int right)// 递归实现的归并排序(自顶向下){
if(left == right)// 当待排序的序列长度为1时，递归开始回溯，进行merge操作return;
int mid = (left + right) /2;
MergeSortRecursion(A, left, mid);
MergeSortRecursion(A, mid +1, right);
Merge(A, left, mid, right);
}
void Merge(intA[],int left, int mid, int right)// 合并两个已排好序的数组A[left...mid]和A[mid+1...right]{
int len = right - left +1;
int*temp =ne wint[len];// 辅助空间O(n)int index =0;
int i = left;// 前一数组的起始元素int j = mid +1;// 后一数组的起始元素while(i <= mid && j <= right)
{
temp[index++] = A[i] <= A[j] ? A[i++] : A[j++];// 带等号保证归并排序的稳定性 }
while(i <= mid)
{
temp[index++] = A[i++];
}
while(j <= right)
{
temp[index++] = A[j++];
}
for(int k =0; k < len; k++)
{
A[left++] = temp[k];
}
}
单例模式：在内部创建一个实例，构造器全部设置为private，所有方法均在该实例上改动，在创建上要注意类的实例化只能执行一次，可以采用许多种方法来实现，如Synchronized关键字，或者利用内部类等机制来实现。
较为优良的双重锁机制：
public class Singleton {
private volatile static Singleton singleton;
private Singleton (){}
public static Singleton getSingleton() {
if (singleton == null) {
synchronized (Singleton.class) {
if (singleton == null) {
singleton = new Singleton();
}
}
}
return singleton;
} }
建造者模式： 1、需要生成的对象具有复杂的内部结构。 2、需要生成的对象内部属性本身相互依赖。
使用：一些基本部件不会变，而其组合经常变化的时候。
适配器模式：使用场景为有动机地修改一个正常运行的系统的接口，这时应该考虑使用适配器模式。
适配器模式的作用就是在原来的类上提供新功能。主要可分为3种：
类适配：创建新类，继承源类，并实现新接口，例如
class adapter extend soldClass implements newFunc{}
对象适配：创建新类持源类的实例，并实现新接口，例如
class adapter implements newFunc {private old Class oldInstance ;}
接口适配：创建新的抽象类实现旧接口方法。例如
abstract class adapter implement soldClassFunc {void newFunc();}
工厂模式：主要解决：主要解决接口选择的问题。何时使用：我们明确地计划不同条件下创建不同实例时。
装饰器模式：在不想增加很多子类的情况下扩展类。允许向一个现有的对象添加新的功能，同时又不改变其结构
interface Source{ void method();}
public class Decorator implements Source{
private Source source ;
public void decotate1(){
System.out.println("decorate");
}
@Override
public void method() {
decotate1();
source.method();
}
}
观察者模式：定义对象间的一种一对多的依赖关系，当一个对象的状态发生改变时，所有依赖于它的对象都得到通知并被自动更新。
场景：一个对象（目标对象）的状态发生改变，所有的依赖对象（观察者对象）都将得到通知，进行广播通知。
网友评论