当前位置：首页 > news >正文

排序算法---（四）

news 2026/5/25 22:51:03

引言

在前几篇文章里面讲到了六种排序，今天来讲一下剩下两种：基数排序、堆排序

基数排序

1.思路

（1）首先确定最大数的位数：找到待排序数组中的最大数，并确定其位数

（2）将元素按照相应的位数存入桶中：先定义一个桶（二维数组）：用来存放待排序数组元素，再定义一个桶计数器（一维数组）：用来记录每个桶里面有几个元素，将元素放入桶中有三步：① 放哪个桶（看相应位数是多少，例如相应位数上是1，那么就放在x坐标为1的桶里）、② 找到桶应该放在桶内的哪个位置（因为相应位数上是同一个数字的可能有多个，因此桶计数器发挥作用了，若计数为3，那说明这个桶已经放了三个元素了，那将待放入元素放在第四个位置上）、③ 更新桶计数器（+1）；

（3）相应位数排完序后，将存入桶里元素有序的放回原数组

2.代码

public class jsSort { public static void main(String[] args) { int[] arr=new int[]{5,1,3,9,8,2}; int n=arr.length; sort(arr); for(int i=0;i<n;i++){ System.out.print(arr[i]+" "); } } public static void sort(int[] arr) { int max=arr[0]; for(int i=0;i<arr.length;i++){ if(arr[i]>max){ max=arr[i]; } } int maxLength=(max+"").length(); int[][] bucket=new int[10][arr.length]; int[] bucketCount=new int[10]; int t=1; for(int i=0;i<maxLength;i++){ //存数据 for(int j=0;j<arr.length;j++){ int element=arr[j]/t%10; bucket[element][bucketCount[element]]=arr[j]; bucketCount[element]++; } int index=0; //取数据 for(int k=0;k<10;k++){ if(bucketCount[k]!=0){ for(int j=0;j<bucketCount[k];j++){ arr[index++]=bucket[k][j]; } } bucketCount[k]=0; } t=t*10; } } }

堆排序

1.相关知识

完全二叉树：从上到下、从左到右依次填满结点，前面每一层必须是满的，最后一层可以不满，但只能缺右边的结点，不能中间空、不能左边空

大顶堆：在完全二叉树的基础上父节点的值大于左右孩子的值

2.思路

（1）首先将待排序数组构造成一个大顶堆，此时整个数组最大值就被放在了二叉树的顶端

（2）将堆顶元素和堆底元素进行交换，此时堆底元素变成了整个数组最大值

（3）重新构建大顶堆，不包含上一步的堆底元素（最大值），重复上述步骤，这样就实现了每次都把最大元素拿出来，实现了数组升序

3.关键点

构造大顶堆：从最后一个元素当作parent，首先判断是否有孩子：child=parent*2+1是否小于nums.length，直到找到符合条件的parent，找到后开始判断parent和child哪个大，大的换到parent位置，依次遍历，遍历到二叉树的最顶端（数组的第一个元素），这样不断地向上遍历并交换，就实现了堆顶元素是数组最大的元素

排除上一轮的堆底元素：只需要将待排序数组长度减一即可

4.代码

public class heapSort { public static void main(String[] args) { int[] arr=new int[]{5,1,3,9,6,8,2}; for(int i=arr.length-1;i>=0;i--){ sort(arr,i,arr.length); } //交换堆顶元素和堆底元素，并排除堆底元素 for(int k=arr.length-1;k>=0;k--){ int temp=arr[k]; arr[k]=arr[0]; arr[0]=temp; sort(arr,0,k); } //循环输出 for(int j=0;j<arr.length;j++){ System.out.print(arr[j]+" "); } } public static void sort(int[] arr,int parent,int length){ int child=parent*2+1; while(child<length){ int rChild=child+1; if(rChild<length && arr[rChild]>arr[child]){ child++; } //将大的元素放在parent位置 if(arr[child]>arr[parent]){ int temp=arr[child]; arr[child]=arr[parent]; arr[parent]=temp; parent=child; child=parent*2+1; }else{ break; } } } }