java算法方面.docx
《java算法方面.docx》由会员分享，可在线阅读，更多相关《java算法方面.docx（13页珍藏版）》请在冰点文库上搜索。
java算法方面
Java
快速排序
基本思想
快速排序（Quicksort）是对冒泡排序的一种改进。
由C.A.R.Hoare在1962年提出。
它的基本思想是：
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
算法过程
设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。
一趟快速排序的算法是：
1）设置两个变量I、J，排序开始的时候：
I=1，J=N；
2）以第一个数组元素作为关键数据，赋值给X，即X=A[1]；
3）从J开始向前搜索，即由后开始向前搜索（J=J-1），找到第一个小于X的值，让该值与X交换；
4）从I开始向后搜索，即由前开始向后搜索（I=I+1），找到第一个大于X的值，让该值与X交换；
5）重复第3、4步，直到I=J；
例如：
待排序的数组A的值分别是：
（初始关键数据：
X=49）
A[0]、A[1]、A[2]、A[3]、A[4]、A[5]、A[6]：
49386597761327
进行第一次交换后：
27386597761349
（按照算法的第三步从后面开始找）
进行第二次交换后：
27384997761365
（按照算法的第四步从前面开始找>X的值，65>49,两者交换，此时：
I=3）
进行第三次交换后：
27381397764965
（按照算法的第五步将又一次执行算法的第三步从后开始找
进行第四次交换后：
27381349769765
（按照算法的第四步从前面开始找大于X的值，97>49,两者交换，此时：
J=4）
此时再执行第三步的时候就发现I=J，从而结束一躺快速排序，那么经过一趟快速排序之后的结果是：
27381349769765，即所以大于49的数全部在49的后面，所以小于49的数全部在49的前面。
快速排序就是递归调用此过程——在以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列，根据这种思想对于上述数组A的快速排序的全过程如图6所示：
初始状态{49386597761327}
进行一次快速排序之后划分为{273813}49{769765}
分别对前后两部分进行快速排序{273813}经第三步和第四步交换后变成{132738}完成排序。
{769765}经第三步和第四步交换后变成{657697}完成排序。
1.
public static void QuickSort（int left, int right, int index）
2. {
3. int i, j, k;
4. int Pivot;
5. int Temp;
6.
7. i = left;
8. j = right;
9.
10. Pivot = a[left];
11. if （i < j）
12. {
13. do
14. {
15. while （a[i] < Pivot && i < right）
16. {
17. i++;
18. }
19. while （a[j] > Pivot && j > left）
20. {
21. j--;
22. }
23. if （i < j） //exchange a[i] and a[j]
24. {
25. Temp = a[i];
26. a[i] = a[j];
27. a[j] = Temp;
28.
29. }
30. } while （i < j）;
31. if （i > j）
32. {
33. Temp = a[left]; // exchange a[Left] and a[j]
34. a[left] = a[j];
35. a[j] = Temp;
36. }
37. QuickSort（left, j - 1, index）; // left
38. QuickSort（j + 1, right, index）; // right
39.
40. }
41. }
冒泡排序的基本概念是：
依次比较相邻的两个数，将小数放在前面，大数放在后面。
即首先比较第1个和第2个数，将小数放前，大数放后。
然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。
重复以上过程，仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再大于第2个数），将小数放前，大数放后，一直比较到最小数前的一对相邻数，将小数放前，大数放后，第二趟结束，在倒数第二个数中得到一个新的最小数。
如此下去，直至最终完成排序。
由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。
用二重循环实现，外循环变量设为i，内循环变量设为j。
外循环重复9次，内循环依次重复9，8，...，1次。
每次进行比较的两个元素都是与内循环j有关的，它们可以分别用a[j]和a[j+1]标识，i的值依次为1,2,...,9，对于每一个i,j的值依次为1,2,...10-i。
1.public class BubbleSort {
2. public static void sort（int[] data） {
3. int temp;
4. for （int i = 0; i < data.length; i++） {
5. for （int j = data.length - 1; j > i; j--） {
6. if （data[i] > data[j]） {
7. temp = data[i];
8. data[i] = data[j];
9. data[j] = temp;
10. }
11. }
12. }
13. }
14.
15. public static void main（String[] args） {
16. int[] a = { 4, 2, 3, 1, 5 };
17. sort（a）;
18. for （int i = 0; i < a.length; i++）
19. System.out.print（a[i] + " "）;
20. }
21.}
排序
所谓排序，就是要整理文件中的记录，使之按关键字递增（或递减）次序排列起来。
当待排序记录的关键字都不相同时，排序结果是惟一的，否则排序结果不惟一。
在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生改变，则称这种排序方法是不稳定的。
要注意的是，排序算法的稳定性是针对所有输入实例而言的。
即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。
一.插入排序
插入排序的基本思想是每步将一个待排序的记录按其排序码值的大小，插到前面已经排好的文件中的适当位置，直到全部插入完为止。
插入排序方法主要有直接插入排序和希尔排序。
①.直接插入排序（稳定）
接插入排序的过程为：
在插入第i个记录时，R1,R2,..Ri-1已经排好序，将第i个记录的排序码Ki依次和R1,R2,..,Ri-1的排序码逐个进行比较，找到适当的位置。
使用直接插入排序，对于具有n个记录的文件，要进行n-1趟排序。
代码如下:
void Dir_Insert（int A[],int N） //直接插入排序
{
int j,t;
for（int i=1;i {
t=A[i];
j=i-1;
while（A[j]>t）
{
A[j+1]=A[j];
j--;
}
A[j+1]=t;
}
}
②.希尔排序（不稳定）：
希尔（Shell）排序的基本思想是：
先取一个小于n的整数d1作为第一个增量把文件的全部记录分成d1个组。
所有距离为d1的倍数的记录放在同一个组中。
先在各组内进行直接插入排序；然后，取得第二个增量d2该方法实质上是一种分组插入方法。
一般取d1=n/2，di+1=di/2。
如果结果为偶数，则加1，保证di为奇数。
希尔排序是不稳定的，希尔排序的执行时间依赖于增量序列，其平均时间复杂度为O（n^1.3）.
代码如下:
void Shell（int A[],int n） //Shell排序
{
int i,j,k,t;
（n/2）%2 == 0 ?
k = n/2+1 :
k = n/2; //保证增量为奇数
while（k > 0）
{
for（j=k;j {
t = A[j];
i = j - k;
while（i>=0 && A[i]>t）
{
A[i+k]=A[i];
i=i-k;
}
A[i+k]=t;
}
if（k == 1） break;
（k/2）%2 ==0 ?
k=k/2+1 :
k=k/2;
}
}
二.选择排序
选择排序的基本思想是每步从待排序的记录中选出排序码最小的记录，顺序存放在已排序的记录序列的后面，直到全部排完。
选择排序中主要使用直接选择排序和堆排序。
①.直接选择排序（不稳定）
直接选择排序的过程是：
首先在所有记录中选出序码最小的记录，把它与第1个记录交换，然后在其余的记录内选出排序码最小的记录，与第2个记录交换......依次类推，直到所有记录排完为止。
无论文件初始状态如何，在第i趟排序中选出最小关键字的记录，需要做n-i次比较，因此，总的比较次数为n（n-1）/2=O（n^2）。
当初始文件为正序时，移动次数为0；文件初态为反序时，每趟排序均要执行交换操作，总的移动次数取最大值3（n-1）。
直接选择排序的平均时间复杂度为O（n^2）。
直接选择排序是不稳定的。
代码如下:
void Dir_Choose（int A[],int n） //直接选择排序
{
int k,t;
for（int i=0;i {
k=i;
for（int j=i+1;j {
if（A[j] }
if（k!
=i）
{
t=A[i];
A[i]=A[k];
A[k]=t;
}
}
}
②.堆排序（不稳定）
堆排序是一种树形选择排序，是对直接选择排序的有效改进。
n个关键字序列
K1,K2,...,Kn称为堆，当且仅当该序列满足（Ki<=K2i且Ki<=K2i+1）或（Ki>=K2i且Ki>=K2i+1）,（1<=i<=n/2）。
根结点（堆顶）的关键字是堆里所有结点关键字中最小者，称为小根堆；根结点的关键字是堆里所有结点关键字中最大者，称为大根堆。
若将此序列所存储的向量R[1..n]看作是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：
树中任一非叶结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。
堆排序的关键步骤有两个：
一是如何建立初始堆；二是当堆的根结点与堆的最后一个结点交换后，如何对少了一个结点后的结点序列做调整，使之重新成为堆。
堆排序的最坏时间复杂度为O（nlog2n）,堆排序的平均性能较接近于最坏性能。
由于建初始堆所需的比较 次数较多，所以堆排序不适宜于记录较少的文件。
堆排序是就地排序，辅助空间为O
（1），它是不稳定的排序方法。
代码略..
三.交换排序
交换排序的基本思想是：
两两比较待排序记录的排序码，并交换不满足顺序要求的那写偶对，直到满足条件为止。
交换排序的主要方法有冒泡排序和快速排序.
①.冒泡排序（稳定的）
冒泡排序将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为ki的气泡。
根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R；凡扫描到违反本原则的轻气泡，就使其向上"漂浮"。
如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。
冒泡排序的具体过程如下：
第一步，先比较k1和k2，若k1>k2，则交换k1和k2所在的记录，否则不交换。
继续对k2和k3重复上述过程，直到处理完kn-1和kn。
这时最大的排序码记录转到了最后位置，称第1次起泡，共执行n-1次比较。
与第一步类似，从k1和k2开始比较，到kn-2和kn-1为止，共执行n-2次比较。
依次类推，共做n-1次起泡，完成整个排序过程。
若文件的初始状态是正序的，一趟扫描即可完成排序。
所需关键字比较次数为n-1次，记录移动次数为0。
因此，冒泡排序最好的时间复杂度为O（n）。
若初始文件是反序的，需要进行n-1趟排序。
每趟排序要进行n-i次关键字的比较（1<=i<=n-1）,且每次比较都必须移动记录三次来达到交换记录位置。
在这种情况下，比较次数达到最大值n（n-1）/2=O（n^2）,移动次数也达到最大值3n（n-1）/2=O（n^2）。
因此，冒泡排序的最坏时间复杂度为O（n^2）。
虽然冒泡排序不一定要进行n-1趟，但由于它的记录移动次数较多，故平均性能比直接插入排序要差得多。
冒泡排序是就地排序，且它是稳定的。
代码如下:
void QP（int A[],int n） //优化的冒泡排序
{
int count=0,t,flag;
for（int i=0;i {
flag=0;
for（int j=0;j {
if（A[j+1] {
t=A[j];
A[j]=A[j+1];
A[j+1]=t;
flag=1;
count+=3;
}
}
if（flag==0） break;
}
}
②.快速排序：
（不稳定的）
快速排序采用了一种分治的策略，通常称其为分治法，其基本思想是：
将原问题分解为若干个规模更小但结构与原问题相似的子问题。
递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
快速排序的具体过程如下：
第一步，在待排序的n个记录中任取一个记录，以该记录的排序码为准，将所有记录分成两组，第1组各记录的排序码都小于等于该排序码，第2组各记录的排序码都大于该排序码，并把该记录排在这两组中间。
第二步，采用同样的方法，对左边的组和右边的组进行排序，直到所有记录都排到相应的位置为止。
代码如下:
void Quick_Sort（int A[],int low,int high） //low和high是数组的下标
{
if（low {
int temp,t=A[low];
int l=low,h=high;
while（l {
while（A[l] while（A[h]>=t） h--;
if（h>l）
{
temp=A[l];
A[l]=A[h];
A[h]=temp;
}
}
Quick_Sort（A,low,l-1）;
Quick_Sort（A,l+1,high）;
}
}
四.归并排序
归并排序是将两个或两个以上的有序子表合并成一个新的有序表。
初始时，把含有n个结点的待排序序列看作由n个长度都为1的有序子表组成，将它们依次两两归并得到长度为2的若干有序子表，再对它们两两合并。
直到得到长度为n的有序表，排序结束。
归并排序是一种稳定的排序，可用顺序存储结构，也易于在链表上实现，对长度为n的文件，需进行log2n趟二路归并，每趟归并的时间为O（n）,故其时间复杂度无论是在最好情况下还是在最坏情况下均是O（nlog2n）。
归并排序需要一个辅助向量来暂存两个有序子文件归并的结果，故其辅助空间复杂度为O（n）,显然它不是就地排序。
代码略...
五.基数排序
设单关键字的每个分量的取值范围均是C0<=Kj<=Crd-1（0<=j<=rd）,可能的取值个数rd称为基数．基数的选择和关键字的分解因关键字的类型而异．
（1）.若关键字是十进制整数，则按个、十等位进行分解，基数rd=10,C0=0,C9=9,d为最长整数的位数．
（2）.若关键字是小写的英文字符串，则rd=26,C0='a',C25='z',d为最长字符串的长度．
基数排序的基本思想是：
从低位到高位依次对待排序的关键码进行分配和收集，经过d趟分配和收集，就可以得到一个有序序列．
按平均时间将排序分为四类：
（1）平方阶（O（n2））排序
一般称为简单排序，例如直接插入、直接选择和冒泡排序；
（2）线性对数阶（O（nlgn））排序
如快速、堆和归并排序；
（3）O（n1+￡）阶排序
￡是介于0和1之间的常数，即0<￡<1，如希尔排序；
（4）线性阶（O（n））排序
如基数排序。
各种排序方法比较
简单排序中直接插入最好，快速排序最快，当文件为正序时，直接插入和冒泡均最佳。
影响排序效果的因素
因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法应综合考虑下列因素：
①待排序的记录数目n；
②记录的大小（规模）；
③关键字的结构及其初始状态；
④对稳定性的要求；
⑤语言工具的条件；
⑥存储结构；
⑦时间和辅助空间复杂度等。
不同条件下，排序方法的选择
（1）若n较小（如n≤50），可采用直接插入或直接选择排序。
当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。
（2）若文件初始状态基本有序（指正序），则应选用直接插人、冒泡或随机的快速排序为宜；
（3）若n较大，则应采用时间复杂度为O（nlgn）的排序方法：
快速排序、堆排序或
归并排序。
快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。
这两种排序都是不稳定的。
若要求排序稳定，则可选用归并排序。
但从单个记录起进行两两归并的 排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。
先利用直接插入排序求得较长的有序子文件，然后再两两归并之。
因为直接插入排序是稳定的，所以改进后的归并排序仍是稳定的。
升级会员 