(5)merge sort

1. 目录

本节介绍两个最经典的排序算法之一的归并排序(另外个自然是快速排序了)

2.basic merge sort

将数列分成两份分别排序,然后最后再合并;这种分治思想递归的使用,就是归并排序了。

2.1 基本过程

基本过程如下:

(4)elementary sort

1. 简介

本节主要讲元素的排序算法,目录如下

2. rules of the game

java中通过回调使用compareTo方法来达到比较的目的。

实数、字符串比较都满足一个全序关系:

(3)Stack and Queue

1. 介绍

因为已经学过数据结构相关的内容,这部分仅仅记录一些比较重要的。一些基本概念这里不再赘述。

2. 栈实现

实现上可以采用链表(Linked list)实现也可以采用数组(Array)实现

2.1 pop()函数实现时注意点

这里实现pop的时候,让出栈对象的引用指向NULL,方便GC对其回收或者重新分配

2.2 resizing arrays

方法一: ......

(2)Analysis of algorithms

1.算法分析基本步骤

Observations: 观察程序运行的特点(比如执行时间等)

Mathematical Models: 建立一些模型

使用算法理论分析

2. observations

3 SUM问题

给定N个不同的整数(N>=3),有多少种方式可以使得其中三个数字加起来为0

这个问题实际上在现实中有很多应用,例如在计算机几何学问......

(1)Union-Find

1. 介绍

本系列关于算法的笔记是记录自己学习Sedgewick的《算法》第四版的学习笔记。本节将介绍UNION-FIND的这个具体算法的例子来了解基本的算法设计和分析方法。

2.动态连接(dynamic connection)

这是一类问题模型,寻求连通性的。寻求某两个节点之间是否有通路。

可以运用在社交网络、计算机网络等。

2.1 解决步骤

分解成多个连接单元

节......