欢迎来到天天文库
浏览记录
ID:59254671
大小:19.67 KB
页数:7页
时间:2020-09-08
《java实现各种排序算法.docx》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、常见的排序算法之Java代码解释一、简要介绍一般排序均值的是将一个已经无序的序列数据重新排列成有序的 常见的排序分为: 1插入类排序 主要就是对于一个已经有序的序列中,插入一个新的记录。它包括:直接插入排序,折半插入排序和希尔排序 2交换类排序 这类排序的核心就是每次比较都要“交换”,每一趟排序都会发生一系列的“交换”排序,但是每一趟排序都会让一个记录排序到它的最终位置上。它包括:起泡排序,快速排序 3选择类排序 顾名思义,这类排序主要就是“选择”,每一趟排序都从一系列数据中选择一个最大或最小的记录,将它放置到第一个或最好一个为位置交换,只有在选择后才交换,比起交换类排序
2、,减少了交换记录的时间。属于它的排序:简单选择排序,堆排序 4归并类排序 将两个或两个以上的有序序列合并成一个新的序列 5基数排序 主要基于多个关键字排序的。 下面针对上面所述的算法,讲解一些常用的java代码写的算法二、插入类排序--------直接插入排序直接插入排序,一般对于已经有序的队列排序效果好。基本思想:每趟将一个待排序的关键字按照大小插入到已经排序好的位置上。算法思路,从后往前先找到要插入的位置,然后所有元素向后移动,将要插入数据插入该文职即可即可。时间复杂度为O(n2),空间复杂度为O(1)publicstaticvoidinsertSort(int[]a
3、){//首先假定第一个值是排序的,从后面值开始从后向前与已排序的序列比较,若遇到比记录值大的则向后移,最后将记录值插入到比记录值小或等于的值后面;//需要记录每一次需要比较的值的值及其最后需要插入的位置;inttmp,j;for(inti=1;i0&&a[j-1]>tmp){a[j]=a[j-1];j--;}a[j]=tmp;}}三 插入类排序------折半插入排序 条件:在一个已经有序的队列中,插入一个新的元素 折半插入排序记录的比较次数与初始序列无关 思想:折半插入就是首先将队列中取最小位置lo
4、w和最大位置high,然后算出中间位置mid 将中间位置mid与待插入的数据data进行比较, 如果mid大于data,则就表示插入的数据在mid的左边,high=mid-1; 如果mid小于data,则就表示插入的数据在mid的右边,low=mid+1 时间复杂度O(n2),空间复杂度O(1)package sort.algorithm;//折半插入排序publicstaticvoid HalfInsertSort(String[]args) {int data[]={2,6,10,3,9,80,1,16,27,20};//存放临时要插入的元素数据int temp
5、;int low,mid,high;for(int i=1;i6、入数据的位置之间数据向后移动 for(int j=i;j>=low+1;j--) data[j]=data[j-1];//low已经代表了要插入的位置了 data[low]=temp; }for(int k=0;k7、将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的下标相差d.对每组中全部元素进行直接插入排序,然后再用一个较小的增量(d/2)对它进行分组,在每组中再进行直接插入排序。当增量减到1时,进行直接插入排序后,排序完成。publicstaticvoidshellSort(int[]a){//根据步长序列[t1,t2,...tk]依次减小的序列其中tk=1//将a分成进行k次排序,分别分成t1,t2、、、tk组;对每组进行直接插入排序//需要记录每次的步长、每组需要插入的值tmpinth,tmp,j;
6、入数据的位置之间数据向后移动 for(int j=i;j>=low+1;j--) data[j]=data[j-1];//low已经代表了要插入的位置了 data[low]=temp; }for(int k=0;k7、将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的下标相差d.对每组中全部元素进行直接插入排序,然后再用一个较小的增量(d/2)对它进行分组,在每组中再进行直接插入排序。当增量减到1时,进行直接插入排序后,排序完成。publicstaticvoidshellSort(int[]a){//根据步长序列[t1,t2,...tk]依次减小的序列其中tk=1//将a分成进行k次排序,分别分成t1,t2、、、tk组;对每组进行直接插入排序//需要记录每次的步长、每组需要插入的值tmpinth,tmp,j;
7、将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的下标相差d.对每组中全部元素进行直接插入排序,然后再用一个较小的增量(d/2)对它进行分组,在每组中再进行直接插入排序。当增量减到1时,进行直接插入排序后,排序完成。publicstaticvoidshellSort(int[]a){//根据步长序列[t1,t2,...tk]依次减小的序列其中tk=1//将a分成进行k次排序,分别分成t1,t2、、、tk组;对每组进行直接插入排序//需要记录每次的步长、每组需要插入的值tmpinth,tmp,j;
此文档下载收益归作者所有