排序算法---（四）

引言在前几篇文章里面讲到了六种排序今天来讲一下剩下两种基数排序、堆排序基数排序1.思路1首先确定最大数的位数找到待排序数组中的最大数并确定其位数2将元素按照相应的位数存入桶中先定义一个桶二维数组用来存放待排序数组元素再定义一个桶计数器一维数组用来记录每个桶里面有几个元素将元素放入桶中有三步① 放哪个桶看相应位数是多少例如相应位数上是1那么就放在x坐标为1的桶里、② 找到桶应该放在桶内的哪个位置因为相应位数上是同一个数字的可能有多个因此桶计数器发挥作用了若计数为3那说明这个桶已经放了三个元素了那将待放入元素放在第四个位置上、③ 更新桶计数器13相应位数排完序后将存入桶里元素有序的放回原数组2.代码public class jsSort { public static void main(String[] args) { int[] arrnew int[]{5,1,3,9,8,2}; int narr.length; sort(arr); for(int i0;in;i){ System.out.print(arr[i] ); } } public static void sort(int[] arr) { int maxarr[0]; for(int i0;iarr.length;i){ if(arr[i]max){ maxarr[i]; } } int maxLength(max).length(); int[][] bucketnew int[10][arr.length]; int[] bucketCountnew int[10]; int t1; for(int i0;imaxLength;i){ //存数据 for(int j0;jarr.length;j){ int elementarr[j]/t%10; bucket[element][bucketCount[element]]arr[j]; bucketCount[element]; } int index0; //取数据 for(int k0;k10;k){ if(bucketCount[k]!0){ for(int j0;jbucketCount[k];j){ arr[index]bucket[k][j]; } } bucketCount[k]0; } tt*10; } } }堆排序1.相关知识完全二叉树从上到下、从左到右依次填满结点前面每一层必须是满的最后一层可以不满但只能缺右边的结点不能中间空、不能左边空大顶堆在完全二叉树的基础上父节点的值大于左右孩子的值2.思路1首先将待排序数组构造成一个大顶堆此时整个数组最大值就被放在了二叉树的顶端2将堆顶元素和堆底元素进行交换此时堆底元素变成了整个数组最大值3重新构建大顶堆不包含上一步的堆底元素最大值重复上述步骤这样就实现了每次都把最大元素拿出来实现了数组升序3.关键点构造大顶堆从最后一个元素当作parent首先判断是否有孩子childparent*21是否小于nums.length直到找到符合条件的parent找到后开始判断parent和child哪个大大的换到parent位置依次遍历遍历到二叉树的最顶端数组的第一个元素这样不断地向上遍历并交换就实现了堆顶元素是数组最大的元素排除上一轮的堆底元素只需要将待排序数组长度减一即可4.代码public class heapSort { public static void main(String[] args) { int[] arrnew int[]{5,1,3,9,6,8,2}; for(int iarr.length-1;i0;i--){ sort(arr,i,arr.length); } //交换堆顶元素和堆底元素并排除堆底元素 for(int karr.length-1;k0;k--){ int temparr[k]; arr[k]arr[0]; arr[0]temp; sort(arr,0,k); } //循环输出 for(int j0;jarr.length;j){ System.out.print(arr[j] ); } } public static void sort(int[] arr,int parent,int length){ int childparent*21; while(childlength){ int rChildchild1; if(rChildlength arr[rChild]arr[child]){ child; } //将大的元素放在parent位置 if(arr[child]arr[parent]){ int temparr[child]; arr[child]arr[parent]; arr[parent]temp; parentchild; childparent*21; }else{ break; } } } }小舟有话说至此八大排序已全部讲解完毕其中要求我们熟练掌握的有三种排序冒泡排序、快速排序、堆排序大家一定要熟练记忆堆排序虽然看起来难理解但是只要懂了二叉树相关知识就不难。如果觉得内容不错那就点点赞点点关注吧下次找我不迷路~