-
java
排序算法大全
为了便于管理，先引入个基础类：
package algorithms;
public
abstract
class
<
br>这样可使
Shell
(from
Sorter
extends
Comparable
public
abstract
void
sort(E[]
array,
int
from
,
int
len);
public
final
void
sort(E[] array)
{
sort(array,0,);
}
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
extends
Comparable
extends
Sorter
/* (non-
Javadoc)
* @see #sort(E[], int,
int)
*/
public
void
sort(E[] array,
int
from,
int
len) {
E tmp=
null
;
for
(
int
i=from+1;i
{
tmp=array[i];
int
j=i;
for
(;j>from;j--)
{
if
(eTo(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
extends
Comparable
extends
Sorter
private
static
boolean
DWON=
true
;
public
final
void
bubble_down(E[] array,
int
from,
int
len)
{
for
(
int
i=from;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
{
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
extends
Comparable
extends
Sorter
/* (non-
Javadoc)
* @see #sort(E[], int,
int)
*/
@Override
public
void
sort(E[] array,
int
from,
int
len) {
for
(
int
i=0;i
{
int
smallest=i;
int
j=i+from;
for
(;j
{
if
(array[j].compareTo(array[
smallest])<0)
{
smallest=j;
}
}
swap(array,i,smallest);
}
}
}
四
Shell
排序
Shell
排序可以理解为插入排序
的变种，它充分利用了插入排序的两个特点：
1
）当数据规模小的时候非常高效
<
/p>
2
）当给定数据已经有序时的时间代价为
O(N)
所以，
Shell
排序每次
把数据分成若个小块，来使用插入排序，而且之后在这若个小块排好
序的情况下把它们合
成大一点的小块，
继续使用插入排序，
不停的合并小块，
知道最后成一
个块，并使用插入排序。
这里每次分成若干小块是通过
“
增量
”
来控制的，开始时增量交大，接近
N/2,
从而使得分割
出来接近
N/2
个小块，逐渐的减小
“
增量
“
最终到减小到
1
。
一直较好的增
量序列是
2^k-1,2^(k-1)-1,.....7,3,1,
Shell
排序时间复杂度达到
O(N^
1.5)
所以我在实现
排序的时候采用该增量序列
package
algorithms;
/**
*
@author
yovn
*/
public
class
ShellSorter
extends
Comparable
extends
Sorter
/* (non-
Javadoc)
* Our delta value choose
2^k-1,2^(k-1)-1,
* complexity is
O(n^1.5)
* @see #sort(E[], int,
int)
*/
@Override
.7,3,1.
public
void
sort(E[] array,
int
from,
int
len) {
//ate the first
delta value;
int
value=1;
while
((value+1)*2
{
value=(value+1)*2-1;
}
for
(
int
delta=value;delta>=1;delta=(delta+1)/2-1)
{
for
(
int
i=0;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<
/p>
;
E
tmp=
null
;
for
(
int
i=from+delta;i
{
tmp=array[i];
int
j=i;
for
(;j>from;j-=delta)
{
if
(eTo(array[j-delta])<0)
{
array[j]=array[j-delta];
}
else
break
;
}
array[j]=tmp;
}
}
}
五
快速排序
快速排序是目前使用可能最广泛的排序算法了。
一般分如下步骤：
1
）选择一个枢纽元素（有很对选法，我的实现里采用去中间元素的简单方法）
2
）使用该枢纽元素分割数组，使得比该元素小的元素在它的左
边，比它大的在右边。并把
枢纽元素放在合适的位置。
3
）根据枢纽元素最后确定的位置，把数组分成三部分，左边的，右边
的，枢纽元素自己，
对左边的，右边的分别递归调用快速排序算法即可。
快速排序的核心在于分割算法，也可以说是最有技巧的部分。
package
algorithms;
/**
*
@author
yovn
*
*/
public
class
QuickSorter
extends
Comparable
extends
Sorter
/* (non-
Javadoc)
* @see #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
if
(from
{
array[to]=array[from];
//now from's
position is available
to--;
}
while
(from
if
(from
{
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
/**
*
@author
yovn
*
*/
public
class
MergeSorter
extends
Comparable
extends
Sorter
/* (non-
Javadoc)
* @see #sort(E[], int,
int)
*/
@SuppressWarnings(
@Override
public
void
sort(E[] array,
int
from,
int
len) {
if
(len<=1)
return<
/p>
;
E[]
temporary=(E[])tance(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;
opy(array, from, temporary, 0, middle-from+1);
for
(
int
i=0;i
{
temporary[to-from-i]=array[middle+i+1];
}
while
(k
{
if
(temporary[leftIndex].compareTo(
temporary[rightIndex])<0)
{
array[k+from]=temporary[leftIndex++];
}
else
{
array[k+from]=temporary[rightIndex--];
}
k++;
}
}
-
-
-
-
-
-
-
-
-
上一篇：三个女婿笑话大全
下一篇：yes,minister转帖学习笔记