简单排序之冒泡、选择、插入、希尔详细总结

前言

本文讲述一些简单算法的实现和效率比较。所有代码用java实现。用到的两个基本的api代码如下。

1
2
3
4
5
6
7
8
9
private boolean less(Comparable v,Comparable w){
return v.compareTo(w) <0;
}
private void exch(Comparable[] a,int i,int j){
Comparable temp = a[i];
a[i] = a[j];
a[j] = temp;
}

冒泡排序(Bubble Sort)

一般算法入门,都是用冒泡做的例子。但实际中基本很难用到,复杂度O(n²)

原理

一趟一趟的比,每一趟中,循环剩余的数,和后一个进行比较,若比它小则交换。这样一趟下来最小的在第一个,最大的在最后一个。总共比n-1趟。

实现

1
2
3
4
5
6
7
8
9
10
11
12
public class Bubblesort implements Sortable {
@Override
public void sort(Comparable[] a) {
for(int i=0;i<a.length-1;i++){
for(int j=0;j<a.length-1-i;j++){
if(less(a[j+1],a[j])){
exch(a,j,j+1);
}
}
}
}
}

优化

上面的算法,无论的你的数据怎么样,始终都要比次,效率很低。若你的数据局部有序,经过几趟交换以后,已经有序,则不用继续往下比。效率会高很多。优化代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Bubblesort implements Sortable {
@Override
public void sort(Comparable[] a) {
for(int i=0;i<a.length-1;i++){
boolean didSwap = flase;
for(int j=0;j<a.length-1-i;j++){
if(less(a[j+1],a[j])){
exch(a,j,j+1);
didSwap = true;
}
}
if(!didSwap) return ;
}
}
}

选择排序(Selection sort)

和冒泡复杂度一样O(n²),但是时间上可能会比冒泡稍微快一点,因为交换的次数比冒泡少。

原理

选择排序可以说是最好理解的算法。就是每次遍历一趟,找出最小的数,放到最前端。(这里说的是最前,是指无序的队列中的最前)

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Selection implements Sortable {
@Override
public void sort(Comparable[] a){
for(int i=0;i<a.length;i++){
int min=i;
for(int j=i+1;j<a.length;j++){
if(less(a[j],a[min])){
min = j;
}
}
exch(a,i,min);
}
}
}

插入排序

时间复杂度O(n²)。

原理

遍历未排序序列。把未排序数列的第一个数和已排序数列的每一个数比较,若比它大则交换。经典的理解方式就是理解成摸牌时候理牌的顺序。我上面的实现是直接交互数字,若是把大的数直接往后移效率还会更高。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Insertion implements Sortable{
@Override
public void sort(Comparable[] a){
for(int i=1;i<a.length;i++){
for(int j=i;j>0;j--){
if(less(a[j],a[j-1])){
exch(a,j,j-1);
}
else break;
}
}
}
}

适合插入排序的数据

当你的数据是基本有序的时候且数据量小,利用插入排序的时候,效率会很高。若数据为逆序的话,效率很低。

希尔排序(Shell Sort)

可以看出是插入排序的一种优化,或者是预处理。希尔排序就是先进行h-sort,也就是让间隔为h的元素都是有序的。普通的插入排序就是1-sort

原理

主要就是选定一个h的有序数组来进行预排序。这样最后进行插入排序的时候,能使数据局部有序。就算交换的话,交换的次数也不会很多。这样h序列称为递增序列。希尔的性能很大部分取决于递增序列.一般来说我们使用这个序列3x + 1.

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class ShellSort implements Sortable {
@Override
public void sort(Comparable[] a){
int h=1;
while(h<a.length/3){
h=3*h+1;
}
while(h>=1){
for(int i=h;i<a.length;i++){
for(int j=i;j>=h;j=j-h){
if(less(a[j],a[j-h])){
exch(a,j,j-h);
}
else break;
}
}
h=h/3;
}
}
}

性能

对于希尔排序的性能其实无法准确表示。介于O(nlogn)O(n²)之间,大概在n的1.5次幂左右。

希尔排序对于中大型数据的排序效率是很高的,而且占用空间少,代码量短。而且就算是很大的数据,用类似快排这种高性能的排序方法,也仅仅只比希尔快两倍或者不到。

运行时间比较

我测试了一下,用5000个数据,排序100次。使用上述四个算法的运行时间如下。

冒泡排序 5.734000000000004

选择排序 2.351

插入排序 2.720999999999999

希尔排序 0.09400000000000007

Reference

算法 4th