526互联

认识o(logn)排序

发布时间 2023-08-03 21:53:13作者: 无聊的飞熊

  1. mid=(L+R)/2 可能会溢出；改成 mid=L+(L-R)/2；提升效率，改成mid=L+(R-L)>>1。

  2. mid=(L+R)/2 可能会溢出；改成 mid=L+(L-R)/2；提升效率，改成mid=L+(R-L)>>1。

  3. 其中：a代表子规模执行次数，b代表子规模大小，d代表除了子规模调用其他的操作的时间复杂度。

  • 若logba<d ，时间复杂度为 O(Nd)

  • 若logba>d ，时间复杂度为 O(Nlogba)

  • 若logba==d ，时间复杂度为 O(Nb * logN)

  • 复习链接

归并排序

  • 整体就是一个简单递归，左边排好序、右边排好序，让其整体有序。

  • 让其整体有序的过程用了外排序方法.

  • 利用master公式来求解时间复杂度

  • 归并排序比另外三个（插入、查找、冒泡）优秀的实质（没有浪费比较，每一轮比较都将结果留存下来了顺序的一个部分数组，不遗漏不重算） 时间复杂度O(N*logN)，额外空间复杂度O(N)

不遗漏不重算：举例数组[a,b,c,d,e,f,g]，以c为例子，a,b先比成为[a,b]，然后与c相比合并成[..c..]的一个数组，接下来c依次合并，并与下面的未知继续比较合并，每个都只比较一次。 为什么归并排序过程中能实现单方向的大小判断？ 实际上是因为归并排序在排序过程中保持了数据的局部有序性，当合并时，在两个子数组整体之间存在相对位置关系。这也是为什么只有在合并的时候才能进行单方向上的大小判断 merge_sort.java

小数和问题Redo（分治策略）

问题描述：小和问题和逆序对问题 小和问题 在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组 的小和。求一个数组 的小和。 例子:[1,3,4,2,5] 1左边比1小的数，没有; 3左边比3小的数，1; 4左 边比4小的数，1、3; 2左边比2小的数，1; 5左边比5小的数，1、3、4、 2; 所以小和为1+1+3+1+1+3+4+2=16 思路：将求左边比自己小的数转换为求右边比自己大的数的数量，再乘上本身，加给结果 merge_fenzhi.java

逆序对问题

问题描述：数组中的两个数，若前面的一个数大于后面的一个数，那么这两个数组成一个逆序对。输入一个数组，返回逆序对的个数 merge_nixudui.java

快排

时间最差情况是O(N2),原因就是划分的位置太差了，即取得第一个或最后一个值 空间最差是O(N)，最好和平均(收敛至)是O(logN),要记录基数(划分值)位置 挖坑填数 + 分治法：举例｛7，5，9，4，1，3，10｝，取第一个数为基数，存到temp中，0位置上空出来，从后往前找第一个比temp小的数字，挖出来放到0位置上，这里是3，然后3位置空出来了，从前往后找比temp大的，这里是9，然后将9放入3位置上，9位置空了出来，从后往前找比7小的数，这里是1，然后从前往后找比temp大的，无了，左右指针相遇，将temp放入4位置

  • 1.0 直接交换 分成两部分，一部分是小于该数，另一部分是大于该数

  • 2.0 分成三部分，一部分是小于该数，一部分是等于该数，另一部分是大于该数。可以一次确定一批数

  • 3.0 每次选数之前，随机等概率选一个位置的数和最后一个数交换，然后再取最后一个数开始划分。这样复杂度为O(N*logN)

  • 4.0 三数取中法，虽然随机基准数方法选取方式减少了出现不好分割的几率，但是最坏情况下还是 O(n²)。为了缓解这个尴尬的气氛，就引入了「三数取中」这样的基准数选取方式 快排1.0 `=quick_sort1.java 快排3.0 quick_sort3.java 快排4.0实现仅替换quick_sort3的partition部分

private static int partition(int[] arr, int left, int right) {
        // 采用三数中值分割法
        int mid = left + (right - left) / 2;
        // 保证左端较小
        if (arr[left] > arr[right])
            swap(arr, left, right);
        // 保证中间较小
        if (arr[mid] > arr[right])
            swap(arr, mid, right);
        // 保证中间最小，左右最大
        if (arr[mid] > arr[left])
            swap(arr, left, mid);
        int pivot = arr[left];
        while (right > left) {
            // 先判断基准数和后面的数依次比较
            while (pivot <= arr[right] && left < right) {
                --right;
            }
            // 当基准数大于了 arr[right]，则填坑
            if (left < right) {
                arr[left] = arr[right];
                ++left;
            }
            // 现在是 arr[right] 需要填坑了
            while (pivot >= arr[left] && left < right) {
                ++left;
            }
            if (left < right) {
                arr[right] = arr[left];
                --right;
            }
        }
        arr[left] = pivot;
        return left;
    }

荷兰国旗问题

(上面问题中条件添加，将等于num的放在数组中间) quick_helanflag.java