排序算法总结Java篇Word格式.docx

1、 /执行插入排序 for（i=1;t;i+） for（j=i;j0;j-） if（numjnumj-1） temp = numj; numj = numj-1; numj-1 = temp; else break; System.out.print（第 + （i + 1） + 次排序结果： for（int a = 0; a t; a+） System.out.print（numa + System.out.println（ /输出排序结果n排序后：2. 冒泡排序冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过

2、来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。冒泡排序算法的运作如下:1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。3. 针对所有的元素重复以上的步骤，除了最后一个。4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。时间复杂度若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数和记录移动次数均达到最小值：，。所以，冒泡排序最好的时间复杂度

3、为若初始文件是反序的，需要进行趟排序。每趟排序要进行次关键字的比较（1in-1），且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：冒泡排序的最坏时间复杂度为综上，因此冒泡排序总的平均时间复杂度为 稳定性： Java程序代码：/冒泡排序public class BubbleSort public static void main（String args） int t = args.length; int score = new intt; /排序前 for（int i=0; scorei = Integer.parseInt（argsi）; System

4、.out.print（scorei + /执行冒泡排序 for （int i = 0; i score.length -1; i+） /最多做n-1趟排序 for（int j = 0 ;j score.length - i - 1; j+） /对当前无序区间score0.length-i-1进行排序（j的范围很关键，这个范围是在逐步缩小的） if（scorej scorej + 1） /把小的值交换到后面 int temp = scorej; scorej = scorej + 1; scorej + 1 = temp; System.out.print（ for（int a = 0; sco

5、re.length; System.out.print（scorea + /排序后最终排序结果：3. 选择排序选择排序是这样实现的：1. 设数组内存放了n个待排数字，数组下标从1开始，到n结束。2. 初始化i=13. 从数组的第i个元素开始到第n个元素，寻找最小的元素。4. 将上一步找到的最小元素和第i位元素交换。5. i+,直到i=n1算法结束，否则回到第3步选择排序的平均时间复杂度也是O（n2）的。不稳定。/选择排序public class SelectSort int t,i; /执行排序 Sort（num）; /选择排序方法 public static void Sort（int so

6、rt）sort.length; for（int j=i+1;jsortj） int temp; temp=sorti; sorti=sortj; sortj=temp; sort.length; System.out.print（sorta + 4. 快速排序快速排序是所有排序算法中最高效的一种。它采用了分治的思想：先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序，这样整个列表就有序了。这是一种先进的思想，也是它高效的原因。因为在排序算法中，算法的高效与否与列表中数字间的比较次数有直接的关系，而保证列表的前半部分都小于后半部分就使得前半部分的任何一个数从此以后都不再跟后半部

7、分的数进行比较了，大大减少了数字间不必要的比较。但查找数据得另当别论了。O（n log n）。/快速排序public class QSort /* * param args */ public static void main（String args） / TODO 自动生成方法存根 quicksort qs = new quicksort（）; int data = 3,1,4,6,5,2; qs.data = data; qs.sort（0, qs.data.length-1）; qs.display（）;class quicksort public int data; private i

8、nt partition（int sortArray,int low,int hight） int key = sortArraylow; while（low=key） hight-; sortArraylow = sortArrayhight; sortArraylow low+; sortArrayhight = sortArraylow; sortArraylow = key; return low; public void sort（int low,int hight） if（low=0;i-） maxHeapify（data,data.length,i）; *创建最大堆 * *par

9、amdata *paramheapSize需要创建最大堆的大小，一般在sort的时候用到，因为最多值放在末尾，末尾就不再归入最大堆了 *paramindex当前需要创建最大堆的位置 private static void maxHeapify（intdata,int heapSize,int index） /当前点与左右子节点比较 int left=getChildLeftIndex（index）; int right=getChildRightIndex（index）; int largest=index; if（leftheapSize & dataindexdataleft） large

10、st=left; if（right datalargest1; *左子节点position注意括号，加法优先级更高 private static int getChildLeftIndex（int current） return（current1）+1; *右子节点position private static int getChildRightIndex（int current）1）+2; private static void print（intdata） int pre=-2; if（pre（int）getLog（i+1） pre=（int）getLog（i+1）; System.out

11、.println（）; System.out.print（datai+| *以2为底的对数 *paramparam private static double getLog（double param） return Math.log（param）/Math.log（2）;6. 归并排序归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。例如有两个有序表：（7,10,13,15）和（4,8,1

12、9,20），归并后得到的有序表为：（4,7,8,10,13,15,19,20）。归并过程为：比较ai和aj的大小，若aiaj，则将第一个有序表中的元素ai复制到rk中，并令i和k分别加上1；否则将第二个有序表中的元素aj复制到rk中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。/* *归并排序 */public class MergeSort * *二路归并 *原理：将两个有序表合并和一个有序表/pre *parama *params *第一个有序表的起始下标 *paramm *第二个有序表的起始下标 *para

13、mt *第二个有序表的结束小标 * */ private static void merge（inta,int s,int m,int t） int tmp=new intt-s+1; int i=s,j=m,k=0; while（im & j=t） if（ai=aj） tmpk=ai; k+; i+; else tmpk=aj; j+;m） tmpk=ai; i+; k+; while（j tmpk=aj; j+; System.arraycopy（tmp,0,a,s,tmp.length）; *paramlen *每次归并的有序集合的长度 public static void mergeS

14、ort（inta,int s,int len） int size=a.length; int mid=size/（len1）; int c=size&（len1）-1）; /-归并到只剩一个有序集合的时候结束算法-/ if（mid=0） return; /-进行一趟归并排序-/mid;+i） s=i*2*len; merge（a,s,s+len,（len1）+s-1）; /-将剩下的数和倒数一个有序集合归并-/ if（c!=0） merge（a,size-c-2*len,size-c,size-1）; /-递归执行下一趟归并排序-/ mergeSort（a,0,2*len）; public s

15、tatic void main（String args） inta=new int4,3,6,1,2,5; mergeSort（a,0,1）;a.length; System.out.print（ai + 7. 希尔排序希尔排序（Shell Sort）是插入排序的一种。是针对直接插入排序算法的改进。思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2d1重复上述的分组和排序，直至所取的增量=1（d2 0; increment /= 2） for （int i = increment; data.length; i+） temp = datai; fo