java实现各种排序算法

常见的排序算法之Java代码解释一、简要介绍一般排序均值的是将一个已经无序的序列数据重新排列成有序的常见的排序分为：1插入类排序主要就是对于一个已经有序的序列中，插入一个新的记录。它包括：直接插入排序，折半插入排序和希尔排序2交换类排序这类排序的核心就是每次比较都要“交换”，每一趟排序都会发生一系列的“交换”排序，但是每一趟排序都会让一个记录排序到它的最终位置上。它包括：起泡排序，快速排序3选择类排序顾名思义，这类排序主要就是“选择”，每一趟排序都从一系列数据中选择一个最大或最小的记录，将它放置到第一个或最好一个为位置交换，只有在选择后才交换，比起交换类排序，减少了交换记录的时间。属于它的排序：简单选择排序，堆排序4归并类排序将两个或两个以上的有序序列合并成一个新的序列5基数排序主要基于多个关键字排序的。下面针对上面所述的算法，讲解一些常用的java代码写的算法二、插入类排序--------直接插入排序直接插入排序,一般对于已经有序的队列排序效果好。基本思想：每趟将一个待排序的关键字按照大小插入到已经排序好的位置上。算法思路，从后往前先找到要插入的位置，然后所有元素向后移动，将要插入数据插入该文职即可即可。时间复杂度为O(n2),空间复杂度为O(1)publicstaticvoidinsertSort(int[]a){//首先假定第一个值是排序的，从后面值开始从后向前与已排序的序列比较，若遇到比记录值大的则向后移，最后将记录值插入到比记录值小或等于的值后面；//需要记录每一次需要比较的值的值及其最后需要插入的位置；inttmp,j;for(inti=1;ia.length;i++){tmp=a[i];j=i;while(j0&&a[j-1]tmp){a[j]=a[j-1];j--;}a[j]=tmp;}}三插入类排序------折半插入排序条件：在一个已经有序的队列中，插入一个新的元素折半插入排序记录的比较次数与初始序列无关思想：折半插入就是首先将队列中取最小位置low和最大位置high，然后算出中间位置mid将中间位置mid与待插入的数据data进行比较，如果mid大于data，则就表示插入的数据在mid的左边，high=mid-1;如果mid小于data，则就表示插入的数据在mid的右边,low=mid+1时间复杂度O(n2),空间复杂度O(1)packagesort.algorithm;//折半插入排序publicstaticvoidHalfInsertSort(String[]args){intdata[]={2,6,10,3,9,80,1,16,27,20};//存放临时要插入的元素数据inttemp;intlow,mid,high;for(inti=1;idata.length;i++){temp=data[i];//在待插入排序的序号之前进行折半插入low=0;high=i-1;while(low=high){mid=(low+high)/2;if(tempdata[mid])high=mid-1;else//low=high的时候也就是找到了要插入的位置，//此时进入循环中，将low加1，则就是要插入的位置了low=mid+1;}//找到了要插入的位置，从该位置一直到插入数据的位置之间数据向后移动for(intj=i;j=low+1;j--)data[j]=data[j-1];//low已经代表了要插入的位置了data[low]=temp;}for(intk=0;kdata.length;k++){System.out.print(data[k]+);}}四、插入类排序-----希尔排序希尔排序，也叫缩小增量排序将待续按照某一种规则分为几个子序列，不断缩小规则，最后用一个直接插入排序合成空间复杂度为O(1)，时间复杂度为O(nlog2n)算法先将要排序的一组数按某个增量d（n/2,n为要排序数的个数）分成若干组，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。当增量减到1时，进行直接插入排序后，排序完成。publicstaticvoidshellSort(int[]a){//根据步长序列[t1,t2,...tk]依次减小的序列其中tk=1//将a分成进行k次排序，分别分成t1，t2、、、tk组；对每组进行直接插入排序//需要记录每次的步长、每组需要插入的值tmpinth,tmp,j;//j要定义为全局变量，否则会有错for(h=a.length/2;h0;h=h/2){for(inti=h;ia.length;i++){tmp=a[i];for(j=i-h;j=0;j=j-h){if(tmpa[j])a[j+h]=a[j];//若tmp比a[j]小，则a[j]向后移动else//不能少了elsebreak;}a[j+h]=tmp;}}}五交换类排序-----冒泡排序交换类排序核心就是每次比较都要进行交换冒泡排序：是一种交换排序每次比较若大小不同则就会发生交换，每一趟排序都能将一个元素放到它最终的位置！每一趟就进行比较。时间复杂度O(n2)，空间复杂度O(1)publicstaticvoidbubbleSort(int[]a){//从头开始两两比较，若前边值大则交换否则，继续比较；//只需记录需要交换的值inttmp;for(inti=0;ia.length-1;i++){//ia.length-1;for(intj=i+1;ja.length;j++){if(a[i]a[j]){tmp=a[i];a[i]=a[j];a[j]=tmp;}}}}六、交换类排序-------快速排序快速排序算法，初始的时候选择一个轴线，一般来说选择第一个元素，每一趟排序交换后，最后出现的就是该轴左边比它小，右边比他大！交替扫描，先从右边开始扫描，如果遇到比它小的就停止，将该元素与轴线交换，马上换成从左开始扫描，如果遇到比它大的就停止，将该元素与轴线数据交换，重复这样的！一般就是递归做的时间复杂度O(nlog2n),平均时间是最好的空间复杂度O(long2n)，快速排序需要递归用到了栈publicstaticvoidquickSort(int[]a,intlow,inthigh){//选择并记录基准值，low=0，high=a.length-1,而不是a.lengthif(low=high)return;intindex=a[low];inti=low,j=high;while(ij){//不能少了这个判断while(ij&&a[j]=index)j--;if(ij)a[i++]=a[j];//将a[j]赋值给a[i]后，需要将i+1；while(ij&&a[i]index)i++;if(ij)a[j--]=a[i];}a[i]=index;quickSort(a,low,i-1);quickSort(a,i+1,high);}七、选择类排序-------简单选择排序简单选择排序，每一趟从数据中选择一个最小值放到最前面，但是不需要交换位置，只记录该交换的位置，只有找到后才做一次交换！//简单选择排序：是一种选择排序publicstaticvoidselectSort(int[]a){//第一次遍历选出最小值与第一个值交换位置，依次//需要记录每一次的最小值与最小值的位置inttmp;intflag;for(inti=0;ia.length;i++){tmp=a[i];//tmp用来存储最小值首先赋值为i位置处的值flag=i;//flag首先赋值为i值for(intj=i+1;ja.length;j++){if(a[j]tmp){tmp=a[j];flag=j;}}if(flag!=i){a[flag]=a[i];a[i]=tmp;}}}八、选择类排序---------堆排序堆排序就是建立大顶堆或者小顶堆，若建立大顶堆，每次对于建好的大顶堆将根元素与最后一个元素交换，无序的数目减少，有序的数目增加。对于求N个数据中的前n个最小的数据，首先就是建立一个n个的大顶堆，然后让其余的元素来进行与这堆顶元素比较，如果小于则与堆顶互换元素。这里采用数组存储节点，并且下标统一从0，length-1，所以对于这样处理的左孩子节点下标为2*i+1，右孩子的节点下标为2*i+212345678910111213packagesort.algorithm;publicclassHeapSort{publicstaticintheap_size;//左孩子编号publicstaticintleftChild(inti){return2*i+1;}//右孩子编号publicstaticintrightChild(inti){return2*i+2;}/***保持最大堆的性质1415161718192021222324252627282930313233343536373839404142434445464748495051525354555657*堆中的数组元素*对以该元素为根元素的堆进行调整，假设前提：左右子树都是最大堆*由于左右孩子都是最大堆，首先比较根元素与左右孩子，找出最大值，假如大于根元素，则调整两个元素的值；*由于左孩子（右孩子）的值与根元素交换，有可能打破左子树（右子树）的最大堆性质，因此继续调用，直至叶子元素。*/publicstaticvoidmax_heapify(int[]a,inti){intleft=leftChild(i);intright=rightChild(i);intlargest=0;if(leftheap_size&&a[i]a[left]){largest=left;}else{largest=i;}if(rightheap_size&&a[right]a[largest]){largest=right;}if(largest==i){return;}else{inttemp=a[i];a[i]=a[largest];a[largest]=temp;max_heapify(a,largest);}}/***建立最大堆。在数据中，下标a.length/2+1一直到最后的元素a.length-1都是叶子元素*因此从其前一个元素开始，一直到*第一个元素，重复调用max_heapify函数，使其保持最大堆的性质*/publicstaticvoidbuild_max_heap(int[]a){//从0~a.length/2中建立最大堆for(inti=a.length/2;i=0;i--){max_heapify(a,i);}}/**58596061626364656667686970717273747576777879808182*堆排序：首先建立最大堆，然后将堆顶元素（最大值）与最后一个值交换，同时使得堆的长度减小1*调用保持最大堆性质的算法调整，使得堆顶元素成为最大值，此时最后一个元素已被排除在外、*/publicstaticvoidheapSort(int[]a){//构建最大堆build_max_heap(a);for(inti=a.length-1;i=0;i--){//将第一个元素和最后一个元素进行互换inttemp=a[0];a[0]=a[i];a[i]=temp;heap_size--;//调整堆为最大堆max_heapify(a,0);}}publicstaticvoidmain(String[]args){inta[]={5,4,1,3,2,16,9,10,14,8,7};heap_size=a.length;//最大数heapSort(a);//输出结果for(inti=0;ia.length;i++){System.out.print(a[i]+);}}}九各种排序总结：时间复杂度：巧记“快些以nlog2n归队”，快代表快速排序，些代表