文档章节

常用排序算法

王孟君
 王孟君
发布于 2016/10/25 23:07
字数 1594
阅读 95
收藏 3

离开课堂后,排序算法写的比较少了,当有排序的要求时,一般用的比较多的是直接采用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;

		}
	}

}

 

排序比较

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

© 著作权归作者所有

王孟君

王孟君

粉丝 227
博文 94
码字总数 221044
作品 0
杭州
高级程序员
私信 提问

暂无文章

策略模式

策略模式封装的是算法,而状态模式侧重的对象状态的转变。 /** * 策略,定义计算报价算法的接口 */public interface Strategy { /** * 计算应报的价格 * @param goo...

铁骨铮铮
50分钟前
0
0
如何用JavaScript写一个区块链?

Part1实现一个基本的区块链 1.区块链 区块链是由一个个任何人都可以访问的区块构成的公共数据库。这好像没什么特别的,不过它们有一个有趣的属性:它们是不可变的。一旦一个区块被添加到区块...

骚年锦时
54分钟前
1
0
HTTP协议

HTTP简介 HTTP协议是Hyper Text Transfer Protocol(超文本传输协议)的缩写,是用于从万维网(WWW:World Wide Web )服务器传输超文本到本地浏览器的传送协议。 HTTP是一个基于TCP/IP通信协议...

惊尘大人
56分钟前
1
0
Feign输出Info级别日志

背景   spring cloud netfix组件中,feign相关的日志默认是不会输出的,需要自定义配置才能输出,并且Feign只对Debug基本的日志做出响应, 实际业务需要输出Info级别的日志,所以需要做自定...

xiaomin0322
今天
3
0
面向解决问题的java编程,spring boot,mybatis generator和坑-1starter

1、start一个spring boot项目 第一课我们也不能免俗,要从starter开始,spring boot的起始项目脚手架可以从spring boot官方starter生成地址开始:https://start.spring.io/ 这张图列出了一个...

wphmoon
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部