[toc]

初级2

题一

给定一个数组arr，和一个数num，请把小于等于num的数放在数 组的左边，大于num的数放在数组的右边。 要求额外空间复杂度O(1)，时间复杂度O(N)

思路

小于等于num区域 和 大于num区域

两个指针： 1. 一个 less --- 小于等于区最后一位 2. 一个 cur --- 当前遍历位置

荷兰国旗问题

给定一个数组arr，和一个数num，请把小于num的数放在数组的 左边，等于num的数放在数组的中间，大于num的数放在数组的 右边。 要求额外空间复杂度O(1)，时间复杂度O(N)

多加 等于区 and 大于区

快速排序

数组算法设计核心

1. 指针移动
2. 边界条件

工业界几乎不会允许递归实现出现，任何递归函数都一定可以转化成为非递归实现

堆 Heap

时间复杂度 O(N * logN) 额外空间复杂度 O(1)

堆结构

1. 分清楚满二叉树，完全二叉树的区别 --- 堆是完全二叉树
2. 具体实现用数组结构，但是我们可以逻辑上想象成一个二叉树
3. 说到堆一定是有隐藏条件的 --- 大根堆 or 小根堆
   1. 大根堆 --- 任何子树中， 父节点 > 子节点
   2. 小跟堆 --- 任何子树中， 父节点 < 子节点

堆结构操作

1. heapInsert --- 增加一个新的节点操作

    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

1. heapify --- 更新节点操作

    public static void heapify(int[] arr, int index, int size) {
        int left = index * 2 + 1;
        while (left < size) {
            int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }

堆排序

排序算法稳定性

定义： 排序结果中，相同值的原始次序不会改变

意义： 保存原始排序中的信息，例如最开始是按照年龄排好序的一组数据，现在想要再对身高进行排序，这时如果排序算法稳定，则按照身高排好序的结果中，相同身高的数据项年龄依然保持原来的有序状态

快速排序和堆排序都是不稳定的

一道坑爹的面试题： 能否将一个数组排序成，奇数放左边，偶数放右边，相对次序不改变

要求：时间复杂度为O(N),额外空间复杂度为O(1)

回答：做不到，因为奇偶和大于小于本质一样，都是一种 01标准，不是0就是1

这两个要求的条件本质和荷兰国旗问题的划分一样，所以这个问题等价于问我快速排序能不能够做到稳定。

比较器 comparator

本质；到底要求怎么排序？基于比较器就很好写代码了

例如，结构体排序时根据什么来排呢？

例如，结构体中

Tips：面试技巧

分清楚压力面试还是故意刁难。

压力面试 --- 问题很尖锐，不给喘息时间，但是态度往往很端正，不会给你出了压力以外的负面情绪

故意刁难 --- 态度很不端正，摆架子，阴阳怪气，而且自己问的问题自己都没有认真准备答案

工业上的排序算法实现

1. 当长度小于 60 时，直接用插入排序，因为常数项极低，而且O(N^2)此时的劣势表现并不明显
2. 当所排序的数组是基础类型 （byte，short，int，double，float），相同数据之间次序无所谓，直接用快排
3. 当所排序的数组是自己定义的结构体类型（student）里面带有多维信息，则用归并排序，保持稳定

其他排序 --- 不基于比较的排序

特点： 受自身数据状况的影响太大

1 桶排序概念

桶是什么？ 一种表示各个数据出现频率的容器

计数排序

一个存储数据（词频）的容器，然后基于这个桶容器把所有数据统计一遍成为词频后（各个数据出现的次数）重新生成一组新的数据，所有过程没有进行过一次比较

经典题目： 给定一个数组，求如果排序之后，相邻两数的最大差值，要求时 间复杂度O(N)，且要求不能用非基于比较的排序

思路：N个数，分配N+1个桶（0~N），先遍历一遍找出最大值和最小值（max and min），min 放在0号桶，max 放在 N号桶，将剩下的N-1个桶均分成等大小的，放入剩下的 N-2个元素，那么必然至少会存在一个空桶。这样做完之后，我们可以排除一个可能性 ： 相邻两数的最大差值一定不会来自于同一个桶中的两个数，一定是来自不同桶的。

实现： 利用三个长度为 N+1 的数组 表示桶中的三个变量 int minList[],int maxList[],boolean isEmptyList[]

遍历每相邻两个桶的最值差： if !isEmptyList[i]： MaxGap = minList[i+1] - maxList[i]