rainyzz's blog

排序复习

排序的稳定性

排序的稳定性主要体现在有多个数据项的情况下,在按照第一项排序的情况下,第二项是否保持稳定。

原始数据 稳定排序 非稳定排序
Chicago 09:00:00 Chicago 09:00:00 Chicago 09:00:00
Phoenix 09:00:03 Chicago 09:10:10 Chicago 10:13:00
Chicago 09:10:10 Chicago 10:13:00 Chicago 09:10:10
Houston 09:15:10 Houston 09:15:10 Houston 09:15:10
Chicago 10:13:00 Phoenix 09:00:03 Phoenix 09:00:03

稳定排序中按名字排序后时间依然有序,非稳定排序中时间可能不再有序。

Java相关

comparejava.util.Comparator中的函数,需要实现比较时比较两个对象的大小。一般用于Collections.sort()

compareTo属于对象的方法,来自Comparable接口,实现当前对象与同类对象的对比。

插入排序(稳定排序)

每次选择一个数加入前半部分的有序数组,直到最后全部有序。

循环不变量:每次循环中前i个数都是有序的。

归并排序(稳定排序)

需要额外空间,空间复杂度O(n)

1
2
3
4
5
6
7
private static void sort(int[] a, int l, int r){
if(r <= l) return;
int mid = l + (r - l) / 2;
sort(a, l, mid);
sort(a, mid + 1, r);
merge(a, l, mid, r);
}

选择排序(非稳定排序)

每次选择当前未排序的数组中最小的数放到前半部分有序数组。

循环不变量:每次循环中前i个数,每一个数都在自己最终的位置上。

希尔排序(非稳定排序)

按照不同的间距进行排序,如每隔5个排序一下,然后隔3个,隔1个等等,大规模数据下性能很好。

快速排序(非稳定排序)

选一个轴,每一次都按照大于轴和小于轴的两部分。由于轴的选择不同,可能无法将元素均匀分开,常使用开头,结尾,中间三个元素中中间的数作为轴,或者随机选轴。

对于小数组来说,切换到插入排序也能加快速度。

1
2
3
4
5
6
private static void sort(int[] a, int l, int r){
if(r <= l) return;
int j = partition(a, l, r);
sort(a, l, j - 1);
sort(a, j + 1, r);
}

三项快速排序(非稳定排序)

数据重复较多的时候块排性能下降,维护两个指针l和r,l左边是小于轴,r右边大于轴,l与r之间是与轴相等的元素,

堆排序(非稳定排序)

堆排序现实中很少使用,因为缓存效果不好。但是在优先级队列中或Top K中使用较多。

堆的插入,堆插入时放在最后一个位置,然后由下往上浮。时间复杂度O(logN)。

1
2
3
4
5
6
private static void swim(int k){
while(k > 1 && less(k / 2, k)){
exch(k / 2, k);
k = k / 2;
}
}

堆的删除,最后一个节点与根节点交换,然后删除,然后调整。时间复杂度O(logN)。

1
2
3
4
5
6
7
8
9
private static 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;
}
}