排序算法总结Java篇.docx
《排序算法总结Java篇.docx》由会员分享，可在线阅读，更多相关《排序算法总结Java篇.docx（22页珍藏版）》请在冰点文库上搜索。
排序算法总结Java篇
排序算法总结-Java篇
1.插入排序
基本操作：
将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。
时间复杂度：
算法适用于少量数据的排序，时间复杂度为O（n^2）。
稳定性：
稳定。
实现：
1.首先新建一个空列表，用于保存已排序的有序数列（我们称之为"有序列表"）。
2.从原数列中取出一个数，将其插入"有序列表"中，使其仍旧保持有序状态。
3.重复2号步骤，直至原数列为空。
插入排序的工作原理与打牌时整理手中的牌的做法类似，开始摸牌时，我们的左手是空的，接着一次从桌上摸起一张牌，并将它插入到左手的正确位置。
为了找到这张牌的正确位置，要将它与手中已有的牌从右到左进行比较，无论什么时候手中的牌都是排序好的。
Java程序代码：
//插入排序
packageSort;
publicclassInsertSort{
publicstaticvoidmain（String[]args）{
intt,temp,i,j;
t=args.length;//输入数据的元素个数
intnum[]=newint[t];//创建数组
System.out.println（"排序前：
"）;
for（i=0;inum[i]=Integer.parseInt（args[i]）;
System.out.print（num[i]+""）;
}
System.out.println（""）;
//执行插入排序
for（i=1;ifor（j=i;j>0;j--）{
if（num[j]temp=num[j];
num[j]=num[j-1];
num[j-1]=temp;
}
else{
break;
}
}
System.out.print（"第"+（i+1）+"次排序结果：
"）;
for（inta=0;aSystem.out.print（num[a]+""）;
}
System.out.println（""）;
}
//输出排序结果
System.out.println（"\n排序后：
"）;
for（i=0;iSystem.out.print（num[i]+""）;
}
}
}
2.冒泡排序
冒泡排序（BubbleSort）是一种简单的排序算法。
它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序算法的运作如下:
1.比较相邻的元素。
如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。
在这一点，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
时间复杂度
若文件的初始状态是正序的，一趟扫描即可完成排序。
所需的关键字比较次数
和记录移动次数
均达到最小值：
，
。
所以，冒泡排序最好的时间复杂度为
。
若初始文件是反序的，需要进行
趟排序。
每趟排序要进行
次关键字的比较（1≤i≤n-1），且每次比较都必须移动记录三次来达到交换记录位置。
在这种情况下，比较和移动次数均达到最大值：
冒泡排序的最坏时间复杂度为
。
综上，因此冒泡排序总的平均时间复杂度为
。
稳定性：
稳定。
Java程序代码：
//冒泡排序
packageSort;
publicclassBubbleSort{
publicstaticvoidmain（String[]args）{
intt=args.length;//输入数据的元素个数
intscore[]=newint[t];
//排序前
System.out.println（"排序前：
"）;
for（inti=0;iscore[i]=Integer.parseInt（args[i]）;
System.out.print（score[i]+""）;
}
System.out.println（""）;
//执行冒泡排序
for（inti=0;ifor（intj=0;jif（score[j]inttemp=score[j];
score[j]=score[j+1];
score[j+1]=temp;
}
}
System.out.print（"第"+（i+1）+"次排序结果：
"）;
for（inta=0;aSystem.out.print（score[a]+""）;
}
System.out.println（""）;
}
//排序后
System.out.print（"最终排序结果：
"）;
for（inta=0;aSystem.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）的。
稳定性：
不稳定。
Java程序代码：
//选择排序
packageSort;
publicclassSelectSort{
publicstaticvoidmain（String[]args）{
intt,i;
t=args.length;//输入数据的元素个数
intnum[]=newint[t];//创建数组
System.out.println（"排序前：
"）;
for（i=0;inum[i]=Integer.parseInt（args[i]）;
System.out.print（num[i]+""）;
}
System.out.println（""）;
//执行排序
Sort（num）;
//输出排序结果
System.out.println（"\n排序后：
"）;
for（i=0;iSystem.out.print（num[i]+""）;
}
}
//选择排序方法
publicstaticvoidSort（int[]sort）{
for（inti=0;ifor（intj=i+1;jif（sort[i]>sort[j]）{
inttemp;
temp=sort[i];
sort[i]=sort[j];
sort[j]=temp;
}
}
System.out.print（"第"+（i+1）+"次排序结果：
"）;
for（inta=0;aSystem.out.print（sort[a]+""）;
}
System.out.println（""）;
}
}
}
4.快速排序
快速排序是所有排序算法中最高效的一种。
它采用了分治的思想：
先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序，这样整个列表就有序了。
这是一种先进的思想，也是它高效的原因。
因为在排序算法中，算法的高效与否与列表中数字间的比较次数有直接的关系，而"保证列表的前半部分都小于后半部分"就使得前半部分的任何一个数从此以后都不再跟后半部分的数进行比较了，大大减少了数字间不必要的比较。
但查找数据得另当别论了。
时间复杂度：
O（nlogn）。
稳定性：
不稳定。
Java程序代码：
//快速排序
packageSort;
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{
while（low=key）
hight--;
sortArray[low]=sortArray[hight];
while（lowlow++;
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;i{
System.out.print（data[i]）;
System.out.print（""）;
}
}
}
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]调整为堆。
……
直到无序区只有一个元素为止。
时间复杂度：
O（nlogn）。
稳定性：
不稳定。
Java程序代码：
//堆排序（大顶堆）
packageSort;
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{
largest=left;
}
if（right{
largest=right;
}
//得到最大值后可能需要交换，如果交换了，其子节点可能就不是最大堆了，需要重新调整
if（largest!
=index）
{
inttemp=data[index];
data[index]=data[largest];
data[largest]=temp;
maxHeapify（data,heapSize,largest）;
}
}
/**
*排序，最大值放在末尾，data虽然是最大堆，在排序后就成了递增的
*
*@paramdata
*/
privatestaticvoidheapSort（int[]data）
{
//末尾与头交换，交换后调整最大堆
for（inti=data.length-1;i>0;i--）
{
inttemp=data[0];
data[0]=data[i];
data[i]=temp;
maxHeapify（data,i,0）;
}
}
/**
*父节点位置
*
*@paramcurrent
*@return
*/
privatestaticintgetParentIndex（intcurrent）
{
return（current-1）>>1;
}
/**
*左子节点position注意括号，加法优先级更高
*
*@paramcurrent
*@return
*/
privatestaticintgetChildLeftIndex（intcurrent）
{
return（current<<1）+1;
}
/**
*右子节点position
*
*@paramcurrent
*@return
*/
privatestaticintgetChildRightIndex（intcurrent）
{
return（current<<1）+2;
}
privatestaticvoidprint（int[]data）
{
intpre=-2;
for（inti=0;i{
if（pre<（int）getLog（i+1））
{
pre=（int）getLog（i+1）;
System.out.println（）;
}
System.out.print（data[i]+"|"）;
}
}
/**
*以2为底的对数
*
*@paramparam
*@return
*/
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的单元。
时间复杂度：
O（nlogn）。
稳定性：
稳定。
Java程序代码：
/**归并排序*/
packageSort;
publicclassMergeSort
{
/**
*
* 二路归并
* 原理：
将两个有序表合并和一个有序表
*
* @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{
if（a[i]<=a[j]）
{
tmp[k]=a[i];
k++;
i++;
}
else
{
tmp[k]=a[j];
j++;
k++;
}
}
while（i{
tmp[k]=a[i];
i++;
k++;
}
while（j<=t）
{
tmp[k]=a[j];
j++;
k++;
}
System.arraycopy（tmp,0,a,s,tmp.length）;
}
/**
* @param a
* @param s
* @param len
* 每次归并的有序集合的长度
*/
publicstaticvoidmergeSort（int[]a,ints,intlen）
{
intsize=a.length;
intmid=size/（len<<1）;
intc=size&（（len<<1）-1）;
//-------归并到只剩一个有序集合的时候结束算法-------//
if（mid==0）
return;
// ------进行一趟归并排序-------//
for（inti=0;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）;
for（inti=0;i{
System.out.print（a[i]+""）;
}
}
}
7.希尔排序
希尔排序（ShellSort）是插入排序的一种。
是针对直接插入排序算法的改进。
思想：
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。
所有距离为d1的倍数的记录放在同一个组中。
先在各组内进行直接插入排序；然后，取第二个增量d2=1（
<
…时间复杂度：
O（n^1.25）。
稳定性：
不稳定。
Java程序代码：
packageSort;
publicclassShellSort{
publicstaticvoidshellSort（int[]data）{
intj=0;
inttemp=0;
for（intincrement=data.length/2;increment>0;increment/=2）{
for（inti=increment;itemp=data[i];
fo
升级会员 