详解常用排序算(Java实现).doc

在 java 学****或是数据结构的学****中,排序都是比较重要的一个部分,对于各种排序算法可能会有些头疼; 这篇文章将详细讲解一下排序问题; 为简单起见, 例子中的数组只包含整数而且元素个数比较少( 百万以内)。 parable 类型, 因此我们使 pareTo 方法对数据进行相容的排序。这种叫做基于比较的排序。默认排序没有或不可接受的时候,parable 来实现排序算法。插入排序插入排序是最简单的排序算法; 它由 N-1 趟排序组成。对于 p-1 到 N-1 趟, 插入排序保证从位置 0 到位置 p 的元素已经完成排序。在第 p趟, 将位置 p 的元素向左移动, 直到它在前 p+1 个元素中的正确位置被找到的地方。位置 p 上的元素储存于 tmp, 而(在位置 p 之前)所有更大的元素都被向右移动一个位置,然后 tmp 被置于正确的位置上;以下为代码: .javawxs; public class InsertionSort { public static void main(String[] args) { Integer[] arr ={ 71, 45, 32, 76, 142, 43, 98, 54, 14, 333, 12, 31, 3 }; insertionSort (arr); } public static <T parable<? super T>> void insertionSort(T[] a) { int j; for ( int p= 1; p< a. length ; p++) { T tmp = a[p]; for (j = p; j>0 && pareTo(a[j - 1]) < 0; j--) a[j] = a[j - 1]; a[j] = tmp; }}} 希尔排序希尔排序( Shellsort )的名字源于的它的发明者 Donald Shell ,它通过比较相距一定间隔的元素来实现; 各趟比较所用的距离随着算法的进行而减小, 直到只比较相邻元素的最后一趟为止;所以希尔排序也叫缩减增量排序。希尔排序使用一个序列 h1,h2,h3 ……,ht, 叫做增量序列,只要 h1=1 ,那么任何增量序列都是可行的。在使用 hk 的一趟排序之后,对于每个 i ,都有 a[i]<=a[i+hk] ;所有间隔 hk的元素都被排序。希尔排序的一个重要性质: 一个 hk 排序的文件保持它的 hk 排序性; 实际上, 假如不这样的话,那么希尔排序也就没什么意义了,因为前面各趟排序会被后面的各趟排序打乱。 hk 排序的一般做法是,对于 hk,hk+1, ……,N-1 中的每一个位置 i ,把其上的元素放到 i ,i-hk,i-2hk, ……中的正确位置上。虽然不影响最终结果,但是通过观察可以发现一趟 hk的排序作用就是对 hk 个独立的子数组执行一次插入排序。; public class ShellSort { public static void main(String[] args) { Integer[] arr ={ 71, 45, 32, 76, 142, 43, 98, 54, 14, 333, 12, 31, 3 }; shellSort (arr); for ( int i= 0; i< arr. l