排序算法总结-Java篇.docx

排序算法总结-Java篇1. 插入排序基本操作：将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。时间复杂度：算法适用于少量数据的排序，时间复杂度为O(n2)。稳定性：稳定。实现：1. 首先新建一个空列表，用于保存已排序的有序数列（我们称之为有序列表）。2. 从原数列中取出一个数，将其插入有序列表中，使其仍旧保持有序状态。3. 重复2号步骤，直至原数列为空。插入排序的工作原理与打牌时整理手中的牌的做法类似，开始摸牌时，我们的左手是空的，接着一次从桌上摸起一张牌，并将它插入到左手的正确位置。为了找到这张牌的正确位置，要将它与手中已有的牌从右到左进行比较，无论什么时候手中的牌都是排序好的。Java程序代码：/插入排序package Sort;public class InsertSort public static void main(String args) int t,temp,i,j;t = args.length; /输入数据的元素个数int num = new intt; /创建数组 System.out.println(排序前：);for(i=0;iargs.length;i+) numi = Integer.parseInt(argsi);System.out.print(numi + );System.out.println();/执行插入排序for(i=1;i0;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();/输出排序结果System.out.println(n排序后：);for(i=0;iargs.length;i+) System.out.print(numi + );2. 冒泡排序冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。冒泡排序算法的运作如下:1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。3. 针对所有的元素重复以上的步骤，除了最后一个。4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。时间复杂度若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数和记录移动次数均达到最小值：，。所以，冒泡排序最好的时间复杂度为。若初始文件是反序的，需要进行趟排序。每趟排序要进行次关键字的比较(1in-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：冒泡排序的最坏时间复杂度为。综上，因此冒泡排序总的平均时间复杂度为。稳定性：稳定。Java程序代码：/冒泡排序package Sort;public class BubbleSort public static void main(String args) int t = args.length; /输入数据的元素个数 int score = new intt; /排序前 System.out.println(排序前：);for(int i=0;iargs.length;i+) scorei = Integer.parseInt(argsi);System.out.print(scorei + );System.out.println();/执行冒泡排序 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(第 + (i + 1) + 次排序结果：); for(int a = 0; a score.length; a+) System.out.print(scorea + ); System.out.println(); /排序后 System.out.print(最终排序结果：); for(int a = 0; a score.length; a+) System.out.print(scorea + ); 3. 选择排序选择排序是这样实现的：1. 设数组内存放了n个待排数字，数组下标从1开始，到n结束。2. 初始化i=13. 从数组的第i个元素开始到第n个元素，寻找最小的元素。4. 将上一步找到的最小元素和第i位元素交换。5. i+,直到i=n1算法结束，否则回到第3步选择排序的平均时间复杂度也是O(n2)的。稳定性：不稳定。Java程序代码：/选择排序package Sort;public class SelectSort public static void main(String args) int t,i;t = args.length; /输入数据的元素个数int num = new intt; /创建数组 System.out.println(排序前：);for(i=0;iargs.length;i+) numi = Integer.parseInt(argsi);System.out.print(numi + );System.out.println();/执行排序Sort(num);/输出排序结果System.out.println(n排序后：);for(i=0;iargs.length;i+) System.out.print(numi + );/选择排序方法public static void Sort(int sort)for(int i=0;isort.length;i+)for(int j=i+1;jsortj)int temp;temp=sorti;sorti=sortj;sortj=temp;System.out.print(第 + (i + 1) + 次排序结果：);for(int a = 0; a sort.length; a+) System.out.print(sorta + ); System.out.println();4. 快速排序快速排序是所有排序算法中最高效的一种。它采用了分治的思想：先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序，这样整个列表就有序了。这是一种先进的思想，也是它高效的原因。因为在排序算法中，算法的高效与否与列表中数字间的比较次数有直接的关系，而保证列表的前半部分都小于后半部分就使得前半部分的任何一个数从此以后都不再跟后半部分的数进行比较了，大大减少了数字间不必要的比较。但查找数据得另当别论了。时间复杂度：O(n log n)。稳定性：不稳定。Java程序代码：/快速排序package Sort;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 int partition(int sortArray,int low,int hight) int key = sortArraylow; while(lowhight) while(low=key) hight-; sortArraylow = sortArrayhight; while(lowhight & sortArraylow=key) low+; sortArrayhight = sortArraylow; sortArraylow = key; return low; public void sort(int low,int hight) if(lowhight) int result = partition(data,low,hight); sort(low,result-1); sort(result+1,hight); public void display() for(int i=0;i=0;i-)maxHeapify(data,data.length,i); /* *创建最大堆 * *paramdata *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)largest=left;if(rightheapSize & datalargest0;i-)int temp=data0;data0=datai;datai=temp;maxHeapify(data,i,0); /*父节点位置*paramcurrent*return*/private static int getParentIndex(int current)return(current-1)1; /*左子节点position注意括号，加法优先级更高*paramcurrent*return*/private static int getChildLeftIndex(int current)return(current1)+1; /*右子节点position*paramcurrent*return*/private static int getChildRightIndex(int current)return(current1)+2; private static void print(intdata)int pre=-2;for(int i=0;idata.length;i+)if(pre(int)getLog(i+1)pre=(int)getLog(i+1);System.out.println();System.out.print(datai+|); /*以2为底的对数*paramparam*return*/privatestatic double getLog(double param)return Math.log(param)/Math.log(2);6. 归并排序归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。例如有两个有序表：（7,10,13,15）和（4,8,19,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的单元。时间复杂度：O(n log n)。稳定性：稳定。Java程序代码：/* *归并排序 */package Sort;public class MergeSort/*二路归并*原理：将两个有序表合并和一个有序表*parama*params*第一个有序表的起始下标*paramm*第二个有序表的起始下标*paramt*第二个有序表的结束小标*/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+;elsetmpk=aj;j+;k+;while(im)tmpk=ai;i+;k+; while(j=t)tmpk=aj;j+;k+;System.arraycopy(tmp,0,a,s,tmp.length);/*parama*params*paramlen*每次归并的有序集合的长度*/public static void mergeSort(inta,int s,int len)int size=a.length;int mid=size/(len1);int c=size&(len1)-1);/-归并到只剩一个有序集合的时候结束算法-/if(mid=0)return;/-进行一趟归并排序-/for(int i=0;imid;+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 static void main(String args)