首页 > 代码库 > 排序-初级排序

排序-初级排序

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排序: