面试笔试必用必须掌握的Java排序算法Word文件下载.docx
《面试笔试必用必须掌握的Java排序算法Word文件下载.docx》由会员分享，可在线阅读，更多相关《面试笔试必用必须掌握的Java排序算法Word文件下载.docx（18页珍藏版）》请在冰点文库上搜索。
而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为O（n2），因此是应该尽量避免的情况。
简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。
――按平均的空间性能来分（指的是排序过程中所需的辅助空间大小）：
1）所有的简单排序方法（包括：
直接插入、起泡和简单选择）和堆排序的空间复杂度为O
（1）；
2）快速排序为O（logn），为栈所需的辅助空间;
3）归并排序所需辅助空间最多，其空间复杂度为O（n）;
4）链式基数排序需附设队列首尾指针，则空间复杂度为O（rd）。
――排序方法的稳定性能：
1）稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。
2）当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。
3）对于不稳定的排序方法，只要能举出一个实例说明即可。
4）快速排序，希尔排序和堆排序是不稳定的排序方法。
4）插入排序：
包括直接插入排序，希尔插入排序。
直接插入排序：
将一个记录插入到已经排序好的有序表中。
1,sorted数组的第0个位置没有放数据。
2，从sorted第二个数据开始处理：
如果该数据比它前面的数据要小，说明该数据要往前面移动。
首先将该数据备份放到sorted的第0位置当哨兵。
然后将该数据前面那个数据后移。
然后往前搜索，找插入位置。
找到插入位置之后讲第0位置的那个数据插入对应位置。
O（n*n）,当待排记录序列为正序时，时间复杂度提高至O（n）。
希尔排序（缩小增量排序diminishingincrementsort）：
先将整个待排记录序列分割成若干个子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。
插入排序Java代码：
publicclassInsertionSort{
//插入排序：
直接插入排序，希尔排序
publicvoidstraightInsertionSort（double[]sorted）{
intsortedLen=sorted.length;
for（intj=2;
j<
sortedLen;
j++）{
if（sorted[j]<
sorted[j-1]）{
sorted[0]=sorted[j];
//先保存一下后面的那个
sorted[j]=sorted[j-1];
//前面的那个后移。
intinsertPos=0;
for（intk=j-2;
k>
=0;
k--）{
if（sorted[k]>
sorted[0]）{
sorted[k+1]=sorted[k];
}else{
insertPos=k+1;
break;
}
}
sorted[insertPos]=sorted[0];
}
}
}
publicvoidshellInertionSort（double[]sorted,intinc）{
for（intj=inc+1;
j++）{
sorted[j-inc]）{
//先保存一下后面的那个
intinsertPos=j;
for（intk=j-inc;
k-=inc）{
sorted[k+inc]=sorted[k];
//数据结构课本上这个地方没有给出判读，出错：
if（k-inc<
=0）{
insertPos=k;
}
insertPos=k+inc;
}
}
}
publicvoidshellInsertionSort（double[]sorted）{
int[]incs={7,5,3,1};
intnum=incs.length;
intinc=0;
for（intj=0;
num;
inc=incs[j];
shellInertionSort（sorted,inc）;
publicstaticvoidmain（String[]args）{
Randomrandom=newRandom（6）;
intarraysize=21;
double[]sorted=newdouble[arraysize];
System.out.print（"
BeforeSort:
"
）;
for（intj=1;
arraysize;
sorted[j]=（int）（random.nextDouble（）*100）;
System.out.print（（int）sorted[j]+"
"
}
System.out.println（）;
InsertionSortsorter=newInsertionSort（）;
//sorter.straightInsertionSort（sorted）;
sorter.shellInsertionSort（sorted）;
AfterSort:
sorted.length;
}
5）交换排序：
包括冒泡排序，快速排序。
冒泡排序法：
该算法是专门针对已部分排序的数据进行排序的一种排序算法。
如果在你的数据清单中只有一两个数据是乱序的话，用这种算法就是最快的排序算法。
如果你的数据清单中的数据是随机排列的，那么这种方法就成了最慢的算法了。
因此在使用这种算法之前一定要慎重。
这种算法的核心思想是扫描数据清单，寻找出现乱序的两个相邻的项目。
当找到这两个项目后，交换项目的位置然后继续扫描。
重复上面的操作直到所有的项目都按顺序排好。
快速排序：
通过一趟排序，将待排序记录分割成独立的两个部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
具体做法是：
使用两个指针low,high,初值分别设置为序列的头，和序列的尾，设置pivotkey为第一个记录，首先从high开始向前搜索第一个小于pivotkey的记录和pivotkey所在位置进行交换，然后从low开始向后搜索第一个大于pivotkey的记录和此时pivotkey所在位置进行交换，重复知道low=high了为止。
交换排序Java代码：
publicclassExchangeSort{
publicvoidBubbleExchangeSort（double[]sorted）{
for（intj=sortedLen;
j>
0;
j--）{
intend=j;
for（intk=1;
k<
end-1;
k++）{
doubletempB=sorted[k];
sorted[k]=sorted[k]<
sorted[k+1]?
sorted[k]:
sorted[k+1];
if（Math.abs（sorted[k]-tempB）>
10e-6）{
sorted[k+1]=tempB;
}
publicvoidQuickExchangeSortBackTrack（double[]sorted,
intlow,inthigh）{
if（low<
high）{
intpivot=findPivot（sorted,low,high）;
QuickExchangeSortBackTrack（sorted,low,pivot-1）;
QuickExchangeSortBackTrack（sorted,pivot+1,high）;
publicintfindPivot（double[]sorted,intlow,inthigh）{
sorted[0]=sorted[low];
while（low<
while（low<
high&
&
sorted[high]>
=sorted[0]）--high;
sorted[low]=sorted[high];
sorted[low]<
=sorted[0]）++low;
sorted[high]=sorted[low];
sorted[low]=sorted[0];
returnlow;
ExchangeSortsorter=newExchangeSort（）;
//sorter.BubbleExchangeSort（sorted）;
sorter.QuickExchangeSortBackTrack（sorted,1,arraysize-1）;
6）选择排序：
分为直接选择排序，堆排序
直接选择排序：
第i次选取i到array.Length-1中间最小的值放在i位置。
堆排序：
首先，数组里面用层次遍历的顺序放一棵完全二叉树。
从最后一个非终端结点往前面调整，直到到达根结点，这个时候除根节点以外的所有非终端节点都已经满足堆得条件了，于是需要调整根节点使得整个树满足堆得条件，于是从根节点开始，沿着它的儿子们往下面走（最大堆沿着最大的儿子走，最小堆沿着最小的儿子走）。
主程序里面，首先从最后一个非终端节点开始调整到根也调整完，形成一个heap，然后将heap的根放到后面去（即：
每次的树大小会变化，但是root都是在1的位置，以方便计算儿子们的index，所以如果需要升序排列，则要逐步大顶堆。
因为根节点被一个个放在后面去了。
降序排列则要建立小顶堆）
代码中的问题：
有时候第2个和第3个顺序不对（原因还没搞明白到底代码哪里有错）
选择排序Java代码：
publicclassSelectionSort{
publicvoidstraitSelectionSort（double[]sorted）{
intjMin=getMinIndex（sorted,j）;
exchange（sorted,j,jMin）;
publicvoidexchange（double[]sorted,inti,intj）{
if（i<
sortedLen&
j<
i<
j&
i>
=0&
j>
doubletemp=sorted[i];
sorted[i]=sorted[j];
sorted[j]=temp;
publicintgetMinIndex（double[]sorted,inti）{
intminJ=1;
doublemin=Double.MAX_VALUE;
for（intj=i;
min）{
min=sorted[j];
minJ=j;
returnminJ;
publicvoidheapAdjust（double[]sorted,intstart,intend）{
if（start<
end）{
doubletemp=sorted[start];
//这个地方j<
end与课本不同，j<
=end会报错：
for（intj=2*start;
end;
j*=2）{
if（j+1<
end&
sorted[j]-sorted[j+1]>
++j;
if（temp<
=sorted[j]）{
break;
}
sorted[start]=sorted[j];
start=j;
sorted[start]=temp;
publicvoidheapSelectionSort（double[]sorted）{
intsortedLen=sorted.length;
for（inti=sortedLen/2;
i>
i--）{
heapAdjust（sorted,i,sortedLen）;
for（inti=sortedLen;
1;
--i）{
exchange（sorted,1,i）;
heapAdjust（sorted,1,i-1）;
publicstaticvoidmain（String[]args）{
intarraysize=9;
SelectionSortsorter=newSelectionSort（）;
//sorter.straitSelectionSort（sorted）;
sorter.heapSelectionSort（sorted）;
7）归并排序：
将两个或两个以上的有序表组合成一个新的有序表。
归并排序要使用一个辅助数组，大小跟原数组相同，递归做法。
每次将目标序列分解成两个序列，分别排序两个子序列之后，再将两个排序好的子序列merge到一起。
归并排序Java代码：
publicclassMergeSort{
privatedouble[]bridge;
//辅助数组
publicvoidsort（double[]obj）{
if（obj==null）{
thrownewNullPointerException（"
Theparamcannotbenull!
bridge=newdouble[obj.length];
//初始化中间数组
mergeSort（obj,0,obj.length-1）;
//归并排序
bridge=null;
privatevoidmergeSort（double[]obj,intleft,intright）{
if（left<
right）{
intcenter=（left+right）/2;
mergeSort（obj,left,center）;
mergeSort（obj,center+1,right）;
merge（obj,left,center,right）;
privatevoidmerge（double[]obj,intleft,
intcenter,intright）{
intmid=center+1;
intthird=left;
inttmp=left;
while（left<
=center&
mid<
=right）{
//从两个数组中取出小的放入中间数组
if（obj[left]-obj[mid]<
=10e-6）{
bridge[third++]=obj[left++];
}else{
bridge[third++]=obj[mid++];
//剩余部分依次置入中间数组
while（mid<
=right）{
bridge[third++]=obj[mid++];
=center）{
bridge[third++]=obj[left++];
//将中间数组的内容拷贝回原数组
copy（obj,tmp,right）;
privatevoidcopy（double[]obj,intleft,intright）
{
obj[left]=bridge[left];
left++;
Randomrandom=newRandom（6）;
intarraysize=10;
double[]sorted=newdouble[arraysize];
for（intj=0;
j<
arraysize;
j++）{
sorted[j]=（int）（random.nextDouble（）*100）;
System.out.print（（int）sorted[j]+"
MergeSortsorter=newMergeSort（）;
sorter.sort（sorted）;
sorted.length;
8）基数排序：
使用10个辅助队列，假设最大数的数字位数为x，则一共做x次，从个位数开始往前，以第i位数字的大小为依据，将数据放进辅助队列，搞定之后回收。
下次再以高一位开始的数字位为依据。
以Vector作辅助队列，基数排序的Java代码：
publicclassRadixSort{
privateintkeyNum=-1;
privateVector<
V
升级会员 