Java实现的八种排序算法Word文档格式.docx
《Java实现的八种排序算法Word文档格式.docx》由会员分享，可在线阅读，更多相关《Java实现的八种排序算法Word文档格式.docx（27页珍藏版）》请在冰点文库上搜索。
10.
11./**
12.*交换数组中的两个数
13.*/
14.publicstaticvoidswap（int[]data,intindex1,intindex2）{
15.inttemp=data[index1];
16.data[index1]=data[index2];
17.data[index2]=temp;
18.}
19.
20.}
importjava.util.Random;
publicclassBubbleSort{
/**
*改进的冒泡排序算法
*通过标志位flag避免无谓的比较
*/
publicstaticvoidbubbleSort（int[]data）{
booleanflag=true;
for（inti=0;
i++）{
flag=false;
for（intj=data.length-1;
j--）{
if（data[j]<
data[j-1]）{
swap（data,j-1,j）;
flag=true;
}
}
}
}
*交换数组中的两个数
publicstaticvoidswap（int[]data,intindex1,intindex2）{
inttemp=data[index1];
data[index1]=data[index2];
data[index2]=temp;
}
2、选择排序
时间复杂度为O（n^2），但性能上优于冒泡排序。
选择排序法就是通过n-i-1次关键字的比较，从n-i-1个关键字中选出关键字最小的记录，并和第i个记录交换。
3.publicclassSelectSort{
6.*选择排序算法
7.*/
8.publicstaticvoidselectSort（int[]data）{
9.for（inti=0;
data.length;
10.for（intj=i+1;
j<
j++）{
11.if（data[j]<
data[i]）{
12.swap（data,i,j）;
13.}
14.}
15.}
16.}
17.
18./**
19.*交换数组中的两个数
20.*/
21.publicstaticvoidswap（int[]data,intindex1,intindex2）{
22.inttemp=data[index1];
23.data[index1]=data[index2];
24.data[index2]=temp;
25.}
26.
27.}
publicclassSelectSort{
*选择排序算法
publicstaticvoidselectSort（int[]data）{
for（intj=i+1;
j++）{
data[i]）{
swap（data,i,j）;
3、插入排序
时间复杂度为O（n^2），但比冒泡和选择排序的性能要好一些。
插入排序的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。
3.publicclassInsertSort{
6.*插入排序算法
1.publicstaticvoidinsertSort（int[]data）{
1.for（inti=1;
1.for（intj=i;
0&
data[j]<
data[j-1];
8.
1.publicstaticvoidswap（int[]data,intindex1,intindex2）{
2.inttemp=data[index1];
3.data[index1]=data[index2];
4.data[index2]=temp;
5.}
9.
10.}
publicclassInsertSort{
*插入排序算法
publicstaticvoidinsertSort（int[]data）{
for（inti=1;
for（intj=i;
4、希尔排序
D.L.Shell于1959年提出的一种排序算法，时间复杂度为O（n^k），1<
k<
2，是突破时间复杂度为O（n^2）的首批算法之一。
希尔排序所需要比较的记录是跳跃式的移动，因此并不是一种稳定的排序算法。
希尔排序可以看作是对插入排序的一种改进，采取跳跃分割的策略，将相距某个“增量”的记录组成一个子序列，这样保证在子序列内分别进行直接插入排序后得到的结果是基本有序，从而减少交换次数，提高排序效率。
3.publicclassShellSort{
6.*希尔排序
7.*i为增量，增量排序的最后一个增量必须为1才行
1.publicstaticvoidshellSort（int[]data）{
1.for（intinc=data.length/2;
inc>
0;
inc/=2）{
1.for（intstart=0;
start<
inc;
start++）{
1.insertSort（data,start,inc）;
10./**
11.*以start为起点，inc为间隔进行插入排序
12.*/
1.privatestaticvoidinsertSort（int[]data,intstart,intinc）{
1.for（inti=start+inc;
i+=inc）{
（j>
=inc）&
（data[j]<
data[j-inc]）;
j-=inc）{
1.swap（data,j,j-inc）;
13.
publicclassShellSort{
*希尔排序
*i为增量，增量排序的最后一个增量必须为1才行
publicstaticvoidshellSort（int[]data）{
for（intinc=data.length/2;
inc/=2）{
for（intstart=0;
start++）{
insertSort（data,start,inc）;
*以start为起点，inc为间隔进行插入排序
privatestaticvoidinsertSort（int[]data,intstart,intinc）{
for（inti=start+inc;
i+=inc）{
for（intj=i;
j-=inc）{
swap（data,j,j-inc）;
5、堆排序
堆排序就是利用堆（假设利用大顶堆）进行排序的方法。
它的基本思想是，将带排序的序列构造成一个大顶堆。
此时，整个序列的最大值就是堆顶的根节点。
将它移走（将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次大值，如此反复执行，便能得到一个有序序列了。
堆排序无论是最好、最坏和平均时间复杂度均为O（nlogn），空间复杂度上，它只有一个用来交换的暂存单元，也非常不错。
但由于记录的比较和交换是跳跃式进行，因此堆排序也是一种不稳定的排序方法。
3.
4.publicclassHeapSort{
5.
6./**
7.*堆排序
1.
6.
7.
11.
12.
14.publicstaticvoidheapSort（int[]data）{
1.for（inti=data.length/2;
i>
=0;
i--）{
1.heapAdjust（data,i,data.length）;
3.for（inti=data.length-1;
1.swap（data,0,i）;
2.heapAdjust（data,0,i）;
4.}
11.*调整数组data[start..end]中的关键字，使之成为一个大顶堆
1.privatestaticvoidheapAdjust（int[]data,intstart,intend）{
1.inttemp,child;
2.for（temp=data[start];
leftChild（start）<
end;
start=child）{
1.child=leftChild（start）;
2.//调整child，使其指向最大那个子节点
3.if（child!
=end-1&
data[child]<
data[child+1]）child++;
4.//start既可是最初要调整的节点索引，也可是子节点索引
5.if（temp<
data[child]）data[start]=data[child];
6.elsebreak;
4.data[start]=temp;
14./**
15.*返回左子树的索引
16.*/
17.privatestaticintleftChild（inti）
18.{
19.return2*i;
21.
22./**
23.*交换数组中的两个数
24.*/
25.publicstaticvoidswap（int[]data,intindex1,intindex2）{
26.inttemp=data[index1];
27.data[index1]=data[index2];
28.data[index2]=temp;
29.}
30.
31.}
publicclassHeapSort{
*堆排序
publicstaticvoidheapSort（int[]data）{
for（inti=data.length/2;
i--）{
heapAdjust（data,i,data.length）;
for（inti=data.length-1;
swap（data,0,i）;
heapAdjust（data,0,i）;
*调整数组data[start..end]中的关键字，使之成为一个大顶堆
privatestaticvoidheapAdjust（int[]data,intstart,intend）{
inttemp,child;
for（temp=data[start];
start=child）{
child=leftChild（start）;
//调整child，使其指向最大那个子节点
if（child!
data[child+1]）
child++;
//start既可是最初要调整的节点索引，也可是子节点索引
if（temp<
data[child]）
data[start]=data[child];
else
break;
data[start]=temp;
*返回左子树的索引
privatestaticintleftChild（inti）
{
return2*i+1;
6、归并排序
归并排序就是利用归并的思想实现的排序方法。
它的原理是假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n/2]个长度为2或1的有序子序列；
在两两归并，……，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法成为2路归并排序。
归并排序的最好、最坏、平均的时间复杂度都是O（nlogn）。
由于归并排序在归并过程中需要与原始记录序列同样数量的存储空间存放归并结果以及递归时深度为logn的栈空间，因此空间复杂度为O（n+logn）。
另外，归并排序的merge函数中有if（data[leftPos]<
=data[rightPos]）的语句，这就是它需要两两比较，不存在跳跃，因此归并排序是一种稳定的排序算法。
2.publicclassMergeSort{
3.publicstaticvoidmergeSort（int[]data）{
4.int[]tempArray=newint[data.length];
5.mergeSort（data,tempArray,0,data.length-1）;
6.}
7.privatestaticvoidmergeSort（int[]data,int[]tempArray,intleft,intright）{
8.if（left<
right）{
9.intcenter=（left+right）/2;
10.mergeSort（data,tempArray,left,center）;
11.mergeSort（data,tempArray,center+1,right）;
12.merge（data,tempArray,left,center+1,right）;
15.
16./**
17.*归并算法
18.*/
19.privatestaticvoidmerge（int[]data,int[]tempArray,intleftPos,intrightPos,intrightEnd）
20.{
21.intleftEnd=rightPos-1;
22.inttempPos=leftPos;
23.intnumElements=rightEnd-leftPos+1;
24.//主循环
25.while（leftPos<
=leftEnd&
rightPos<
=rightEnd）{
26.if（data[leftPos]<
=data[rightPos]）
27.tempArray[tempPos++]=data[leftPos++];
28.else
29.tempArray[tempPos++]=data[rightPos++];
30.}
31.//复制剩余部分到tempArray
32.while（leftPos<
=leftEnd）
33.tempArray[tempPos++]=data[leftPos++];
34.while（rightPos<
=rightEnd）
35.tempArray[tempPos++]=data[rightPos++];
36.//复制tempArray回原数组
37.for（inti=0;
numElements;
i++,rightEnd--）
38.data[rightEnd]=tempArray[rightEnd];
39.}
40.
41.}
publicclassMergeSort{
*归并排序
publicstaticvoidmergeSort（int[]data）{
int[]tempArray=newint[data.length];
mergeSort（data,tempArray,0,data.length-1）;
*递归调用
privatestaticvoidmergeSort（int[]data,int[]tempArray,intleft,intright）{
if（left<
right）{
intcenter=（left+right）/2;
mergeSort（data,tempArray,left,center）;
升级会员 