Go语言视频零基础入门到精通

javalearner

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

   

    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;
               
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;
               
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
;
     }

}

六 归并排序

算法思想是每次把待排序列分成两部分，分别对这两部分递归地用归并排序，完成后把这两个子部分合并成一个
序列。
归并排序借助一个全局性临时数组来方便对子序列的归并，该算法核心在于归并。


  
package
  algorithms;


import
  java.lang.reflect.Array;


/**

  *
@author
  yovn
  *
  
*/


public
  
class
  MergeSorter
<
E
extends
  Comparable
<
E
>>
  
extends
  Sorter
<
E
>
   {

     
/*
  (non-Javadoc)
      * @see algorithms.Sorter#sort(E[], int, int)
      
*/

     @SuppressWarnings(
"
unchecked
"
)
     @Override
     
public
  
void
  sort(E[] array,
int
  from,
int
  len) {
         
if
(len
<=
1
)
return
;
         E[] temporary
=
(E[])Array.newInstance(array[
0
].getClass(),len);
         merge_sort(array,from,from
+
len
-
1
,temporary);

     }

     
private
  
final
  
void
  merge_sort(E[] array,
int
  from,
int
  to, E[] temporary) {
         
if
(to
<=
from)
         {
            
return
;
         }
         
int
  middle
=
(from
+
to)
/
2
;
         merge_sort(array,from,middle,temporary);
         merge_sort(array,middle
+
1
,to,temporary);
         merge(array,from,to,middle,temporary);
     }

     
private
  
final
  
void
  merge(E[] array,
int
  from,
int
  to,
int
  middle, E[] temporary) {
         
int
  k
=
0
,leftIndex
=
0
,rightIndex
=
to
-
from;
         System.arraycopy(array, from, temporary,
0
, middle
-
from
+
1
);
         
for
(
int
  i
=
0
;i
<
to
-
middle;i
++
)
         {
             temporary[to
-
from
-
i]
=
array[middle
+
i
+
1
];
         }
         
while
(k
<
to
-
from
+
1
)
         {
            
if
(temporary[leftIndex].compareTo(temporary[rightIndex])
<
0
)
             {
                 array[k
+
from]
=
temporary[leftIndex
++
];
                 
             }
            
else

             {
                 array[k
+
from]
=
temporary[rightIndex
--
];
             }
             k
++
;
         }
         
     }

}

七 堆排序

堆是一种完全二叉树，一般使用数组来实现。
堆主要有两种核心操作，
1）从指定节点向上调整(shiftUp)
2）从指定节点向下调整(shiftDown)
建堆，以及删除堆定节点使用shiftDwon,而在插入节点时一般结合两种操作一起使用。
堆排序借助最大值堆来实现，第i次从堆顶移除最大值放到数组的倒数第i个位置，然后shiftDown到倒数第i+1个位置,一共执行N此调整，即完成排序。
显然，堆排序也是一种选择性的排序，每次选择第i大的元素。



  
package
  algorithms;


/**

  *
@author
  yovn
  *
  
*/


public
  
class
  HeapSorter
<
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) {
         build_heap(array,from,len);

         
for
(
int
  i
=
0
;i
<
len;i
++
)
         {
            
//
swap max value to the (len-i)-th position


             swap(array,from,from
+
len
-
1
-
i);
             shift_down(array,from,len
-
1
-
i,
0
);
//
always shiftDown from 0


         }
     }

     
private
  final
  
void
  build_heap(E[] array,
int
  from,
int
  len) {
         
int
  pos
=
(len
-
1
)
/
2
;
//
we start from (len-1)/2, because branch"s node +1=leaf"s node, and all leaf node is already a heap


         
for
(
int
  i
=
pos;i
>=
0
;i
--
)
         {
             shift_down(array,from,len,i);
         }
         
     }
     
     
private
  
final
  
void
  shift_down(E[] array,
int
  from,
int
  len,
int
  pos)
     {
         
         E tmp
=
array[from
+
pos];
         
int
  index
=
pos
*
2
+
1
;
//
use left child


         
while
(index
<
len)
//
until no child


         {
            
if
(index
+
1
<
len
&&
array[from
+
index].compareTo(array[from
+
index
+
1
])
<
0
)
//
right child is bigger


             {
                 index
+=
1
;
//
switch to right child


             }
            
if
(tmp.compareTo(array[from
+
index])
<
0
)
             {
                 array[from
+
pos]
=
array[from
+
index];
                 pos
=
index;
                 index
=
pos
*
2
+
1
;
                 
             }
            
else

             {
                 
break
;
             }
            
         }
         array[from
+
pos]
=
tmp;
            
     }

     
}

八 桶式排序

桶式排序不再是基于比较的了，它和基数排序同属于分配类的排序，这类排序的特点是事先要知道待排序列的一些特征。
桶式排序事先要知道待排序列在一个范围内，而且这个范围应该不是很大的。
比如知道待排序列在[0,M）内，那么可以分配M个桶，第I个桶记录I的出现情况，最后根据每个桶收到的位置信息把数据输出成有序的形式。
这里我们用两个临时性数组，一个用于记录位置信息，一个用于方便输出数据成有序方式，另外我们假设数据落在0到MAX,如果所给数据不是从0开始，你可以把每个数减去最小的数。


  
package
  algorithms;


/**

  *
@author
  yovn
  *
  
*/


public
  
class
  BucketSorter {

     
     
     
public
  
void
  sort(
int
[] keys,
int
  from,
int
  len,
int
  max)
     {
         
int
[] temp
=
new
  
int
[len];
         
int
[] count
=
new
  
int
[max];
         
         
         
for
(
int
  i
=
0
;i
<
len;i
++
)
         {
             count[keys[from
+
i]]
++
;
         }
         
//
calculate position info


         
for
(
int
  i
=
1
;i
<
max;i
++
)
         {
             count
=
count
+
count[i
-
1
];
//
this means how many number which is less or equals than i,thus it is also position + 1


         }
         
         System.arraycopy(keys, from, temp,
0
, len);
         
for
(
int
  k
=
len
-
1
;k
>=
0
;k
--
)
//from the ending to beginning can keep the stability


         {
             keys[
--
count[temp[k]]]
=
temp[k];
//
  position +1 =count


         }
     }
     
/**

      *
@param
  args
      
*/

     
public
  
static
  
void
  main(String[] args) {

         
int
[] a
=
{
1
,
4
,
8
,
3
,
2
,
9
,
5
,
0
,
7
,
6
,
9
,
10
,
9
,
13
,
14
,
15
,
11
,
12
,
17
,
16
};
         BucketSorter sorter
=
new
  BucketSorter();
         sorter.sort(a,
0
,a.length,
20
);
//
actually is 18, but 20 will also work


         
         
         
for
(
int
  i
=
0
;i
<
a.length;i
++
)
         {
             System.out.print(a
+
"
,
"
);
         }

     }

}

九 基数排序

基数排序可以说是扩展了的桶式排序，比如当待排序列在一个很大的范围内，比如0到999999内，那么用桶式排序是很浪费空间的。而基数排序把每个排序码拆成由d个排序码，比如任何一个6位数（不满六位前面补0）拆成6个排序码，分别是个位的，十位的，百位的。。。。
排序时，分6次完成，每次按第i个排序码来排。
一般有两种方式:
1) 高位优先(MSD)： 从高位到低位依次对序列排序
2）低位优先(LSD)： 从低位到高位依次对序列排序
计算机一般采用低位优先法（人类一般使用高位优先），但是采用低位优先时要确保排序算法的稳定性。
基数排序借助桶式排序，每次按第N位排序时，采用桶式排序。对于如何安排每次落入同一个桶中的数据有两种安排方法：
1）顺序存储：每次使用桶式排序，放入r个桶中，，相同时增加计数。
2）链式存储：每个桶通过一个静态队列来跟踪。



  
package
  algorithms;


import
  java.util.Arrays;



/**

  *
@author
  yovn
  *
  
*/


public
  
class
  RadixSorter {
     
     
public
  
static
  
boolean
  USE_LINK
=
true
;
     
     
/**

      *
      *
@param
  keys
      *
@param
  from
      *
@param
  len
      *
@param
  radix  key"s radix
      *
@param
  d      how many sub keys should one key divide to
      
*/

     
public
  
void
  sort(
int
[] keys,
int
  from ,
int
  len,
int
  radix,
int
  d)
     {
         
if
(USE_LINK)
         {
             link_radix_sort(keys,from,len,radix,d);
         }
         
else

         {
             array_radix_sort(keys,from,len,radix,d);
         }
         
     }
     
     
     
private
  
final
  
void
  array_radix_sort(
int
[] keys,
int
  from,
int
  len,
int
  radix,
            
int
  d)
     {
         
int
[] temporary
=
new
  
int
[len];
         
int
[] count
=
new
  
int
[radix];
         
int
  R
=
1
;
         
         
for
(
int
  i
=
0
;i
<
d;i
++
)
         {
             System.arraycopy(keys, from, temporary,
0
, len);
             Arrays.fill(count,
0
);
            
for
(
int
  k
=
0
;k
<
len;k
++
)
             {
                 
int
  subkey
=
(temporary[k]
/
R)
%
radix;
                 count[subkey]
++
;
             }
            
for
(
int
  j
=
1
;j
<
radix;j
++
)
             {
                 count[j]
=
count[j]
+
count[j
-
1
];
             }
            
for
(
int
  m
=
len
-
1
;m
>=
0
;m
--
)
             {
                 
int
  subkey
=
(temporary[m]
/
R)
%
radix;
                 
--
count[subkey];
                 keys[from
+
count[subkey]]
=
temporary[m];
             }
             R
*=
radix;
         }
            
     }


     
private
  
static
  
class
  LinkQueue
     {
         
int
  head
=-
1
;
         
int
  tail
=-
1
;
     }
     
private
  
final
  
void
  link_radix_sort(
int
[] keys,
int
  from,
int
  len,
int
  radix,
int
  d) {
         
         
int
[] nexts
=
new
  
int
[len];
         
         LinkQueue[] queues
=
new
  LinkQueue[radix];
         
for
(
int
  i
=
0
;i
<
radix;i
++
)
         {
             queues
=
new
  LinkQueue();
         }
         
for
(
int
  i
=
0
;i
<
len
-
1
;i
++
)
         {
             nexts
=
i
+
1
;
         }
         nexts[len
-
1
]
=-
1
;
         
         
int
  first
=
0
;
         
for
(
int
  i
=
0
;i
<
d;i
++
)
         {
             link_radix_sort_distribute(keys,from,len,radix,i,nexts,queues,first);
             first
=
link_radix_sort_collect(keys,from,len,radix,i,nexts,queues);
         }
         
int
[] tmps
=
new
  
int
[len];
         
int
  k
=
0
;
         
while
(first
!=-
1
)
         {
         
             tmps[k
++
]
=
keys[from
+
first];
             first
=
nexts[first];
         }
         System.arraycopy(tmps,
0
, keys, from, len);
         
         
     }
     
private
  
final
  
void
  link_radix_sort_distribute(
int
[] keys,
int
  from,
int
  len,
            
int
  radix,
int
  d,
int
[] nexts, LinkQueue[] queues,
int
  first) {
         
         
for
(
int
  i
=
0
;i
<
radix;i
++
)queues.head
=
queues.tail
=-
1
;
         
while
(first
!=-
1
)
         {
            
int
  val
=
keys[from
+
first];
            
for
(
int
  j
=
0
;j
<
d;j
++
)val
/=
radix;
             val
=
val
%
radix;
            
if
(queues[val].head
==-
1
)
             {
                 queues[val].head
=
first;
             }
            
else
  
             {
                 nexts[queues[val].tail]
=
first;
                 
             }
             queues[val].tail
=
first;
             first
=
nexts[first];
         }
         
     }
     
private
  
int
  link_radix_sort_collect(
int
[] keys,
int
  from,
int
  len,
            
int
  radix,
int
  d,
int
[] nexts, LinkQueue[] queues) {
         
int
  first
=
0
;
         
int
  last
=
0
;
         
int
  fromQueue
=
0
;
         
for
(;(fromQueue
<
radix
-
1
)
&&
(queues[fromQueue].head
==-
1
);fromQueue
++
);
         first
=
queues[fromQueue].head;
         last
=
queues[fromQueue].tail;
         
         
while
(fromQueue
<
radix
-
1
&&
queues[fromQueue].head
!=-
1
)
         {
             fromQueue
+=
1
;
            
for
(;(fromQueue
<
radix
-
1
)
&&
(queues[fromQueue].head
==-
1
);fromQueue
++
);
            
             nexts[last]
=
queues[fromQueue].head;
             last
=
queues[fromQueue].tail;
            
         }
         
if
(last
!=-
1
)nexts[last]
=-
1
;
         
return
  first;
     }
     
     
/**

      *
@param
  args
      
*/

     
public
  
static
  
void
  main(String[] args) {
         
int
[] a
=
{
1
,
4
,
8
,
3
,
2
,
9
,
5
,
0
,
7
,
6
,
9
,
10
,
9
,
135
,
14
,
15
,
11
,
222222222
,
1111111111
,
12
,
17
,
45
,
16
};
         USE_LINK
=
true
;
         RadixSorter sorter
=
new
  RadixSorter();
         sorter.sort(a,
0
,a.length,
10
,
10
);
         
for
(
int
  i
=
0
;i
<
a.length;i
++
)
         {
             System.out.print(a
+
"
,
"
);
         }


     }

}




  
  
   
   

     
   

     
   
  

复制代码

源码下载：http://file.javaxxz.com/2014/11/5/000229875.zip