0%

排序算法之堆排序

堆排序是一种树形选择排序方法,它的特点是:在排序的过程中,将array[0,…,n-1]看成是一颗完全二叉树的顺序存储结构,利用完全二叉树中双亲节点和孩子结点之间的内在关系,在当前无序区中选择关键字最大(最小)的元素。

  1. 若array[0,…,n-1]表示一颗完全二叉树的顺序存储模式,则双亲节点指针和孩子结点指针之间的内在关系如下

    任意一节点指针 i:
    父节点:i==0 ? null : (i-1)/2
    左孩子:2i + 1
    右孩子:2
    i + 2

  2. 堆的定义:n个关键字序列array[0,…,n-1],当且仅当满足下列要求:(0 <= i <= (n-1)/2)

    • array[i] <= array[2i + 1] 且 array[i] <= array[2i + 2]; 称为小根堆;
    • array[i] >= array[2i + 1] 且 array[i] >= array[2i + 2]; 称为大根堆;
  3. 建立大根堆:

    n个节点的完全二叉树array[0,…,n-1],最后一个节点n-1是第(n-1-1)/2个节点的孩子。对第(n-1-1)/2个节点为根的子树调整,使该子树称为堆。

    对于大根堆,调整方法为:若【根节点的关键字】小于【左右子女中关键字较大者】,则交换。

    之后向前依次对各节点((n-2)/2 - 1)~ 0为根的子树进行调整,看该节点值是否大于其左右子节点的值,若不是,将左右子节点中较大值与之交换,交换后可能会破坏下一级堆,于是继续采用上述方法构建下一级的堆,直到以该节点为根的子树构成堆为止。

    反复利用上述调整堆的方法建堆,直到根节点。

阅读全文 »

排序算法之快速排序

基于分治的思想,是冒泡排序的改进型。

首先在数组中选择一个基准点(该基准点的选取可能影响快速排序的效率,后面讲解选取的方法),然后分别从数组的两端扫描数组,设两个指示标志(lo指向起始位置,hi指向末尾),

  1. 首先从后半部分开始,如果发现有元素比该基准点的值小,就交换lo和hi位置的值
  2. 然后从前半部分开始扫秒,发现有元素大于基准点的值,就交换lo和hi位置的值,如此往复循环
  3. 直到lo>=hi,然后把基准点的值放到hi这个位置。一次排序就完成了
  4. 以后采用递归的方式分别对前半部分和后半部分排序,当前半部分和后半部分均有序时该数组就自然有序了
阅读全文 »

排序算法之插入排序

  1. 从第一个元素开始,该元素可以认为已经被排序
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置,将新元素插入到该位置中

简单插入排序的时间复杂度也是O(n^2)

阅读全文 »

排序算法之选择排序

在未排序序列中找到最小元素,并与待排序列的首位进行交换。
选择排序可以看成冒泡排序的优化,因为其目的相同,只是选择排序只有在确定了最小数的前提下才进行交换,大大减少了交换的次数。

选择排序的时间复杂度为O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class SelectSort {
public static void selectSort(int [] arr) {
if(arr.length == 0 || arr == null)
return ;
int minIndex = 0;
for(int i = 0; i < arr.length-1; i++) {
minIndex = i;
for (int j = i+1; j < arr.length-i-1; j++) {
if (arr[minIndex] > arr[j])
minIndex = j;
}
if(minIndex != i)
swap(arr, i, minIndex);
}
}

public void swap(int[] arr, int a, int b) {
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
}

排序算法之冒泡排序

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

NIO

NIO概述

Java NIO 由以下几个核心部分组成:

  • Channel
  • Buffer
  • Selector

虽然 Java NIO 中除此之外还有很多类和组件,但在我看来,Channel,Buffer 和 Selector 构成了核心的 API。其它组件,如 Pipe 和 FileLock,只不过是与三个核心组件共同使用的工具类。

Java NIO笔记

NIO概述

Java NIO 由以下几个核心部分组成:

  • Channel
  • Buffer
  • Selector

虽然 Java NIO 中除此之外还有很多类和组件,但在我看来,Channel,Buffer 和 Selector 构成了核心的 API。其它组件,如 Pipe 和 FileLock,只不过是与三个核心组件共同使用的工具类。

阅读全文 »

#Mac安装配置MPV播放器

OS X 上常见的视频播放器有,QuickTime,MplayerX,VLC,收费的 Movist等,但都有各自的缺点。我理想的播放器应该有这样几个特点:

  1. 常见格式都支持。
  2. 画面质量还可以,不掉帧不模糊。
  3. 字幕支持全面。
  4. 省电 (躺床上就不插电源了)。
阅读全文 »