http://algs4.cs.princeton.edu/21elementary/
排序算法分析:比较(Compare),交换(Exchange),如果没有使用
选择排序:首先,找到最小的元素然后和第一个数做交换,然后在剩下的元素里找最小的,和第二个数做交换,一直下去。
选择排序用了: ~N2/2 次比较(compares)and N 次 交换(exchanges)
插入排序:按先后顺序取出一个数,将其插入到已经有序的队列中,然后再去下个,扑克牌就是这样。
插入排序: 平均 ~N2/4 compares and ~N2/4 exchanges .
最坏~ N2/2 compares and ~N2/2 exchanges
最好 N-1 compares and 0 exchanges.
Shell排序:
h-sorted: 以h作为间隔,将这些对象排序。
做几次h-sorted且最后一次是1-sorted,这就是shell排序:
原文:http://www.cnblogs.com/ming11/p/3705836.html