数据结构(七)树和二叉树

什么是树

我们知道,链表是一种线性递归的数据结构。前一个结点指向后一个结点,线性地链接起来。树跟链表类似,只不过树的结点与结点之间,不再是单个线性地链接,而是一个结点可以指向多个其他结点。

阅读更多

数据结构(六)查找算法

什么是查找

有时候我们需要搜索信息,例如,在数组中找出某个元素,或者找出某个集中是否有某个对象。我们把寻找目标信息的过程,叫做查找。

顺序查找二分查找 是查找的基本方法。

当我们需要高效查找时,我们可以用 符号表(或者叫字典、索引) 来表示一张抽象的表格。符号表(symbol table)是一种存储键值对的数据结构。目的是将一个键和一个值联系起来,使我们可以通过键找到值。这种数据结构包括两种操作:

  1. 插入(put):将一组新的键值对存入表中
  2. 查找(get):根据给定的键,找到相应的值

生活中不乏符号表的例子:

  1. 字典:通过单词找到释义
  2. 网络搜索:通过关键字找到网页
  3. 账户管理:通过账号找到交易详情

在计算机科学中,有三种经典的高效符号表:

  1. 二叉查找树(或者叫二叉搜索树,Binary Search Tree, BST)
  2. 红黑树(基于平衡查找树, AVL)
  3. 哈希表(或者叫散列表)
阅读更多

数据结构(五)优先队列和堆排序

有时候我们会收集一些元素,然后处理当前键值最大的元素。然后再收集更多,再处理。例如,在手机来电、短信、游戏三个程序中,来电的优先级是最高的,我们总希望先处理来电请求。

满足这种场景的数据结构,需要支持两种操作:删除最大(或最小)元素插入元素。这种数据类型,就叫优先队列。优先队列也是一种队列,但是跟前面提到的先进先出队列不同,优先队列的“出”,是根据优先级来的(最大或最小的先出)。

priorityqueue

优先队列在很多地方有应用,例如:

  • 数据压缩:哈夫曼编码算法
  • 最短路径算法:Dijkstra算法
  • 最小生成树算法:Prim算法
  • 事件驱动仿真:顾客排队算法
  • 选择问题:查找第k个最小元素
阅读更多

漫谈递归和迭代

兔子问题

今天看到一个题目

有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子对数为多少?

我一开始的解法是这样的:

1
2
3
4
5
6
7
8
9
10
11
12
public static void rabbit2(){
int last_month_num = 0;
int current_month_num = 1;
int next_month_num = last_month_num + current_month_num;

for (int months = 1; months <= 12; months++) {
current_month_num = next_month_num;
System.out.printf("第 %d 个月兔子的对数为 %d\n",months,current_month_num);
next_month_num = current_month_num + last_month_num;
last_month_num = current_month_num;
}
}

我的想法是,根据题意,可以得出规律: 1、1、2、3、5、8、13…

总结规律:前两个月的数量和等于下个月

阅读更多

数据结构(四)快速排序算法

快速排序简介

在归并排序中,我们将一个数组分为两半,每一半又再分为两半,分到最后再一步步归并。

快速排序和归并排序是互补的:快速排序先选定一个元素,比这个元素小的放在左边,比这个元素大的放在右边,每一半,也都选一个元素,比它小的放左边,比它大的放右边。不断地选、分下去。

阅读更多

数据结构(三)归并排序算法

一、归并排序简介

要将一个有16个元素的数组排序,可以先将它分成两半,每一半8个元素,分别排序,然后将排序好的两个8元素的结果归并起来。

要将一个有8个元素的数组排序,可以先将它分成两半,每一半4个元素,分别排序,然后将排序好的两个4元素的结果归并起来。

要将一个有4个元素的数组排序,可以先将它分成两半,每一半2个元素……

基于这种思想的排序,就是归并排序。

MergeSort1

MergeSort2

阅读更多

数据结构(二)算法的复杂度、简单排序算法

前言:算法的复杂度

在讨论数据结构和算法时,我们通常用算法的复杂度来描述一个算法的好坏,复杂度包括:时间复杂度空间复杂度。计算机本质上是一个状态机,内存里的数据构成了当前的状态,CPU利用当前的状态计算出下一个状态。所谓的空间复杂度就是为了支持你的计算所必需存储的状态最多有多少,所谓时间复杂度就是从初始状态到达最终状态中间需要多少步!

时间复杂度

算法的时间复杂度,也就是算法的时间量度,记作:T(n) = O(f(n))。它表示随问题规模 n 的增大,算法执行时间的增长率和 f(n) 的增长率相同,称为算法的渐近时间复杂度,简称为时间复杂度。其中 f(n) 是规模 n 的某个函数。

如何推导时间复杂度

  1. 用常数 1 取代运行时间中的所有加法常数。
  2. 在修改后的运行次数函数中,只保留最高阶项。
  3. 如果最高阶项存在,且不是 1 ,则去除与这个项相乘的常数。

例如:

1
2
3
int sum = 0, n = 100;   // 执行 1 次
sum = (1 + n) * n / 2; // 执行 1 次
printf("%d", sum); // 执行 1 次

这个算法的运行次数函数是 f(n) = 3。根据推导规则,第一步把常数项 3 改为 1。第二步保留最高阶项,它没有最高阶项,所以这个算法的时间复杂度为 T(n) = O(1)

常数阶

当 n = 1 时,算法执行次数为 3, 当 n = 100 时,算法的执行次数还是 3,所以我们可以看出这个算法的执行次数与 n 的规模没关系。我们把这种与问题的大小(n 的大小)无关,执行时间恒定的算法,叫作常数阶。

线性阶

下面这段代码的时间复杂度为 T(n) = O(n),因为循环体中的代码必须要执行 n 次。

1
2
3
for (i = 0; i < n; i++) {
/* 时间复杂度为 O(1) 的程序步骤序列 */
}

对数阶

1
2
3
4
5
int count = 1;
while (count < n) {
count = count * 2;
/* 时间复杂度为 O(1) 的程序步骤序列 */
}

由于每次 count 乘以 2 以后,就越来越接近于 n,也就是说有多少个 2 相乘后大于 n,则会退出循环。由2^x = n 得到 x = log2n。所以这个算法的时间复杂度为 T(n) = O(logn)

平方阶

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 例1
int i, j;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
/* 时间复杂度为 O(1) 的程序步骤序列 */
}
}

// 例2
int i, j, m;
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
/* 时间复杂度为 O(1) 的程序步骤序列 */
}
}

在 例1 中内循环时间复杂度为O(n),而对于外层的循环,不过是这个内循环再循环 n 次。所以这段代码的时间复杂度为 O(n^2)

在 例2 中,时间复杂度就变为 O(m^n)

常见的时间复杂度耗费时间

从小到大依次是:

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

空间复杂度

算法的空间复杂度通过计算算法所需的存储空间实现,算法空间复杂度的计算公式:

1
S(n) = O(f(n))

其中 n 为问题的规模,f(n)为语句关于 n 所占存储空间的函数。

复杂度分析的主要方法

  1. 迭代:级数求和
  2. 递归:递归跟踪 + 递推方程

猜测 + 验证


一、选择排序(Selection Sort)

选择排序介绍

选择排序是一种最简单的排序算法,它的算法步骤如下:

  1. 找到数组中最小的元素
  2. 将它和数组的第一个元素交换位置(如果相同,也交换)
  3. 在剩下的元素中找到最小的元素
  4. 将它和数组的第二个元素交换位置
  5. 重复。。

选择排序交换的总次数为N,算法的效率取决于比较的次数。

特点:

  • 运行时间和输入无关、移动数据是最少的
  • 选择排序是不稳定的排序方法
  • 对于长度为 N 的数组,选择排序需要大约 N²/2次比较和 N 次交换
  • 时间复杂度 O(n^2)

算法2.1 选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void selectSort(int[] arr){

int size = arr.length;

for (int i = 0; i < size; i++) {
int min = i;
// 第二个for循环找出最小元素
for (int j = i; j < size; j++) {
if (arr[j] < arr[min]) min = j;
}
Swap.swap(arr, min, i);
}

}

二、插入排序(Insertion Sort)

插入排序介绍

插入排序,将数插入到其他已经有序的数中的适当位置。为了给要插入的数腾出空间,我们需要将其余所有元素在插入之前都向右移动一位。

插入排序所需的时间取决于输入中元素的初始顺序。(原始数据越接近有序,越快)

命题:对于随机排列的长度为 N 且主键不重复的数组,平均情况下插入排序需要约 N²/4 次比较以及 N²/4 次交换。最坏情况下需要 约 N²/2 次比较以及 N²/2 次交换,最好情况下需要 N-1 次比较 和 0 次交换。

时间复杂度:O(n^2)

算法2.2 插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* 原理:插入排序,将数插入到其他已经有序的数中的适当位置
* 思路:从 a[0] 开始,a[0] 已经是第一个,所以不用动
* a[1] 与 a[0] 比较 -> 得出顺序
* a[2] 与 a[1] a[0] 比较 -> a[2] 先与 a[1] 比较 ,如果 a[2] 比 a[1] 小,则交换, 然后 a[1] 与 a[0] 比较
* a[3] 与 a[2] a[1] a[0] 比较 -> 插入适当位置
* ...
*/
private static void insertSort(int[] arr){
for (int i = 1; i < arr.length; i++) {
for (int j = i; j > 0 && arr[j] < arr[j-1]; j--) {
Swap.swap(arr, j, j-1);
}
}
}

三、希尔排序(Shell Sort)

希尔排序介绍

在插入排序和选择排序中,由于它们只能交换相邻的元素,如果有位于数组起始的大元素,则需要多次遍历才能交换到队尾,很不划算。希尔排序以更大的间隔来比较和交换元素,这样,大元素在交换的时候,可以向右移动不止一个位置。

希尔排序只需要在插入排序的代码中将移动的元素距离由1改为h即可。

希尔排序依赖于间隔(step)的选取。

算法2.3 希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Shell {
public static void sort(Comparable[] a){
int N = a.length;
int h = 1;
while(h < N/3) h = 3*h + 1; // 1,4,13,40,121,364,1093...

//将数组变为h有序
while (h >= 1){
//将a[i] 插入到 a[i-h]、a[i-2h]、a[i-3h]...之中
for (int i = h; i < N ; i++) {
for (int j = i; j > h && less(a[j],a[j-h]); j-=h) {
exch(a, j, j-h);
}
}
h = h/3;
}
}
}

四、冒泡排序

比较相邻元素,大的放右边

要点:第一躺结束后,最右元素一定是最大的,因此第二趟最右元素不参与,即 size - i - 1

时间复杂度:O(n^2)

1
2
3
4
5
6
7
8
9
10
11
public static void bubbleSort(int[] arr){

int size = arr.length;

for (int i = 0; i < size; i++) {
// 第一躺结束后,最右元素一定是最大的,因此第二趟最右元素不参与,即 size - i - 1
for (int j = 0; j < size - i - 1; j++) {
if (arr[j] > arr[j+1]) Swap.swap(arr, j, j+1);
}
}
}

数据结构(一)数据抽象、数组、链表

数据抽象

在开始谈数据结构之前,先聊一聊什么是数据抽象抽象数据类型(ADT)

数据类型是指 一组值一组对这些值的操作 的集合,Java中有多种 原始数据类型,如int。int是 -2^312^31 - 1 之间的这些整数值,以及加、减、乘、除等这些操作的集合。理论上所有程序只需要使用这些原始数据类型(int double char等)即可,但如果我们能把原始数据类型抽象成更高级的数据类型(string queue stack等),无疑会更加方便程序的编写。

我们把定义和使用我们自己的数据类型的这个过程,叫做数据抽象。

抽象数据类型(ADT) 是一种能够对使用者隐藏数据表示的数据类型。它将数据和函数的实现关联,并将数据的表示方式隐藏起来。我们在使用抽象数据类型时,主要关注如何操作而不关心数据本身是怎么表示的。也就是说,使用一个抽象数据类型,并不需要了解其实现细节。

ADT

阅读更多
Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×