排序算法总结Java篇Word格式.docx
《排序算法总结Java篇Word格式.docx》由会员分享，可在线阅读，更多相关《排序算法总结Java篇Word格式.docx（22页珍藏版）》请在冰点文库上搜索。
}
//执行插入排序
for（i=1;
t;
i++）{
for（j=i;
j>
0;
j--）{
if（num[j]<
num[j-1]）{
temp=num[j];
num[j]=num[j-1];
num[j-1]=temp;
}
else{
break;
}
System.out.print（"
第"
+（i+1）+"
次排序结果：
for（inta=0;
a<
t;
a++）{
System.out.print（num[a]+"
}
System.out.println（"
//输出排序结果
\n排序后：
}
2.冒泡排序
冒泡排序（BubbleSort）是一种简单的排序算法。
它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序算法的运作如下:
1.比较相邻的元素。
如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。
在这一点，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
时间复杂度
若文件的初始状态是正序的，一趟扫描即可完成排序。
所需的关键字比较次数
和记录移动次数
均达到最小值：
，
。
所以，冒泡排序最好的时间复杂度为
若初始文件是反序的，需要进行
趟排序。
每趟排序要进行
次关键字的比较（1≤i≤n-1），且每次比较都必须移动记录三次来达到交换记录位置。
在这种情况下，比较和移动次数均达到最大值：
冒泡排序的最坏时间复杂度为
综上，因此冒泡排序总的平均时间复杂度为
稳定性：
Java程序代码：
//冒泡排序
publicclassBubbleSort{
publicstaticvoidmain（String[]args）{
intt=args.length;
intscore[]=newint[t];
//排序前
for（inti=0;
score[i]=Integer.parseInt（args[i]）;
System.out.print（score[i]+"
//执行冒泡排序
for（inti=0;
i<
score.length-1;
i++）{//最多做n-1趟排序
for（intj=0;
j<
score.length-i-1;
j++）{//对当前无序区间score[0......length-i-1]进行排序（j的范围很关键，这个范围是在逐步缩小的）
if（score[j]<
score[j+1]）{//把小的值交换到后面
inttemp=score[j];
score[j]=score[j+1];
score[j+1]=temp;
}
System.out.print（"
for（inta=0;
score.length;
System.out.print（score[a]+"
//排序后
最终排序结果：
3.选择排序
选择排序是这样实现的：
1.设数组内存放了n个待排数字，数组下标从1开始，到n结束。
2.初始化i=1
3.从数组的第i个元素开始到第n个元素，寻找最小的元素。
4.将上一步找到的最小元素和第i位元素交换。
5.i++,直到i=n－1算法结束，否则回到第3步
选择排序的平均时间复杂度也是O（n^2）的。
不稳定。
//选择排序
publicclassSelectSort{
intt,i;
//执行排序
Sort（num）;
//选择排序方法
publicstaticvoidSort（int[]sort）{
sort.length;
for（intj=i+1;
j<
j++）{
if（sort[i]>
sort[j]）{
inttemp;
temp=sort[i];
sort[i]=sort[j];
sort[j]=temp;
sort.length;
System.out.print（sort[a]+"
4.快速排序
快速排序是所有排序算法中最高效的一种。
它采用了分治的思想：
先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序，这样整个列表就有序了。
这是一种先进的思想，也是它高效的原因。
因为在排序算法中，算法的高效与否与列表中数字间的比较次数有直接的关系，而"
保证列表的前半部分都小于后半部分"
就使得前半部分的任何一个数从此以后都不再跟后半部分的数进行比较了，大大减少了数字间不必要的比较。
但查找数据得另当别论了。
O（nlogn）。
//快速排序
publicclassQSort
{
/**
*@paramargs
*/
publicstaticvoidmain（String[]args）
{
//TODO自动生成方法存根
quicksortqs=newquicksort（）;
intdata[]={3,1,4,6,5,2};
qs.data=data;
qs.sort（0,qs.data.length-1）;
qs.display（）;
classquicksort
publicintdata[];
privateintpartition（intsortArray[],intlow,inthight）
intkey=sortArray[low];
while（low<
hight）
hight&
&
sortArray[hight]>
=key）
hight--;
sortArray[low]=sortArray[hight];
sortArray[low]<
low++;
sortArray[hight]=sortArray[low];
sortArray[low]=key;
returnlow;
publicvoidsort（intlow,inthight）
if（low<
intresult=partition（data,low,hight）;
sort（low,result-1）;
sort（result+1,hight）;
publicvoiddisplay（）
for（inti=0;
data.length;
i++）
System.out.print（data[i]）;
5.堆排序
用大根堆排序的基本思想
①先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区
②再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key
③由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。
然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。
……
直到无序区只有一个元素为止。
//堆排序（大顶堆）
publicclassHeapSort
privatestaticint[]sort=newint[]{3,5,2,6,1,4,0};
publicstaticvoidmain（String[]args）
buildMaxHeapify（sort）;
heapSort（sort）;
print（sort）;
privatestaticvoidbuildMaxHeapify（int[]data）
//没有子节点的才需要创建最大堆，从最后一个的父节点开始
intstartIndex=getParentIndex（data.length-1）;
//从尾端开始创建最大堆，每次都是正确的堆
for（inti=startIndex;
i>
=0;
i--）
{
maxHeapify（data,data.length,i）;
*创建最大堆
*
*@paramdata
*@paramheapSize需要创建最大堆的大小，一般在sort的时候用到，因为最多值放在末尾，末尾就不再归入最大堆了
*@paramindex当前需要创建最大堆的位置
privatestaticvoidmaxHeapify（int[]data,intheapSize,intindex）
//当前点与左右子节点比较
intleft=getChildLeftIndex（index）;
intright=getChildRightIndex（index）;
intlargest=index;
if（left<
heapSize&
data[index]<
data[left]）
largest=left;
if（right<
data[largest]<
data[right]）
largest=right;
//得到最大值后可能需要交换，如果交换了，其子节点可能就不是最大堆了，需要重新调整
if（largest!
=index）
inttemp=data[index];
data[index]=data[largest];
data[largest]=temp;
maxHeapify（data,heapSize,largest）;
*排序，最大值放在末尾，data虽然是最大堆，在排序后就成了递增的
privatestaticvoidheapSort（int[]data）
//末尾与头交换，交换后调整最大堆
for（inti=data.length-1;
inttemp=data[0];
data[0]=data[i];
data[i]=temp;
maxHeapify（data,i,0）;
*父节点位置
*@paramcurrent
*@return
privatestaticintgetParentIndex（intcurrent）
return（current-1）>
>
1;
*左子节点position注意括号，加法优先级更高
privatestaticintgetChildLeftIndex（intcurrent）
return（current<
<
1）+1;
*右子节点position
privatestaticintgetChildRightIndex（intcurrent）
1）+2;
privatestaticvoidprint（int[]data）
intpre=-2;
if（pre<
（int）getLog（i+1））
{
pre=（int）getLog（i+1）;
System.out.println（）;
System.out.print（data[i]+"
|"
*以2为底的对数
*@paramparam
privatestaticdoublegetLog（doubleparam）
returnMath.log（param）/Math.log
（2）;
6.归并排序
归并排序是建立在归并操作上的一种有效的排序算法。
该算法是采用分治法（DivideandConquer）的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序列；
即先使每个子序列有序，再使子序列段间有序。
若将两个有序表合并成一个有序表，称为二路归并。
例如有两个有序表：
（7,10,13,15）和（4,8,19,20），归并后得到的有序表为：
（4,7,8,10,13,15,19,20）。
归并过程为：
比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；
否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。
/**归并排序*/
publicclassMergeSort
* <
pre>
* 二路归并
* 原理：
将两个有序表合并和一个有序表
/pre>
* @param a
* @param s
* 第一个有序表的起始下标
* @param m
* 第二个有序表的起始下标
* @param t
* 第二个有序表的结束小标
*
*/
privatestaticvoidmerge（int[]a,ints,intm,intt）
int[]tmp=newint[t-s+1];
inti=s,j=m,k=0;
while（i<
m&
j<
=t）
if（a[i]<
=a[j]）
tmp[k]=a[i];
k++;
i++;
else
tmp[k]=a[j];
j++;
m）
tmp[k]=a[i];
i++;
k++;
while（j<
tmp[k]=a[j];
j++;
System.arraycopy（tmp,0,a,s,tmp.length）;
* @param len
* 每次归并的有序集合的长度
publicstaticvoidmergeSort（int[]a,ints,intlen）
intsize=a.length;
intmid=size/（len<
1）;
intc=size&
（（len<
1）-1）;
//-------归并到只剩一个有序集合的时候结束算法-------//
if（mid==0）
return;
// ------进行一趟归并排序-------//
mid;
++i）
s=i*2*len;
merge（a,s,s+len,（len<
1）+s-1）;
// -------将剩下的数和倒数一个有序集合归并-------//
if（c!
=0）
merge（a,size-c-2*len,size-c,size-1）;
// -------递归执行下一趟归并排序------//
mergeSort（a,0,2*len）;
publicstaticvoidmain（String[]args）
int[]a=newint[]{4,3,6,1,2,5};
mergeSort（a,0,1）;
a.length;
System.out.print（a[i]+"
7.希尔排序
希尔排序（ShellSort）是插入排序的一种。
是针对直接插入排序算法的改进。
思想：
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。
所有距离为d1的倍数的记录放在同一个组中。
先在各组内进行直接插入排序；
然后，取第二个增量d2<
d1重复上述的分组和排序，直至所取的增量
=1（
…<
d2<
d1），即所有记录放在同一组中进行直接插入排序为止。
O（n^1.25）。
publicclassShellSort{
publicstaticvoidshellSort（int[]data）{
intj=0;
inttemp=0;
for（intincrement=data.length/2;
increment>
0;
increment/=2）{
for（inti=increment;
data.length;
i++）{
temp=data[i];
fo
升级会员 