为了便于管理，先引入个基础类：

package

 algorithms;

 

 

/**

 * 

@author

 yovn

 *

 

*/

public

 

abstract

 

class

 Sorter

<

E 

extends

 Comparable

<

E

>>

 {

    

    

public

 

abstract

 

void

 sort(E[] array,

int

 from ,

int

 len);

    

    

public

 

final

 

void

 sort(E[] array)

    {

        sort(array,

0

,array.length);

    }

    

protected

 

final

 

void

 swap(E[] array,

int

 from ,

int

 to)

    {

        E tmp

=

array[from];

        array[from]

=

array[to];

        array[to]

=

tmp;

    }

 

}

一 插入排序

该算法在数据规模小的时候十分高效，该算法每次插入第K+1到前K个有序数组中一个合适位置，K从0开始到N-1,从而完成排序：

package

 algorithms;

/**

 * 

@author

 yovn

 

*/

public

 

class

 InsertSorter

<

E 

extends

 Comparable

<

E

>>

 

extends

 Sorter

<

E

>

 {

 

 

/*

 (non-Javadoc)

     * @see algorithms.Sorter#sort(E[], int, int)

     

*/

    

public

 

void

 sort(E[] array, 

int

 from, 

int

 len) {

         E tmp

=

null

;

          

for

(

int

 i

=

from

+

1

;i

<

from

+

len;i

++

)

          {

              tmp

=

array[i];

              

int

 j

=

i;

              

for

(;j

>

from;j

--

)

              {

                  

if

(tmp.compareTo(array[j

-

1

])

<

0

)

                  {

                      array[j]

=

array[j

-

1

];

                  }

                  

else

 

break

;

              }

              array[j]

=

tmp;

          }

    }

        

    

 

}

二 冒泡排序

这可能是最简单的排序算法了，算法思想是每次从数组末端开始比较相邻两元素，把第i小的冒泡到数组的第i个位置。i从0一直到N-1从而完成排序。（当然也可以从数组开始端开始比较相邻两元素，把第i大的冒泡到数组的第N-i个位置。i从0一直到N-1从而完成排序。)

 

 

package

 algorithms;

 

 

/**

 * 

@author

 yovn

 *

 

*/

public

 

class

 BubbleSorter

<

E 

extends

 Comparable

<

E

>>

 

extends

 Sorter

<

E

>

 {

 

 

private

 

static

  

boolean

 DWON

=

true

;

    

    

public

 

final

 

void

 bubble_down(E[] array, 

int

 from, 

int

 len)

    {

        

for

(

int

 i

=

from;i

<

from

+

len;i

++

)

        {

            

for

(

int

 j

=

from

+

len

-

1

;j

>

i;j

--

)

            {

                

if

(array[j].compareTo(array[j

-

1

])

<

0

)

                {

                    swap(array,j

-

1

,j);

                }

            }

        }

    }

    

    

public

 

final

 

void

 bubble_up(E[] array, 

int

 from, 

int

 len)

    {

        

for

(

int

 i

=

from

+

len

-

1

;i

>=

from;i

--

)

        {

            

for

(

int

 j

=

from;j

<

i;j

++

)

            {

                

if

(array[j].compareTo(array[j

+

1

])

>

0

)

                {

                    swap(array,j,j

+

1

);

                }

            }

        }

    }

    @Override

    

public

 

void

 sort(E[] array, 

int

 from, 

int

 len) {

        

        

if

(DWON)

        {

            bubble_down(array,from,len);

        }

        

else

        {

            bubble_up(array,from,len);

        }

    }

    

}

三，选择排序

选择排序相对于冒泡来说，它不是每次发现逆序都交换，而是在找到全局第i小的时候记下该元素位置，最后跟第i个元素交换，从而保证数组最终的有序。

相对与插入排序来说，选择排序每次选出的都是全局第i小的，不会调整前i个元素了。

package

 algorithms;

/**

 * 

@author

 yovn

 *

 

*/

public

 

class

 SelectSorter

<

E 

extends

 Comparable

<

E

>>

 

extends

 Sorter

<

E

>

 {

 

 

/*

 (non-Javadoc)

     * @see algorithms.Sorter#sort(E[], int, int)

     

*/

    @Override

    

public

 

void

 sort(E[] array, 

int

 from, 

int

 len) {

        

for

(

int

 i

=

0

;i

<

len;i

++

)

        {

            

int

 smallest

=

i;

            

int

 j

=

i

+

from;

            

for

(;j

<

from

+

len;j

++

)

            {

                

if

(array[j].compareTo(array[smallest])

<

0

)

                {

                    smallest

=

j;

                }

            }

            swap(array,i,smallest);

                   

        }

 

    }

 

}

四 Shell排序

Shell排序可以理解为插入排序的变种，它充分利用了插入排序的两个特点：

1）当数据规模小的时候非常高效

2）当给定数据已经有序时的时间代价为O(N)

所以，Shell排序每次把数据分成若个小块，来使用插入排序，而且之后在这若个小块排好序的情况下把它们合成大一点的小块，继续使用插入排序，不停的合并小块，知道最后成一个块，并使用插入排序。

 

这里每次分成若干小块是通过“增量” 来控制的，开始时增量交大，接近N/2,从而使得分割出来接近N/2个小块，逐渐的减小“增量“最终到减小到1。

一直较好的增量序列是2^k-1,2^(k-1)-1,.....7,3,1,这样可使Shell排序时间复杂度达到O(N^1.5)

所以我在实现Shell排序的时候采用该增量序列

package

 algorithms;

 

 

/**

 * 

@author

 yovn

 

*/

public

 

class

 ShellSorter

<

E 

extends

 Comparable

<

E

>>

 

extends

 Sorter

<

E

>

  {

 

 

/*

 (non-Javadoc)

     * Our delta value choose 2^k-1,2^(k-1)-1,.7,3,1.

     * complexity is O(n^1.5)

     * @see algorithms.Sorter#sort(E[], int, int)

     

*/

    @Override

    

public

 

void

 sort(E[] array, 

int

 from, 

int

 len) {

        

        

//

1.calculate  the first delta value;

        

int

 value

=

1

;

        

while

((value

+

1

)

*

2

<

len)

        {

            value

=

(value

+

1

)

*

2

-

1

;

        

        }

    

        

for

(

int

 delta

=

value;delta

>=

1

;delta

=

(delta

+

1

)

/

2

-

1

)

        {

            

for

(

int

 i

=

0

;i

<

delta;i

++

)

            {

                modify_insert_sort(array,from

+

i,len

-

i,delta);

            }

        }

 

    }

    

    

private

 

final

  

void

 modify_insert_sort(E[] array, 

int

 from, 

int

 len,

int

 delta) {

          

if

(len

<=

1

)

return

;

          E tmp

=

null

;

          

for

(

int

 i

=

from

+

delta;i

<

from

+

len;i

+=

delta)

          {

              tmp

=

array[i];

              

int

 j

=

i;

              

for

(;j

>

from;j

-=

delta)

              {

                  

if

(tmp.compareTo(array[j

-

delta])

<

0

)

                  {

                      array[j]

=

array[j

-

delta];

                  }

                  

else

 

break

;

              }

              array[j]

=

tmp;

          }

 

    }

}

五 快速排序

快速排序是目前使用可能最广泛的排序算法了。

一般分如下步骤：

1）选择一个枢纽元素（有很对选法，我的实现里采用去中间元素的简单方法）

2）使用该枢纽元素分割数组，使得比该元素小的元素在它的左边，比它大的在右边。并把枢纽元素放在合适的位置。

3）根据枢纽元素最后确定的位置，把数组分成三部分，左边的，右边的，枢纽元素自己，对左边的，右边的分别递归调用快速排序算法即可。

快速排序的核心在于分割算法，也可以说是最有技巧的部分。

package

 algorithms;

 

 

/**

 * 

@author

 yovn

 *

 

*/

public

 

class

 QuickSorter

<

E 

extends

 Comparable

<

E

>>

 

extends

 Sorter

<

E

>

 {

 

 

/*

 (non-Javadoc)

     * @see algorithms.Sorter#sort(E[], int, int)

     

*/

    @Override

    

public

 

void

 sort(E[] array, 

int

 from, 

int

 len) {

        q_sort(array,from,from

+

len

-

1

);

    }

 

 

private

 

final

 

void

 q_sort(E[] array, 

int

 from, 

int

 to) {

        

if

(to

-

from

<

1

)

return

;

        

int

 pivot

=

selectPivot(array,from,to);

 

        

        

        pivot

=

partion(array,from,to,pivot);

        

        q_sort(array,from,pivot

-

1

);

        q_sort(array,pivot

+

1

,to);

        

    }

 

 

private

 

int

 partion(E[] array, 

int

 from, 

int

 to, 

int

 pivot) {

        E tmp

=

array[pivot];

        array[pivot]

=

array[to];

//

now to's position is available

        

        

while

(from

!=

to)

        {

            

while

(from

<

to

&&

array[from].compareTo(tmp)

<=

0

)from

++

;

            

if

(from

<

to)

            {

                array[to]

=

array[from];

//

now from's position is available

                to

--

;

            }

            

while

(from

<

to

&&

array[to].compareTo(tmp)

>=

0

)to

--

;

            

if

(from

<

to)

            {

                array[from]

=

array[to];

//

now to's position is available now 

                from

++

;

            }

        }

        array[from]

=

tmp;

        

return

 from;

    }

 

 

private

 

int

 selectPivot(E[] array, 

int

 from, 

int

 to) {

    

        

return

 (from

+

to)

/

2

;

    }

 

}

还有归并排序，堆排序，桶式排序，基数排序，下次在归纳。