Java实现8种排序算法的示例代码
冒泡排序O(n2)
两个数比较大小,较大的数下沉,较小的数冒起来。
publicstaticvoidbubbleSort(int[]a){ //临时变量 inttemp; //i是循环次数,也是冒泡的结果位置下标,5个数组循环5次 for(inti=0;ii;j--){ //让小的数字排在前面 if(a[j] 选择排序O(n2)
在长度为N的无序数组中,第一次遍历n-1个数,找到最小的数值与第一个元素交换;
第二次遍历n-2个数,找到最小的数值与第二个元素交换;
。。。
第n-1次遍历,找到最小的数值与第n-1个元素交换,排序完成。publicstaticvoidselectSort(int[]a){ //临时变量 inttemp; //i是循环次数,也是选择交换的结果的位置下标,5个数组循环5次 for(inti=0;ia[j]){ min=j; } } temp=a[i]; a[i]=a[min]; a[min]=temp; } } 插入排序O(n2)
在要排序的一组数中,假定前n-1个数已经排好序,现在将第n个数插到前面的有序数列中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。
publicstaticvoidinsertSort(int[]a){ inttemp; //i是循环次数,也是插入的队列的长度,最后一位是a[i] //所以一开始a[0]是排好的一个队列,比较a.length-1次,最后一次循环是a[a.length-1]插入a[0]~a[a.length-2] for(inti=0;i0;j--){ //如果插入的数小,交换位置 if(a[j] 希尔排序O(n1.5)
在要排序的一组数中,根据某一增量分为若干子序列,并对子序列分别进行插入排序。
然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序。publicstaticvoidshellSort(int[]a){ inttemp; intd=a.length; for(;;){ d=d/2; //根据差值分组为子序列 for(intk=0;kk;j-=d){ //如果插入的数小,交换位置 if(a[j] 快速排序O(N*logN)
先从数列中取出一个数作为base值;
将比这个数小的数全部放在它的左边,大于或等于它的数全部放在它的右边;
对左右两个小数列重复第二步,直至各区间只有1个数。publicvoidquickSort(inta[],intl,intr){ //左边必须大于右边 if(l>=r){ return; } inti=l; intj=r; //选择第一个数为基准 intbase=a[l]; while(ibase){ j--; } //从左向右找第一个大于base的值,如果小于右移一位,直到找到大值或者i/j重合 while(i 归并排序O(N*logN)
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。
首先考虑下如何将2个有序数列合并。
这个非常简单,只要从比较2个数列的第一个数,谁小就先取谁,取了后就在对应数列中删除这个数。
然后再进行比较,如果有数列为空,那直接将另一个数列的数据依次取出即可。privatestaticvoidmergeSort(int[]a,intfirst,intlast,inttemp[]){ if(first堆排序O(N*logN)
利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。
publicstaticvoidheapSort(inta[]){ //堆顶最大值和数组最后(叶节点)交换长度-1次 for(inti=a.length-1;i>0;i--){ //构建大顶堆(最大堆) buildHeap(a,i); //堆顶最大值和数组最后(叶节点)交换 swap(a,0,i); } } //构建大顶堆(最大堆) publicstaticvoidbuildHeap(inta[],intlastIndex){ //排最后的非叶节点为长度/2-1,从第i检查到堆顶第0项,上浮大值 for(inti=(lastIndex+1)/2-1;i>=0;i--){ //必定存在的左叶节点,不一定存在的右叶节点 intleft=i*2+1; intright=i*2+2; //max为左右叶节点中的最大值 intmax=left; if(right<=lastIndex){ if(a[left]基数排序O(d(n+r))
【d代表关键字有d位,n代表n个记录,r代表r个空队列】
基数排序(radixsort),相对于常见的比较排序,基数排序是一种分配式排序,即通过将所有数字分配到应在的位置最后再覆盖到原数组完成排序的过程。publicstaticvoidradixSort(int[]a){ //位数 intdigit=1; //作为排序后数组的新下标 intnewIndex=0; //供基数排序使用的二维数组,第一维度固定10位0~9,第二维度根据下标依次存放每次基数排序的结果 int[][]container=newint[10][a.length]; //第一维度每个数组的内容计数,最少为10,防止数组全是个位数时越界,例如五位数组最大值为8,counter.length=5,counter[8]就越界 intcounterLength=10; if(a.length>10){ counterLength=a.length; } int[]counter=newint[counterLength]; //算出数组中最大的值,用来确定最大位 intmax=a[0]; intmaxDigit=0; for(inti=0;imax){ max=a[i]; } } while(max>0){ max/=10; maxDigit++; } //对每位进行排序 while(digit<=maxDigit){ //对每个数值该位取余,container[remainder],并计数该位置上数值的下标counter[remainder] for(intnum:a){ intremainder=(num/digit)%10; container[remainder][counter[remainder]]=num; counter[remainder]++; } //将上一步放入容器的数值依次覆盖到远数组中 for(inti=0;i<10;i++){ for(intj=0;j 以上就是Java实现8种排序算法的示例代码的详细内容,更多关于Java实现8种排序算法的资料请关注毛票票其它相关文章!
声明:本文内容来源于网络,版权归原作者所有,内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:czq8825#qq.com(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。