排序算法的应用

1. 多种排序方式

使用 Comparator 接口,我们可以定义不同的 sort() 方法或者使用不同的键来对数据进行排序。

Comparator 接口:

1
2
3
public interface Comparator {
int compare();
}

注意,此接口是被排序类提供的,排序方法只需要调用接口的 compare方法即可

为了使用此接口,我们可以通过重载 sort() 方法来实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// The original sort() method
public void sort(Comparable[] a) {
/* The sort method body */
}

// Now we use new sort which comes wit Comparator
public void sort(Object[] a, Comparator c) {
/* The new sort method body */
}

// Also, we need to changge other
// assistant method to use Comparator
private int less(Comparator c, Key v, Key w) {
// Invoke the interface method
return c.compare(v, w);
}

对于被排序类的实现,可以通过使用内部类的方式来提供 Comparator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Student {
public static final Comparator<Student> BY_NAME = new ByName();
public static final Comparator<Student> BY_SECTION = new BySection();


private class ByName implements Comapator<Student> {
pubic int compare(Student v, Student w) {
// By name
}
}

private class BySection implements Comparator<Student> {
public int compare(Student v, Student w) {
// By Section
}
}
}

2. 稳定性

稳定性指的是,在排序过程中,算法会保留具有相同键值的元素的相对顺序。

如果能够保留,就说明排序算法是稳定的,如果不能够保留,则不稳定。

排序算法稳定与否,在于在排序过程中,是否改变了相同键值元素的位置

3. 排序算法的比较

AlgorithmStable?Inplace?Grow Rate to Sort N ItemsNotes
Running TimeExtra Space
Selection SortNoYes$N^2$1
Insertion SortYesYesBetween $N$ and $N^2$1Base on the input
Shell SortNoYes$N^{6/5}$1
Quick SortNoYes$NlogN$$lgN$The efficiency is guaranteed by the posibility
3-way Partitioning
Quick Sort
NoYesbetween $N$ and $NlogN$$lgN$The efficiency is guaranteed by the posibility, meanwhile it also depens on the input
Merge SortYesNo$NlogN$$N$
Heap SortNoYes$NlogN$$N$

4. 结论

  1. 快速排序是最快的排序算法

    快速排序的时间复杂度为 cNlogN\sim cNlogN 级别,同时它的 cc 也比其他排序算法要小

  2. 如果稳定性很重要,而空间并不是很紧张,那么归并排序是最好的选择

  3. 如果空间非常小,那么堆排序是一个不错的选择