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

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 ]