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

在java学习或是数据结构的学习中，排序都是比较重要的一个部分，对于各种排序算法可能会有些头疼；这篇文章将详细讲解一下排序问题；为简单起见，例子中的数组只包含整数而且元素个数比较少（百万以内）。被排序的对象应属于Comparable类型，因此我们使用CompareTo方法对数据进行相容的排序。这种叫做基于比较的排序。默认排序没有或不可接受的时候，需要重写Comparable来实现排序算法。 插入排序 插入排序是最简单的排序算法；它由N-1趟排序组成。对于p-1到N-1趟，插入排序保证从位置0到位置p的元素已经完成排序。在第p趟，将位置p的元素向左移动，直到它在前p+1个元素中的正确位置被找到的地方。 位置p上的元素储存于tmp,而（在位置p之前）所有更大的元素都被向右移动一个位置，然后tmp被置于正确的位置上；以下为代码： package com.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 extends Comparable? 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个独立的子数组执行一次插入排序。 以下为代码 package com.javawxs; 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.length; i++) System.out.print(arr[i] + ); } public static T extends Comparable? super T void shellSort(T[] a) { int j; for (int gap = a.length / 2; gap 0; gap /= 2) for (int i = gap; i a.length; i++) { T tmp = a[i]; for (j = i; j = gap pareTo(a[j - gap]) 0; j -= gap) a[j] = a[j - gap]; a[j] = tmp; } } } 堆排序 首先建立N个元素的二叉堆，花费时间（O(N)），然后执行N次的deleteMin操作。按照顺序，最小的元素先离开堆。通过将这些元素记录到第二个数组然后再将数组拷贝回来，得到N个元素的排序。由于每个deleteMin花费时间O(log N)，因此运行总时间为O(N log N)。 该算法的主要问题在于它使用了一个附加数组，增大大储存需求；可以这样来避免使用第二个数组：在每次deleteMin之后，堆缩小1；所以位于堆中最后