Java常见排序算法怎么实现(java,开发技术)

汇总：

1. 冒泡排序

每轮循环确定最值；

publicvoidbubbleSort(int[]nums){inttemp;booleanisSort=false;//优化，发现排序好就退出for(inti=0;i<nums.length-1;i++){for(intj=0;j<nums.length-1-i;j++){//每次排序后能确定较大值if(nums[j]>nums[j+1]){isSort=true;temp=nums[j];nums[j]=nums[j+1];nums[j+1]=temp;}}if(!isSort){return;}else{isSort=false;}}}

2. 选择排序

每次选出最值，再交换到边上；

publicvoidselectSort(int[]nums){for(inti=0;i<nums.length-1;i++){intindex=i;intminNum=nums[i];for(intj=i+1;j<nums.length;j++){if(nums[j]<minNum){minNum=nums[j];index=j;}}if(index!=i){nums[index]=nums[i];nums[i]=minNum;}}}

3. 插入排序

对循环的每个数找到属于自己的位置插入；

publicvoidinsertionSort(int[]nums){for(inti=1;i<nums.length;i++){intj=i;intinsertNum=nums[i];while(j-1>=0&&nums[j-1]>insertNum){nums[j]=nums[j-1];j--;}nums[j]=insertNum;}}

4. 快速排序

选一个基本值，小于它的放一边，大于它的放另一边；

publicvoidquickSortDfs(int[]nums,intleft,intright){if(left>right){return;}intl=left;intr=right;intbaseNum=nums[left];while(l<r){//必须右边先走while(nums[r]>=baseNum&&l<r){r--;}while(nums[l]<=baseNum&&l<r){l++;}inttemp=nums[l];nums[l]=nums[r];nums[r]=temp;}nums[left]=nums[l];nums[l]=baseNum;quickSortDfs(nums,left,r-1);quickSortDfs(nums,l+1,right);}

5. 归并排序

分治算法；

//归publicvoidmergeSortDfs(int[]nums,intl,intr){if(l>=r){return;}intm=(l+r)/2;mergeSortDfs(nums,l,m);mergeSortDfs(nums,m+1,r);merge(nums,l,m,r);}//并privatevoidmerge(int[]nums,intleft,intmid,intright){int[]temp=newint[right-left+1];intl=left;intm=mid+1;inti=0;while(l<=mid&&m<=right){if(nums[l]<nums[m]){temp[i++]=nums[l++];}else{temp[i++]=nums[m++];}}while(l<=mid){temp[i++]=nums[l++];}while(m<=right){temp[i++]=nums[m++];}System.arraycopy(temp,0,nums,left,temp.length);}

6. 希尔排序

引入步长减少数字交换次数提高效率；

6.1 希尔-冒泡排序（慢）

publicvoidshellBubbleSort(int[]nums){for(intstep=nums.length/2;step>0;step/=2){for(inti=step;i<nums.length;i++){for(intj=i-step;j>=0;j-=step){if(nums[j]>nums[j+step]){inttemp=nums[j];nums[j]=nums[j+step];nums[j+step]=temp;}}}}}

6.2 希尔-插入排序（快）

publicvoidshellInsertSort(int[]nums){for(intstep=nums.length/2;step>0;step/=2){for(inti=step;i<nums.length;i++){intj=i;intinsertNum=nums[i];while(j-step>=0&&nums[j-step]>insertNum){nums[j]=nums[j-step];j-=step;}nums[j]=insertNum;}}}

7. 堆排序

大顶堆实现升序，每次将最大值移到堆的最后一个位置上；

publicvoidheapSort2(int[]nums){for(inti=nums.length/2-1;i>=0;i--){sift(nums,i,nums.length);}for(inti=nums.length-1;i>0;i--){inttemp=nums[0];nums[0]=nums[i];nums[i]=temp;sift(nums,0,i);}}privatevoidsift(int[]nums,intparent,intlen){intvalue=nums[parent];for(intchild=2*parent+1;child<len;child=child*2+1){if(child+1<len&&nums[child+1]>nums[child]){child++;}if(nums[child]>value){nums[parent]=nums[child];parent=child;}else{break;}}nums[parent]=value;}

8. 计数排序

按顺序统计每个数出现次数；

publicvoidcountSort(int[]nums){intmax=Integer.MIN_VALUE;intmin=Integer.MAX_VALUE;for(intnum:nums){max=Math.max(max,num);min=Math.min(min,num);}int[]countMap=newint[max-min+1];for(intnum:nums){countMap[num-min]++;}inti=0;intj=0;while(i<nums.length&&j<countMap.length){if(countMap[j]>0){nums[i]=j+min;i++;countMap[j]--;}else{j++;}}}

9. 桶排序

类似计数排序，不同点在于统计的是某个区间（桶）里的数；

publicvoidbucketSort(int[]nums){intmax=Integer.MIN_VALUE;intmin=Integer.MAX_VALUE;for(intnum:nums){max=Math.max(max,num);min=Math.min(min,num);}intbucketCount=(max-min)/nums.length+1;List<List<Integer>>bucketList=newArrayList<>();for(inti=0;i<bucketCount;i++){bucketList.add(newArrayList<>());}for(intnum:nums){intindex=(num-min)/nums.length;bucketList.get(index).add(num);}for(List<Integer>bucket:bucketList){Collections.sort(bucket);}intj=0;for(List<Integer>bucket:bucketList){for(intnum:bucket){nums[j]=num;j++;}}}

10. 基数排序

按个、十、百位依次归类排序；

publicvoidradixSort(int[]nums){intmin=Integer.MAX_VALUE;intmax=Integer.MIN_VALUE;for(intnum:nums){min=Math.min(min,num);max=Math.max(max,num);}for(inti=0;i<nums.length;i++){nums[i]-=min;}max-=min;intmaxLen=(max+"").length();int[][]bucket=newint[nums.length][10];int[]bucketCount=newint[10];for(inti=0,n=1;i<maxLen;i++,n*=10){for(intnum:nums){intdigitVal=num/n%10;bucket[bucketCount[digitVal]][digitVal]=num;bucketCount[digitVal]++;}intindex=0;for(intj=0;j<bucketCount.length;j++){if(bucketCount[j]>0){for(intk=0;k<bucketCount[j];k++){nums[index]=bucket[k][j];index++;}}bucketCount[j]=0;}}for(inti=0;i<nums.length;i++){nums[i]+=min;}}

11. 使用集合或 API

11.1 优先队列

publicvoidpriorityQueueSort(int[]nums){PriorityQueue<Integer>queue=newPriorityQueue<>();for(intnum:nums){queue.offer(num);}for(inti=0;i<nums.length;i++){nums[i]=queue.poll();}}

11.2 Java API

publicvoidarraysApiSort(int[]nums){Arrays.sort(nums);}