神刀安全网

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

前言

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

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 趟。

实现

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;j++){
if(less(a[j+1],a[j])){
exch(a,j,j+1);
}
}
}
}
}

优化

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

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;j++){
if(less(a[j+1],a[j])){
exch(a,j,j+1);
didSwap = true;
}
}
if(!didSwap) return ;
}
}
}

选择排序(Selection sort)

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

原理

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

实现

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²)。

原理

遍历未排序序列。把未排序数列的第一个数和已排序数列的每一个数比较,若比它大则交换。经典的理解方式就是理解成摸牌时候理牌的顺序。

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

实现

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 .

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

性能

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

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

运行时间比较

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

冒泡排序 9.234000000000004

选择排序 2.351

插入排序 2.720999999999999

希尔排序 0.09400000000000007

Reference

算法 4th

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » 简单排序之冒泡、选择、插入、希尔详细总结

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
分享按钮