做网站需要学多久,北京海淀建设工程律师哪个好,html网页制作app,在线自助设计平台2.认识O(NlogN)的排序_哔哩哔哩_bilibili master公式 有这样一个数组#xff1a;【0#xff0c;4#xff0c;2#xff0c;3#xff0c;3#xff0c;1#xff0c;2】#xff1b;假设实现了这样一个sort()排序方法#xff0c; 将数组二分成左右两等分#xff0c;使用so…
2.认识O(NlogN)的排序_哔哩哔哩_bilibili master公式 有这样一个数组【0423312】假设实现了这样一个sort()排序方法 将数组二分成左右两等分使用sort()对左右两个小数组进行排序就满足master公式的使用; 或者将数组平均分成三等分n等分都满足master公式。 归并排序 小和问题 原数组一分为二左数组内部求和右数组内部求和左右数组比较求和将三部分小和相加求和。 左数组内部求和右数组内部求和的过程就是原数组一分为二小和相加求和的过程。 问题一 定义一个左边界左指针 遍历数组从数组第一个元素开始比较: 如果比num值大直接跳过 如果比num值小将边界长度1指针右移1位 直到下标越界就实现了遍历一遍整个元素时间复杂度o(n),空间复杂度0(1) 问题二 定义一个左边界左指针右边界右指针 从数组第一个元素开始比较: 默认先调用左指针 如果比num值大将右边界长度1右指针左移1位调用右指针 比num值小将左边界长度1左指针右移1位调用左指针。 直到左右指针相遇。 堆排序 定义 通过堆排序算法实现将给定的数组元素按大小构建一个完全二叉树并且二叉树分为最大堆和最小堆两种类型。 最大堆每颗树的父节点是当前树的最大值或者最大值之一 最小堆每棵树的父节点是当前树的最小值或者最小值之一。 举例 有这样一个数组 int [ ] n {0,99,2,2,3}; 父节点下标father和子节点下标son总满足这样的关系 son father1/ 2 或者 son father2/ 2 或者 father (son-1) / 2 或者 father (son-2) / 2 思路 对于数组每一个值都满足堆排序的定义那它就是一个最大堆或者最小堆。 反过来说遍历数组每一个值进行堆排序最终就能得到最大或最小堆。 heapify() 堆排序方法 1 对于某一颗树对比父节点和左右节点如果最大值还是父节点那这颗树什么都不需要改变就是一个最大堆 2 如果发生左右节点 比 父节点 值大的情况最大值max给父节点原父节点值father下来给子节点。 这时还要考虑子节点father是不是还要向下移动 因为从数组后往前进行heapify()前面的值还没进行heapify()预先还不知道具体情况和值就被拽下来。 实现代码 public class HeapSort {public static void sort(int[] sort){for(int i (sort.length - 1) / 2 ; i 0; i--) {heapify(sort,i,sort.length);}}public static void heapify(int[] arr ,int index ,int heapLenth){int max index;while(true){int left index*2 1;int right left 1;if (left heapLenth arr[left] arr[index]){max left;}if (right heapLenth arr[right] arr[max]){max right;}if (maxindex)break;swap(arr,max,index);index max;}}// public static void heapinsert(int[] nums, int index){
// if (nums.length1)return;
//
//
// while(true){
// if (nums[index] nums [(index-1)/2]){
// swap(nums,index,(index-1)/2);
// }else {
// index;
// }
// if (heapLenthnums.length){
// heapLenth;
// index (index-1)/2;
// }else {
// break;
// }
// }
//
// }public static void swap(int[] nums,int index, int otherIndex){int temporary nums[index];nums[index] nums[otherIndex];nums[otherIndex] temporary;}public static void main(String[] args) {int[] n {0,99,2,2,3};
// int[] n {0,1,2};
// heapinsert(n,0);sort(n);System.out.println(Arrays.toString(n));}
}输出结果为 [ 99 , 3 , 2 , 2 , 0 ]
