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

算法day05 master公式估算递归时间复杂度归并排序小和问题堆排序

news 2025/6/30 8:33:29

2.认识O(NlogN)的排序_哔哩哔哩_bilibili

master公式

有这样一个数组：【0，4，2，3，3，1，2】；假设实现了这样一个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 = （father+1）/ 2 或者

                                son = （father+2）/ 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 (max==index)break;swap(arr,max,index);index = max;}}//    public static void heapinsert(int[] nums, int index){
//        if (nums.length<=1)return;
//
//
//        while(true){
//        if (nums[index] > nums [(index-1)/2]){
//            swap(nums,index,(index-1)/2);
//        }else {
//            index++;
//        }
//        if (heapLenth<nums.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 ]

查看全文

http://www.lryc.cn/news/404582.html