算法第二章 排序

算法第二章 排序

第二章 排序

待排序的元素需要实现 Java 的 Comparable 接口,该接口有 compareTo() 方法,可以用它来判断两个元素的大小关系。

定义算法模板类API

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public abstract class Example {

/**
* 具体排序算法实现
*/
public abstract void sort(Comparable[] a);

/**
* 对元素进行比较
* @return first < second ? true : false
*/
public static boolean less(Comparable first, Comparable second) {
return first.compareTo(second) < 0;
}

/**
* 把两个元素交换位置
*/
public static void exch(Comparable[] a, int i, int j) {
Comparable tem = a[i];
a[i] = a[j];
a[j] = tem;
}

/**
* 返回序列是否有序(asc)
*/
public static boolean isSorted(Comparable[] a) {
for (int i = 1; i < a.length; i++) {
if (less(a[i], a[i - 1])) {
// 后面的元素 < 前面的元素 不是升序排列 返回false
return false;
}
}
return true;
}

public static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
StdOut.print(a[i] + " ");
}
StdOut.println();
}
}

选择排序

首先在数组中找到最小的元素,将其和第一个元素交换;然后继续在第一个元素之后的元素中寻找最小元素,将其和第二个元素交换… 循环往复直到将整个数组排序。

  • 外循环遍历数组的每个当前元素
  • 内循环遍历当前元素之后的所有元素寻找最小值

算法分析

优点:数据移动次数最少,选择排序的交换次数和数组长度N成线性关系,其他排序算法不具备该特征。

缺点:运行时间与输入(整个序列的值)无关,一个值相同的或有序的序列和一个随机无序的序列进行排序的时间一样长。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Selection extends Example {
@Override
public void sort(Comparable[] a) {
int N = a.length;
for (int i = 0; i < N; i++) {
int minIndex = i;
for (int j = i + 1; j < N; j++) {
if (less(a[j], a[minIndex])) {
minIndex = j; // 如果后续元素小于最小元素,把后续元素索引赋给最小元素索引。
}
exch(a, i, minIndex); // 交换原最小元素与新最小元素位置
}
}
}
public static void main(String[] args) {
String[] a = new In().readAllStrings();
new Selection().sort(a);
assert isSorted(a); // 验证:确认排序后的算法是有序的,当序列元素相同时无法通过验证。
show(a);
}
}

插入排序

将当前元素插入到当前元素之前的合适位置

首先从数组的第二个元素(目标元素)开始,当目标元素小于前面的元素,交换两者位置(否则不变);然后目标元素变为第三个元素,将其与第二个元素比较,若小则交换位置(此时目标元素索引为1),再将其与第一个元素对比,循环往复…

  • 外循环遍历每一个需要插入的目标元素
  • 内循环将目标元素与其左边的每一个元素对比、交换位置,直至目标元素被插入到了合适的位置。
  • 目标元素(a[i])从左到右移动时,其左侧的元素始终时有序的,当其移动到了最右边,数组也完成了排序。

算法分析

插入排序所需的时间取决于数组中元素的初始位置。因为当元素有序时不会进行交换,对于一个元素很大的且元素有序(或接近有序)的序列进行排序会比随机顺序的序列进行排序要快得多。

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Insertion extends Example {
@Override
public void sort(Comparable[] a) {
int N = a.length;
for (int i = 1; i < N; i++) {
// 将当前元素 a[i] 与 其左边的所有元素对比、交换位置
for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
// 后面的元素比前面的元素小才进行排序
exch(a, j, j - 1);
}
}
}
}

大幅度提高插入排序的速度,只需要在内循环中将较大的元素向右移动而不总是交换两个元素(这样访问数组的次数会减半),实现见 练习

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Ex25 extends Example {
public void sort(Comparable[] a) {
int n = a.length;
for (int i = 1; i < n; i++) {
Comparable target = a[i]; // 保存目标元素的值
int j; // 保存目标元素应该插入的位置
for (j = i; j > 0 && less(target, a[j - 1]); j--) {
a[j] = a[j - 1]; // 前驱元素后移
}
a[j] = target;
}
}
}

选择排序与插入排序比较

从直观上来说:

  • 选择排序不会访问索引左侧的元素(每次都是从目标元素的索引右边遍历所有元素取最小值进而与目标元素交换位置)
  • 插入排序不会访问索引右侧的元素(每次都是目标元素与其左边的每一个元素做对比进而交换位置)

首先规定输入模型:数组中的元素随机排序,且主键值不重复。

速度对比:

  • 1000条数据排序100次,选择排序花费0.4s,插入排序花费0.1s;
  • 10000条数据排序100次,选择排序花费43.6s,插入排序花费10.2s;

结论:

对于随机排序的无重复主键,插入排序和选择排序的运行时间都是平方级别的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class SortCompare {
public static double time(String alg, Comparable[] a) {
StopWatch watch = new StopWatch();
if (alg.equals("Insertion")) {
new Insertion().sort(a);
}
if (alg.equals("Selection")) {
new Selection().sort(a);
}
return watch.elapsedTime();
}

//使用alg算法将长度为N的数组排序T次
public static double timeRandomInput(String alg, int N, int T) {
double total = 0.0;
Double[] a = new Double[N]; // 目标数组
for (int t = 0; t < T; t++) {
for (int i = 0; i < N; i++) {
a[i] = StdRandom.uniform(); // 生成随机值
}
total += time(alg, a); // 计算T次时间总和
}
return total;
}

public static void main(String[] args) {
String alg1 = args[0];
String alg2 = args[1];
int N = Integer.parseInt(args[2]);
int T = Integer.parseInt(args[3]);
double t1 = timeRandomInput(alg1, N, T); // 算法1的总时间
double t2 = timeRandomInput(alg2, N, T); // 算法2的总时间
StdOut.printf("the %s algorithm takes %.1f seconds.\n", alg2, t2);
StdOut.printf("the %s algorithm takes %.1f seconds.\n", alg1, t1);
}
}

希尔排序

希尔排序是插入排序的增强版,是为了改进插入排序对于处理大规模乱序数组排序速度过慢的问题。实质上是分组插入排序,该方法又称缩小增量排序

该方法的基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高的,因此希尔排序在时间效率上比前两种方法有较大提高。

序列分组轨迹图:

参考:https://blog.csdn.net/IWantToHitRen/article/details/51583047

对于希尔排序和插入排序速度的对比:

  • 10000条数据排序100次,插入排序用时12.3s,希尔排序用时0.3s!;
  • 50000条数据排序100次,插入排序用时380.7s,希尔排序用时1.8s!;

以下是结合网上对希尔排序的理解实现的算法以及《算法 第四版》原文中的算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class Shell extends Example {

/**
* 根据网上总结自己实现的算法
*/
@Override
public void sort(Comparable[] a) {
int N = a.length;
for (int gap = N / 2; gap > 0; gap /= 2) { // gap:增量(步数),每次循环增量减少一倍,直至增量为1(此时对全部元素进行插入排序)完成排序。
for (int i = 0; i < gap; i++) { // 把整体序列分为若干子序列。a[i]是每一组的第一个元素
for (int j = i + gap; j < N; j += gap) { // 每间隔一个增量,获得一个该组的元素。
int tarIndex = j; // 目标元素索引,当前元素索引。
for (int k = tarIndex; k > i && less(a[k], a[k - gap]); k -= gap) { // 对子序列进行插入排序,将该元素与本组左边所有元素进行比较。
exch(a, k, k - gap);
}
}
}
}
}

/**
* 原文的算法,增量使用了递增序列,有时间再来理解。
*/
public void sort3(Comparable[] a) {
int N = a.length;
int h = 1;
while (h < N / 3) {
h = 3 * h + 1;
}
while (h >= 1) {
// 子数组插入排序
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;
}
}
}

归并排序

归并排序的核心是归并操作,归并排序每次将数组 递归的 拆分成两半分别排序,再将两半的结果 合并 起来最终实现整个数组的排序。

归并操作

归并操作的前提是数组的两边是分别 有序 的,将一个“两边有序的数组”合并成一个“整体有序的数组”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Merge extends Example {
private static Comparable aux[]; // 辅助数组,用于合并操作。

//TODO sort()

public static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
int le = lo;
int ri = mid + 1;

for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}

for (int k = lo; k <= hi; k++) {
if (le > mid) {
a[k] = aux[ri++]; // 左边元素用尽,将右边元素一个一个放入a[]
} else if (ri > hi) {
a[k] = aux[le++]; // 右边元素用尽,将左边元素一个一个放入a[]
} else if (less(aux[ri], aux[le])) {
a[k] = aux[ri++]; // 右边元素小于左边元素,右边元素放入a[],右边元素索引+1
} else {
a[k] = aux[le++]; // 左边元素小于右边元素,左边元素放入a[],左边元素索引+1
}
}
}
}

自顶向下归并排序

归并排序不断(递归)的将大数组插拆分为两半,直到不可再拆(小数组仅剩“左右”两个元素),再将两边的数组合并成一个整体有序的大数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Merge extends Example {
private static Comparable aux[]; // 辅助数组,用于合并操作。

@Override
public void sort(Comparable[] a) {
aux = new Comparable[a.length];
sort(a, 0, a.length - 1);
}

private void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, lo, mid); // 左半边排序
sort(a, mid + 1, hi); // 右半边排序
merge(a, aux, lo, mid, hi); // 合并子数组
}
}

每一个节点都是 merge() 操作形成的子数组。当数组不可再分(递归到了最小情况),merge()通过交换前后元素实现排序。

Alt text

改进

对于小规模数组使用插入排序

测试数组是否有序

有参考价值博客:图解排序算法(四)之归并排序

自底向上归并排序

先归并微型数组,再成对归并得到的子数组,直到归并形成一个大数组,排序结束。

  • 第一轮:将大数组的每一个元素当作一个子数组(最小的子数组),两两归并 子数组(将大小为1的子数组归并成大小为2的子数组)。

  • 第二轮:一轮归并之后每个子数组存在 2 个元素,再 四四归并 子数组(将大小为2的子数组归并为大小为4的子数组)。

  • 第三轮:二轮归并之后每个子数组存在 4 个元素,再 八八归并 子数组(将大小为4的子数组归并为大小为8的子数组)。

  • …… 如此往复,直到子数组大小 >= 待排序的大数组,完成了排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class MergeBU extends Example {
private static Comparable aux[];

@Override
public void sort(Comparable[] a) {
int N = a.length;
aux = new Comparable[N];
for (int sz = 1; sz < N; sz = sz + sz) { // 控制子数组大小呈倍数递增
/**
* 遍历每个子数组
* lo 每个子数组的第一个元素
* lo < N - sz 控制最后一个子数组的开头
* lo = lo + sz + sz 跳到下一个子数组开头
* Math.min(lo + sz + sz - 1, N - 1) 最后一个子数组的大小有可能不是sz的整数倍,lo + sz + sz - 1可能会出现数组越界。
*/
for (int lo = 0; lo < N - sz; lo = lo + sz + sz) {
int mid = lo + sz - 1;
int hi = Math.min(lo + sz + sz - 1, N - 1);
merge(a, aux, lo, mid, hi);
}
}
assert isSorted(a);
}
}

可视图:
Alt text

快速排序

快速排序同归并排序一样是一种分治的排序算法。它通过 切分 递归的将数组分为两个部分,对两个部分分别排序,并保证左边的元素都 <= 切点,右边的元素都 >= 切点

每次切分都能保证子数组左边的元素小于切点,右边的元素大于切点。通过递归,对左半边和右半边数组再次切分,最终达到整个数组的有序。

切分算法:

  • 切点定为子数组的第一个元素(可以是任意元素)

  • 指针 i 从左往右扫描 大于 切点的值,找到即退出扫描;指针 j 从右往左扫描 小于 切点的值,找到即退出扫描。

  • 交换 a[i] 与 a[j] 的位置,小的值放在左边,大的值放在右边。

  • 若 i 扫描完毕找不到最大值,说明 切点 就是最大值;若 j 扫描完毕找不到最小值,说明 切点 就是最小值

  • 为什么指针相遇(i >= j)切分结束?因为相遇了代表所有元素都已遍历完毕。

  • 指针相遇(双向扫描完毕)之后,交换 切点(v) 与 a[j] 的值,此时a[j]是最后一个小于 v 的值,而切点到了数组中间,最后返回切点索引。

博客参考,对于理解很有帮助:坐在马桶上看算法:快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Quick extends Example {
@Override
public void sort(Comparable[] a) {
StdRandom.shuffle(a);
sort(a, 0, a.length - 1);
}

private void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo) return;
int j = partition(a, lo, hi); // 切分
sort(a, lo, j - 1); // 左半边排序
sort(a, j + 1, hi); // 右半边排序
}

private int partition(Comparable[] a, int lo, int hi) {
int i = lo, j = hi + 1; // 左右扫描的指针
Comparable v = a[lo]; // 切分的元素
while (true) {
while (less(a[++i], v)) { // 指针 i 从左往右扫描大于v的值
if (i == hi) break;
}
while (less(v, a[--j])) { // 指针 j 从右往左扫描小于v的值
if (j == lo) break;
}
if (i >= j) break; // 为什么 i >= j 退出外循环?
exch(a, i, j); // 小值放左边,大值放右边。
}
exch(a, lo, j);
return j;
}
}

快速排序最好的情况下是每次都正好能将数组对半分,这样递归调用次数才是最少的。

最坏的情况下,第一次从最小的元素切分,第二次从第二小的元素切分,如此这般。为了防止数组最开始就是有序的,在进行快速排序时需要随机打乱数组。

改进

  1. 对于小数组,使用插入排序。只需将递归结束条件从 if (hi <= lo) return; 改为:if (hi <= lo + 15) { new Insertion().sort(a); return; }

  2. 三取样切分:选取较优的切点元素来提高性能。将子数组的一小部分元素中的中位数作为切点来切分数组效果为好,一般取3个元素。参考:图解排序算法(五)之快速排序——三数取中法

  3. 对于含有大量重复元素的数组,该算法还是会继续切分数组,增加不必要的性能开销。解决方案:三向切分算法:Quick3way.java

以上改进 均未!实现!太搞脑子了😣~~~

优先队列

在某些拥有大量输入N(数十亿甚至无限)的用例中,需要在大量输入中取最大(或最小)的前M个值。解决这种需求,数组排序的代价特别高昂,原因有2点:1. 数据量特别大,不可能将十亿个数放进数组排序,有可能内存都装不下;2. 只需要取前M的有序的值,并不需要将所有数据排序,甚至都无法获取全部的数据。

优先队列可以解决这类问题,有了优先队列,只需要创建一个大小为M的队列即可代替创建大小为总数据量N的数组。

API

方法 描述
MaxPQ() 创建一个优先队列
MaxPQ(int max) 创建一个初始容量的优先队列
MaxPQ(Key[] arr) 用arr[]中的元素创建一个优先队列
void insert(Key v) 向优先队列插入一个元素
Key max() 返回最大元素
Key delMax() 删除最大元素
boolean isEmpty() 判断是否为空
int size() 查看队列大小

初级实现

基于无序数组的优先队列:MaxPQ4DisArray.java

基于有序数组的优先队列:MaxPQ4Array.java

基于无序链表栈的优先队列:MaxPQ4Linked.java

基于堆的优先队列

二叉堆的定义与表示法

二叉堆(完全二叉树,之不过在这叫做堆)是一种基于数组的数据结构。既然是树形结构,必然有一个根节点,根节点下面挂着(一个或)两个子节点,每个子节点作为父节点又挂着两个子节点。同级节点之间无关顺序,父节点大于等于子节点。当一个二叉树的每个节点都大于等于它的两个子节点时,被称之为“堆有序”。

如何用数组存储具有层级顺序关系的二叉堆呢?

首先,二叉堆在数组中按索引位置 1 开始存储(不使用数组的第一个元素)

在一个堆中位置 k 的节点的父节点的位置为 k/2,而它的两个子节点的位置分别为 k*2, K*2+1,这样就可以通过计算索引在树中上下移动。

二叉堆表示:

Alt text

二叉堆在数组中的存储结构:

Alt text

用长度为 N+1 的数组 pq[] 来表示一个大小为 N 的堆,因为堆元素存放与 pq[1]到pq[N]之中,所以实际数组的长度要是堆的元素大小+1

由下至上的堆有序化(上浮)

当堆的有序化因为某个节点变得比其父节点更大而被打破,我们需要交换该节点和其父节点来修复堆。交换后该节点比它的两个子节点(一个是交换之前的父节点,另一个比它更小,因为是旧父节点的子节点)都要大了,但该节点仍然有可能比现在的父节点要大,所以需要再一次交换,使得该节点不断上浮直到遇到了更大的节点或到达堆顶。

1
2
3
4
5
6
7
8
9
public class MaxPQ<Key extends Comparable<Key>> implements IMaxPQ<Key> {
//......
public void swim(int k) {
while (k > 1 && less(k / 2, k)) {
exch(k / 2, k);
k = k / 2;
}
}
}

由上至下的堆有序化(下沉)

下沉与上浮相反,当有序状态因为某个节点变得比它的两个(或其中之一)子节点要小被打破,那么需要交换该节点与其较大的一个子节点来保持平衡。倘若交换之后该节点仍比现在的子节点之一要大,继续交换,直至向下交换到该节点的子节点都比它小或到达堆的底部。

疑问:“父节点怎么会变得比子节点要小呢?添加一个元素在数组末尾时会通过上浮移动到合适的位置的啊。” — 这跟删除最大元素的算法有关,移除堆顶元素时,会用数组的最后一个元素替补最大元素,所以此时存在元素下沉的必要。

1
2
3
4
5
6
7
8
9
10
11
12
public class MaxPQ<Key extends Comparable<Key>> implements IMaxPQ<Key> {
//......
public void sink(int k) {
while (2 * k <= N) {
int j = 2 * k;
if (j < N && less(j, j + 1)) j++;
if (!less(k, j)) break;
exch(k, j);
k = j;
}
}
}

堆的上浮与下沉:

Alt text

优先队列实现

理解了上浮和下沉,优先队列核心的两个api就能实现了,对于 插入元素,只需将元素添加到数组末尾,增加堆的大小并让新元素上浮到合适的位置;对于 删除最大元素,我们从数组顶端去除最大元素,并将数组最后一个元素放到顶端,减少堆的大小并让元素下沉到合适的位置即可。

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class MaxPQ<Key extends Comparable<Key>> implements IMaxPQ<Key> {
private Key[] pq; // 基于堆的完全二叉树
private int N; // 堆元素数量

@Override
public void insert(Key v) {
if (N == pq.length - 1) resize(pq.length * 2);
pq[++N] = v;
swim(N);
}

@Override
public Key delMax() {
if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");
Key max = pq[1];
exch(1, N--);
pq[N + 1] = null; // 防止对象游离
sink(1);
if (N > 0 && (pq.length - 1) / 4 == N) resize(pq.length / 2);
return max;
}

@Override
public Key max() {
if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");
return pq[1];
}

private void resize(int max) {
assert max > N;
Key[] temp = (Key[]) new Comparable[max];
for (int i = 1; i < N + 1; i++) {
temp[i] = pq[i];
}
pq = temp;
}
}

基于堆的优先队列API能够保证插入元素和删除最大元素的用时和队列的大小仅成对数关系。

索引优先队列

二叉树存储的不是元素值,而是元素值的key;通过这个 key 在元素数组 element[] 中找到元素值;用keyIndex[]存储key的索引。

先补点智商,干了这碗鸡汤:索引优先队列的工作原理与简易实现

提醒:前方高能!!!传送门

堆排序

以优先队列实现的排序算法,将原始数组元素放入一个优先队列中,由于在队列中可以轻易的获得最大值,每次获取的最大值可以组成一个递减序列。如果获取的最大值不删除,而是将其和队列的最后一个元素交换,第二次将新的最大值与数组的倒数第二个值交换,循环往复,直至数组元素遍历完,排序完成。

堆的构建

将原始数组元素组成一个完全二叉树结构,一个简单的方式就是将数组 从左至右 执行 上浮 操作,直至每个元素放到了合适的位置。

上浮操作生成堆会扫描数组的每一个元素,更好的方式是 从右至左 执行 下沉 操作,它只需要扫描数组一半的元素,因为不需要比较叶子节点。

排序

交换堆顶元素和最后一个元素,每次交换之后重新下沉以维持堆的有序状态。

由于在堆结构中不使用数组的第一个位置的元素,导致原始数组的第一个元素值必须为null,要以正常存储的方式使用堆排序,只需要在 less() 和 exch() 中将传入的索引-1即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
public class Heap {
public void sort(Comparable[] a) {
int n = a.length - 1;
// 构造堆
sinkGenerationHead(a, n);
// swimGenerationHead(a, n);
// 堆排序
while (n > 1) {
exch(a, 1, n--);
sink(a, 1, n);
}
}

//下沉生成大顶堆(最优)
public void sinkGenerationHead(Comparable[] a, int n) {
for (int i = n / 2; i >= 1; i--) { // 从右到左
sink(a, i, n);
}
}

// 上浮生成大顶堆
public void swimGenerationHead(Comparable[] a, int n) {
for (int k = 0; k < n; k++) { // 必须是从左到右
swim(a, k, n);
}
}

public void sink(Comparable[] a, int k, int n) {
while (2 * k <= n) {
int j = 2 * k;
if (j < n && less(a, j, j + 1))
j++;
if (!less(a, k, j))
break;
exch(a, k, j);
k = j;
}
}

public void swim(Comparable[] a, int k, int n) {
while (k > 1 && less(a, k / 2, k)) {
exch(a, k / 2, k);
k = k / 2;
}
}

private boolean less(Comparable[] a, int i, int j) {
return a[i].compareTo(a[j]) < 0;
}

private void exch(Comparable[] a, int i, int j) {
Comparable tem = a[i];
a[i] = a[j];
a[j] = tem;
}

public static void main(String[] args) {
Comparable[] a = new Comparable[]{null, 2, 0, 5, 7, 9, 8, 3, 1, 4, 6};
Heap heap = new Heap();
heap.sort(a);
for (int i = 0; i < a.length; i++) {
StdOut.print(a[i] + " ");
}
}
}

总结

在java中的排序都是基于指针的,除了原始数据类型以外,我们操作的都是数据的引用(指针),而非数据本身。指针排序增加了一层间接性,因为数组保存的是待排序对象的引用,而非对象本身。

在一些情况下,对于排序之后的数据要求不可改变键值,如果能修改,那么数组将不再有序。类似的,优先队列在能改变键值的情况下也不太可能正常工作(索引优先队列能改变键值并维持有序是每次改变之后都进行上浮下沉操作)。限定排序元素不可变可以使用java的不可变数据类型,如八大封装类型和String,以及自定义的不可变数据类型(不可变类型:实例变量以private、final修饰;不提供setter方法;提供带参构造器以初始化实例变量)。

在java中实现任意数据类型排序的方法就是实现Comparable接口,重写其compareTo方法。但当我们对该数据类型的排序方法有多个时,我们可以创建一个比较器对象,使其实现Comparator接口,重写compare方法,进行比较时根据需求传入不同Comparator接口的实现即可。

如果一个排序算法能够保留数组中重复元素的相对位置则可以被称之为 稳定的,对于排序算法稳定性的要求在某些场景尤为重要。

对于前面学习过的各种排序算法的性能特点如下:

算 法 是否稳定 是否为原地排序 时间复杂度 空间复杂度 备 注
选择排序 N^2 1
插入排序 介于N和N^2之间 1 取决于输入元素的排列情况
希尔排序 NlogN? N^(6/5)? 1
快速排序 NlogN lgN 运行效率由概率提供保证
三向快速排序 介于N和NlogN之间 lgN 运行效率由概率保证,同时也取决于输入元素的分布情况
归并排序 NlogN N
堆排序 NlogN 1

大多数情况下,快速排序是最好的选择。但是如果稳定性很重要而空间不是问题的情况下,归并排序可能是最好的。

java 函数库中对原始数据类型使用三向切分快速排序,对于引用类型使用归并排序。这么做也印证着用速度和空间(对于原始数据类型)来换取稳定性(对于引用类型)。

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×