常用排序算法小结

标签: 排序算法 | 发表时间:2013-08-14 23:32 | 作者:
出处:http://www.iteye.com

离开课堂后,排序算法写的比较少了,当有排序的要求时,一般用的比较多的是直接采用Arrays.sort以及Collections.sort结合比较器来实现。

Arrays工具类包含了对各种类型数组的排序,以下是Arrays中包括的sort方法:


以下是 Collections中的sort方法,该sort方法中结合了Arrays.sort来实现的。
/**
     * Sorts the specified list into ascending order, according to the
     * <i>natural ordering</i> of its elements.  All elements in the list must
     * implement the <tt>Comparable</tt> interface.  Furthermore, all elements
     * in the list must be <i>mutually comparable</i> (that is,
     * <tt>e1.compareTo(e2)</tt> must not throw a <tt>ClassCastException</tt>
     * for any elements <tt>e1</tt> and <tt>e2</tt> in the list).<p>
     *
     * This sort is guaranteed to be <i>stable</i>:  equal elements will
     * not be reordered as a result of the sort.<p>
     *
     * The specified list must be modifiable, but need not be resizable.<p>
     *
     * The sorting algorithm is a modified mergesort (in which the merge is
     * omitted if the highest element in the low sublist is less than the
     * lowest element in the high sublist).  This algorithm offers guaranteed
     * n log(n) performance. 
     *
     * This implementation dumps the specified list into an array, sorts
     * the array, and iterates over the list resetting each element
     * from the corresponding position in the array.  This avoids the
     * n<sup>2</sup> log(n) performance that would result from attempting
     * to sort a linked list in place.
     *
     * @param  list the list to be sorted.
     * @throws ClassCastException if the list contains elements that are not
     *	       <i>mutually comparable</i> (for example, strings and integers).
     * @throws UnsupportedOperationException if the specified list's
     *	       list-iterator does not support the <tt>set</tt> operation.
     * @see Comparable
     */
    public static <T extends Comparable<? super T>> void sort(List<T> list) {
	Object[] a = list.toArray();
	Arrays.sort(a);
	ListIterator<T> i = list.listIterator();
	for (int j=0; j<a.length; j++) {
	    i.next();
	    i.set((T)a[j]);
	}
    }

    /**
     * Sorts the specified list according to the order induced by the
     * specified comparator.  All elements in the list must be <i>mutually
     * comparable</i> using the specified comparator (that is,
     * <tt>c.compare(e1, e2)</tt> must not throw a <tt>ClassCastException</tt>
     * for any elements <tt>e1</tt> and <tt>e2</tt> in the list).<p>
     *
     * This sort is guaranteed to be <i>stable</i>:  equal elements will
     * not be reordered as a result of the sort.<p>
     *
     * The sorting algorithm is a modified mergesort (in which the merge is
     * omitted if the highest element in the low sublist is less than the
     * lowest element in the high sublist).  This algorithm offers guaranteed
     * n log(n) performance. 
     *
     * The specified list must be modifiable, but need not be resizable.
     * This implementation dumps the specified list into an array, sorts
     * the array, and iterates over the list resetting each element
     * from the corresponding position in the array.  This avoids the
     * n<sup>2</sup> log(n) performance that would result from attempting
     * to sort a linked list in place.
     *
     * @param  list the list to be sorted.
     * @param  c the comparator to determine the order of the list.  A
     *        <tt>null</tt> value indicates that the elements' <i>natural
     *        ordering</i> should be used.
     * @throws ClassCastException if the list contains elements that are not
     *	       <i>mutually comparable</i> using the specified comparator.
     * @throws UnsupportedOperationException if the specified list's
     *	       list-iterator does not support the <tt>set</tt> operation.
     * @see Comparator
     */
    public static <T> void sort(List<T> list, Comparator<? super T> c) {
	Object[] a = list.toArray();
	Arrays.sort(a, (Comparator)c);
	ListIterator i = list.listIterator();
	for (int j=0; j<a.length; j++) {
	    i.next();
	    i.set(a[j]);
	}
}


本文将用JAVA实现七个常用排序,包括:冒泡排序,插入排序,选择排序,希尔排序,快速排序,归并排序和堆排序。


代码类图如下:


一个抽象类 BsseSort中包含了排序用到的一些公共操作,比如比较等。
package my.sort;

public abstract class BaseSort<T> {

	@SuppressWarnings("hiding")
	protected abstract <T extends Comparable<T>> void sort(T[] array);

	@SuppressWarnings({ "hiding" })
	protected <T extends Comparable<T>> boolean lessThan(T t1, T t2) {
		return t1.compareTo(t2) < 0;
	}

	@SuppressWarnings({ "hiding" })
	protected <T extends Comparable<T>> boolean greatThan(T t1, T t2) {
		return t1.compareTo(t2) > 0;
	}

	@SuppressWarnings("hiding")
	protected <T extends Comparable<T>> boolean equalTo(T t1, T t2) {
		return t1.compareTo(t2) == 0;
	}

	@SuppressWarnings("hiding")
	protected <T extends Comparable<T>> void swap(T[] array, int i, int j) {
		T t = array[i];
		array[i] = array[j];
		array[j] = t;
	}

	@SuppressWarnings("hiding")
	protected <T extends Comparable<T>> void printArray(T[] array) {
		for (T t : array) {
			System.out.print(t);
			System.out.print(" ");
		}
		System.out.println();
	}

}


冒泡排序
package my.sort;

public class BubbleSort<T> extends BaseSort<T> {

	@SuppressWarnings("hiding")
	@Override
	protected <T extends Comparable<T>> void sort(T[] array) {
		int length = array.length;
		for (int i = 0; i < length; i++) {
			for (int j = 1; j < length - i; j++) {
				if (greatThan(array[j - 1], array[j])) {
					swap(array, j - 1, j);
				}
			}
		}
	}
}


插入排序
package my.sort;

public class InsertionSort<T> extends BaseSort<T> {

	@SuppressWarnings("hiding")
	@Override
	protected <T extends Comparable<T>> void sort(T[] array) {
		int length = array.length;
		for (int i = 1; i < length; i++) {
			for (int j = i; j > 0 && lessThan(array[j], array[j - 1]); j--) {
				swap(array, j, j - 1);
			}
		}
	}
}


选择排序
package my.sort;

public class SelectionSort<T> extends BaseSort<T> {

	@SuppressWarnings("hiding")
	@Override
	protected <T extends Comparable<T>> void sort(T[] array) {
		int length = array.length;
		for (int i = 0; i < length; i++) {
			int min = i;
			for (int j = i + 1; j < length; j++) {
				if (lessThan(array[j], array[min])) {
					min = j;
				}
			}
			swap(array, i, min);
		}
	}

}



希尔排序

package my.sort;

public class ShellSort<T> extends BaseSort<T> {

	@SuppressWarnings("hiding")
	@Override
	protected <T extends Comparable<T>> void sort(T[] array) {
		int length = array.length;
		int h = 1;
		while (h < length / 3) {
			h = 3 * h + 1;
		}
		while (h >= 1) {
			for (int i = h; i < length; i++) {
				for (int j = i; j >= h && lessThan(array[j], array[j - h]); j -= h) {
					swap(array, j, j - h);
				}
			}
			h /= 3;
		}

	}

}

快速排序
package my.sort;

public class QuickSort<T> extends BaseSort<T> {

	@SuppressWarnings("hiding")
	@Override
	protected <T extends Comparable<T>> void sort(T[] array) {
		sort(array, 0, array.length - 1);
	}

	@SuppressWarnings("hiding")
	private <T extends Comparable<T>> void sort(T[] array, int low, int high) {
		if (high <= low)
			return;
		int j = partition(array, low, high);
		sort(array, low, j - 1);
		sort(array, j + 1, high);
	}

	@SuppressWarnings("hiding")
	private <T extends Comparable<T>> int partition(T[] array, int low, int high) {
		int i = low;
		int j = high + 1;

		T v = array[low];

		while (true) {
			while (lessThan(array[++i], v)) {
				if (i == high)
					break;
			}

			while (lessThan(v, array[--j])) {
				if (j == low)
					break;
			}

			if (i >= j)
				break;

			swap(array, i, j);
		}

		swap(array, low, j);

		return j;

	}
}


归并排序

package my.sort;

/**
 * 自顶向下的归并排序
 * 
 * @author Eric
 * @param <T>
 */
public class MergeSort<T> extends BaseSort<T> {

	@SuppressWarnings("unchecked")
	private Comparable[] aux = null; // 归并所需的辅助数组

	@SuppressWarnings("hiding")
	@Override
	protected <T extends Comparable<T>> void sort(T[] array) {
		int length = array.length;
		aux = new Comparable[length];
		doSort(array, 0, length - 1);

	}

	@SuppressWarnings("hiding")
	private <T extends Comparable<T>> void doSort(T[] array, int low, int high) {
		if (low < high) {

			// 找出中间索引
			int mid = low + (high - low) / 2;

			// 对左边数组进行递归
			doSort(array, low, mid);

			// 对右边数组进行递归
			doSort(array, mid + 1, high);

			// 合并
			doMerge(array, low, mid, high);
		}

	}

	@SuppressWarnings( { "hiding", "unchecked" })
	private <T extends Comparable<T>> void doMerge(T[] array, int low, int mid,
			int high) {
		// 将array[low...mid]和[mid+1...high]归并
		int i = low;
		int j = mid + 1;

		/* 将array[low...high]复制到aux[low...high] */
		for (int k = low; k <= high; k++) {
			aux[k] = array[k];
		}

		for (int k = low; k <= high; k++) {
			if (i > mid) {
				array[k] = (T) aux[j++];
			} else if (j > high) {
				array[k] = (T) aux[i++];
			} else if (lessThan(aux[j], aux[i])) {
				array[k] = (T) aux[j++];
			} else {
				array[k] = (T) aux[i++];
			}
		}
	}

/*	public static void main(String[] args) {

		String[] array = { "Hello", "World", "Eric", "Allen" };
		MergeSort<String> sort = new MergeSort<String>();
		sort.printArray(array);
		sort.sort(array);
		sort.printArray(array);
	}*/

}


堆排序
package my.sort;

public class HeapSort<T> extends BaseSort<T> {

	@SuppressWarnings("hiding")
	@Override
	protected <T extends Comparable<T>> void sort(T[] array) {

		int length = array.length;

		buildHeap(array, length);

		while (length > 1) {
			length--;
			swap(array, 0, length);
			downHeap(array, length, 0);
		}

	}

	@SuppressWarnings("hiding")
	private <T extends Comparable<T>> void buildHeap(T[] array, int length) {
		for (int v = length / 2 - 1; v >= 0; v--) {
			downHeap(array, length, v);
		}
	}

	@SuppressWarnings("hiding")
	private <T extends Comparable<T>> void downHeap(T[] array, int length, int v) {

		int w = 2 * v + 1;
		while (w < length) {

			if ((w + 1 < length) && greatThan(array[w + 1], array[w])) {
				w++;
			}

			if (!lessThan(array[v], array[w])) {
				return;
			}
			swap(array, v, w);
			v = w;
			w = 2 * v + 1;

		}
	}

}


测试代码比如:   
  public static void main(String[] args) {

	 String[] array = { "Hello", "World", "Eric", "Allen" };
	 HeapSort<String> sort = new HeapSort<String>();
	 sort.printArray(array);
	 sort.sort(array);
	 sort.printArray(array);
     }


下面是几个算法的一些比较。



已有 0 人发表留言,猛击->> 这里<<-参与讨论


ITeye推荐



相关 [排序算法] 推荐:

排序算法

- - 互联网 - ITeye博客
排序算法有很多,所以在特定情景中使用哪一种算法很重要. 为了选择合适的算法,可以按照建议的顺序考虑以下标准: .     对于数据量较小的情形,(1)(2)差别不大,主要考虑(3);而对于数据量大的,(1)为首要.  一、冒泡(Bubble)排序——相邻交换 .  二、选择排序——每次最小/大排在相应的位置 .

排序算法 Sleep Sort

- Jeff - 酷壳 - CoolShell.cn
排序算法好像是程序员学习编程最多的算法,也可能是算法研究者们最喜欢研究的算法了. 排序有很多很多的算法,比如,冒泡,插入,选择,堆,快速,归并等等(你可以看看本站以前的那些文章:可视化的排序,排序算法比较,显示排序过程的python)这里向大家介绍一个“巨NB”的排序算法——Sleep Sort. 闲言少说,请看下面的代码(用Shell脚本写的).

“天才”排序算法:Sleepsort

- Sirius - 黑客志
4chan上某位神人发明的天才排序算法:Sleepsort,充分发挥多核威力,评论中还有更多优化版本:. TermKit: 下一代的Mac命令行/终端程序.

SegmentFault问答排序算法

- - 标点符
SegmentFault 参考了 Stack Overflow的热门算法设置了自己的排序算法,具体排序算法如下:. 对于热门文章,使用了如下公式:. views:浏览量,对浏览量做了一次去对数处理,主要是为了防止某些浏览量较大的文章异军突起,待在榜单迟迟不动. recommendScore/collectScore:文章的推荐数和收藏数,直接加和到分子中,作为文章热门程度的考虑因素.

常用排序算法小结

- - ITeye博客
离开课堂后,排序算法写的比较少了,当有排序的要求时,一般用的比较多的是直接采用Arrays.sort以及Collections.sort结合比较器来实现. Arrays工具类包含了对各种类型数组的排序,以下是Arrays中包括的sort方法:. 以下是 Collections中的sort方法,该sort方法中结合了Arrays.sort来实现的.

Java排序算法:归并排序

- - zzm
 Java排序算法(九):归并排序. 归并排序(Merge)是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的. 然后再把有序子序列合并为整体有序序列. 归 并排序是建立在归并操作上的一种有效的排序算法. 该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.

有意思的排序算法-插入排序

- - 博客园_首页
所谓排序,无非就是把一个无序的序列排成一个有序的序列,从本文开始,将着重介绍经典的一些排序算法. 插入排序,是指将待排序列中的数,一个一个插入到适当位置的过程. 说起算法的概念来,总是让人摸不着头脑,还是从生活中的例子来理解吧. 相信每个人都玩过牌,我们在开始摸牌的时候,左手是空的,牌面朝下放到桌子上,接着,一次从桌子上摸起一张牌,并将它插入到左手一把牌中的正确位置上,为了找到这张牌的正确位置,要将它与手中已有的每一张牌从右到左地进行比较,无论什么时候,左手中的牌都是排好序的,而这些牌原先都是桌子上那副牌里最顶上的一些牌.

面试算法之排序算法集锦

- - CSDN博客推荐文章
排序算法在面试过程中是经常会考的,这是很基础的,面试官觉得你应该很熟悉这些东西,如果你半个小时内写不出来,那基本就给跪了,因为这真的是狠基础狠基础的东西,所以我们得对一些基本的排序算法烂熟于胸,对这些排序思想,效率了如指掌,才能让面试官觉得你还行. 基本的排序算法有:直接插入排序,冒泡排序,简单选择排序,shell排序,归并排序,快速排序,堆排序.

利用归并排序算法对大文件进行排序

- - ITeye博客
归并排序算法介绍,请参照Wikipeida. 大文件分割成行数相等的两个小文件,使用递归一直分割到所有所有小文件低于限制行数. 两个排序好的小文件归并到大文件. 直到最后所有排序好的文件归并到输入的大文件并返回. 之前看了网上很多示例代码,写的很不简洁, 引入了过多的临时变量i, j, k等等, 导致程序基本没法看,.

Java程序员必知的8大排序算法

- - JavaRanger - 专注JAVA高性能程序开发、JVM、Mysql优化、算法
(1)基本思想:在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排. 好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数. 如此反复循环,直到全部排好顺序. //将大于temp的值整体后移一个单位. (1)基本思想:算法先将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的下标相差d.对每组中全部元素进行直接插入排序,然后再用一个较小的增量(d/2)对它进行分组,在每组中再进行直接插入排序.