原型模式

原型模式介绍

原型模式是一个创建型的模式。原型二字即可表明该模式有一个样板实例,用户可以从这个样板的对象中复制一个与该对象内部属性一致的对象,也就是我们所说的克隆。被复制的实例就是我们所称的“原型”,这个原型是可定制的。原型模式多用于创建复杂的或者构造耗时的实例,因为这种情况下,复制一个已经存在的实例可以使程序运行更高效。

Read more   2019/5/23 posted in  算法

Builder模式(建造者模式)

Builder模式介绍

  • 建造者模式(Builder Pattern)也叫做生成器模式,Builder Design pattern 是一种创造型模式,Builder模式所解决的问题与对象的创建有关。它允许用户在不知道内部构建细节的情况下,可以更精细的控制对象的构造流程,Builder模式是为了将构造复杂对象的过程和他的部件解耦。Android 中我们最常用的Builder模式是AlterDialog.Builder。
  • Builder 模式通常是以静态内部类的形式实现。
Read more   2019/5/23 posted in  算法

单例模式

单例模式的意义

单例模式是最简单的设计模式之一,属于创建模式,它提供了一种创建对象的方式,确保只有单个对象被创建。这种设计模式主要目的是使整个系统中只能出现一个类的实例,即一个类只有一个对象。如果某个类,创建时需要消耗很多资源,即new出这个类的代价很大;或者是这个类占用很多内存,如果创建太多这个类实例会导致内存占用太多,就需要使用单例模式。

  • 优点
    • 由于频繁使用对象,可以省略创建对象所花费的时间,尤其是对于重量级的对象而言,是很重要的。
    • 由于不需要频繁的创建对象,所以GC的压力变轻了,不需要频繁的分配资源和释放资源。
  • 缺点
    • 简单的单例模式设计都很简单,但是复杂的单例模式需要考虑线程安全等并发问题,引入了部分复杂度
Read more   2019/5/12 posted in  算法

设计模式全面解析

为什么要学习设计模式

首先,我们为什么要学习设计模式。主要是这些模式是前人总结的经验,使用这些模式能让我们的程序更健壮、更稳定、容易扩展等等优点。在编写面向对象程序时,我们需要遵循以下6个原则,能让我们的程序维护起来更轻松~

Read more   2019/5/12 posted in  算法

排序算法

前言

  • 现在排序算法经过长时间的演变,发展处各种不同的排序算法。不得不说在日常开发以及日后的研究生活中还是比较常见以及使用的。再此对各种排序算法做一个记录,方便日后比较和查阅。

  • 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。

  • 当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序序。

  • 快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;

直接插入排序(插入排序)

  • 介绍
    它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。
  • 步骤
    1. 从第一个元素开始,该元素可以认为已经被排序
    2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
    3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
    4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
    5. 将新元素插入到该位置中
    6. 重复步骤2
  • 最优复杂度:当输入数组就是排好序的时候,复杂度为O(n),而快速排序在这种情况下会产生O(n2)的复杂度。
  • 最差复杂度:当输入数组为倒序时,复杂度为O(n2)
  • 比较适合用于“少量元素的数组”。

  • 代码

import java.util.*;

class Untitled {
    public static void main(String[] args) {
        Random ran = new Random();
        int[] sort = new int[10];
        for (int i = 0;i < 10;i++) {
            sort[i] = ran.nextInt(50);
        }
        System.out.println("排序前的数组为");
        for (int i : sort) {
            System.out.print(i + " ");
        }
        System.out.println();
        directInsertSort(sort);
        System.out.println("排序后的数组为");
        for (int i : sort) {
            System.out.print(i + " ");
        }
    }
    /** 
     * 直接插入排序 
     *  
     * @param sort 
     */
    private static void directInsertSort(int[] sort) {  
        for (int i = 1; i < sort.length; i++) {  
            int index = i - 1;  
            int temp = sort[i];  
            while (index >= 0 && sort[index] > temp) {  
                sort[index + 1] = sort[index];  
                index--;  
            }  
            sort[index + 1] = temp;  
        }  
    }
}
  • 示例

希尔排序

  • 介绍

    希尔排序,也称递减增量排序算法,是插入排序的一种高速而稳定的改进版本。

    希尔排序是基于插入排序的以下两点性质而提出改进方法的:

    1. 插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率
    2. 但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位
  • 步骤

    1. 选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;
    2. 按增量序列个数k,对序列进行k 趟排序;
    3. 每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。
  • 示例

  • 排序效果

冒泡排序

  • 介绍

    冒泡排序(Bubble Sort,台湾译为:泡沫排序或气泡排序)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

  • 步骤

    1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
    2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
    3. 针对所有的元素重复以上的步骤,除了最后一个。
    4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
  • 代码

import java.util.*;
class test1 {
    public static void main(String[] args) {
        Random ran = new Random();
        int[] sort = new int[10];
        for (int i = 0;i < 10;i++) {
            sort[i] = ran.nextInt(50);
        }
        System.out.println("排序前的数组为");
        for (int i : sort) {
            System.out.print(i + " ");
        }
        System.out.println();
        buddleSort(sort);
        System.out.println("排序后的数组为");
        for (int i : sort) {
            System.out.print(i + " ");
        }
    }
    
    public static void buddleSort(int[] sort){
        for (int i = 1;i < sort.length;i++) {
            for (int j = 0;j < sort.length - i;j++) {
                if (sort[j] > sort[j+1]) {
                    int temp = sort[j];
                    sort[j] = sort[j + 1];
                    sort[j + 1] = temp;
                }
            }
        }
    }
}
  • 示例

  • 排序效果

选择排序

  • 介绍

    选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾。以此类推,直到所有元素均排序完毕。

  • 步骤

    1. 从n个记录中找出关键码最小的记录与第一个记录交换;
    2. 从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换;
    3. 以此类推.....
    4. 第i 趟,则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换;
    5. 直到整个序列按关键码有序。
  • 代码

import java.util.*;

class Untitled {
    public static void main(String[] args) {
        Random ran = new Random();
        int[] sort = new int[10];
        for (int i = 0;i < 10;i++) {
            sort[i] = ran.nextInt(50);
        }
        System.out.println("排序前的数组为");
        for (int i : sort) {
            System.out.print(i + " ");
        }
        System.out.println();
        selectSort(sort);
        System.out.println("排序后的数组为");
        for (int i : sort) {
            System.out.print(i + " ");
        }
    }
    
    public static void selectSort(int[] sort){
        for (int i = 0; i < sort.length - 1;i++) {
            for (int j = i + 1;j < sort.length;j++) {
                if (sort[j] < sort[i]) {
                    int temp = sort[j];  
                    sort[j] = sort[i];  
                    sort[i] = temp;
                }
            }
        }
    }
}
  • 示例

  • 排序效果

快速排序

  • 介绍

    快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来,且在大部分真实世界的数据,可以决定设计的选择,减少所需时间的二次方项之可能性。

  • 步骤

    1. 从数列中挑出一个元素,称为 “基准”(pivot)
    2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
    3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
  • 代码

import java.util.*;

class Untitled {
    public static void main(String[] args) {
        Random ran = new Random();
        int[] sort = new int[10];
        for (int i = 0;i < 10;i++) {
            sort[i] = ran.nextInt(50);
        }
        System.out.println("排序前的数组为");
        for (int i : sort) {
            System.out.print(i + " ");
        }
        System.out.println();
        quickSort(sort, 0, sort.length - 1);
        System.out.println("排序后的数组为");
        for (int i : sort) {
            System.out.print(i + " ");
        }
    }
    
    public static void quickSort(int[] sort, int start, int end) {  
            // 设置关键数据key为要排序数组的第一个元素,  
            // 即第一趟排序后,key右边的数全部比key大,key左边的数全部比key小  
            int key = sort[start];  
            // 设置数组左边的索引,往右移动判断比key大的数  
            int i = start;  
            // 设置数组右边的索引,往左移动判断比key小的数  
            int j = end;  
            // 如果左边索引比右边索引小,则还有数据没有排序  
            while (i < j) {  
                while (sort[j] > key && j > start) {
                    j--;
                }
                while (sort[i] < key && i < end) {
                    i++;
                }
                if (i < j) {
                    int temp = sort[i];
                    sort[i] = sort[j];
                    sort[j] = temp;
                }
            }
            // 如果左边索引比右边索引要大,说明第一次排序完成,将sort[j]与key对换
            // 即保持了key左边的数比key小,key右边的数比key大
            if (i > j) {
                int temp = sort[j];
                sort[j] = sort[start];
                sort[start] = temp;
            }
            //递归调用
            if (j > start && j < end) {
                quickSort(sort, start, j - 1);
                quickSort(sort, j + 1, end);
            }
        }
}
  • 示例

    • 一趟排序的过程
    • 排序的全过程
  • 排序效果

归并排序

  • 介绍

    归并排序(Merge sort,台湾译作:合并排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用

  • 步骤

    1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
    2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置
    3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
    4. 重复步骤3直到某一指针达到序列尾
    5. 将另一序列剩下的所有元素直接复制到合并序列尾
  • 示例

  • 排序效果

堆排序

  • 介绍

    堆积排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆性质:即子结点的键值或索引总是小于(或者大于)它的父节点。由堆的定义可以看出,堆顶元素(即第一个元素)必为最小项(小顶堆)。若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点的值均不大于(或不小于)其子女的值,根结点(堆顶元素)的值是最小(或最大)的。

    1. 大顶堆序列:(96, 83,27,38,11,09)
    2. 小顶堆序列:(12,36,24,85,47,30,53,91)
      初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树(一维数组存储二叉树),调整它们的存储序,使之成为一个堆,将堆顶元素输出,得到n 个元素中最小(或最大)的元素,这时堆的根节点的数最小(或者最大)。然后对前面(n-1)个元素重新调整使之成为堆,输出堆顶元素,得到n 个元素中次小(或次大)的元素。依此类推,直到只有两个节点的堆,并对它们作交换,最后得到有n个节点的有序序列。称这个过程为堆排序。
  • 步骤

    • 调整小顶堆的方法
      1. 设有m 个元素的堆,输出堆顶元素后,剩下m-1 个元素。将堆底元素送入堆顶(最后一个元素与堆顶进行交换),堆被破坏,其原因仅是根结点不满足堆的性质。
      2. 将根结点与左、右子树中较小元素的进行交换。
      3. 若与左子树交换:如果左子树堆被破坏,即左子树的根结点不满足堆的性质,则重复方法(2).
      4. 若与右子树交换,如果右子树堆被破坏,即右子树的根结点不满足堆的性质。则重复方法(2).
      5. 继续对不满足堆性质的子树进行上述交换操作,直到叶子结点,堆被建成。
    • n个元素初始建堆的过程(建堆方法:对初始序列建堆的过程,就是一个反复进行筛选的过程。)
      1. n 个结点的完全二叉树,则最后一个结点是第

        个结点的子树。
      2. 筛选从第
        个结点为根的子树开始,该子树成为堆。
      3. 之后向前依次对各结点为根的子树进行筛选,使之成为堆,直到根结点。
      4. 如图建堆初始过程:无序序列:(49,38,65,97,76,13,27,49)
  • 排序效果

2015/7/22 posted in  算法