左神算法-基础课-02-笔记

快速排序

问题一:partition

给定一个数组$arr$, 和一个数$num$,请把小于等于$num$的数放在数组的左边,大于$num$的数放在数组的右边。

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

解决答案

image-20201002124018348

image-20201002124024185

image-20201002124028365

问题二:荷兰国旗问题

给定一个数组$arr$, 和一个数$num$,请把小于等于$num$的数放在数组的左边,等于$num$的数放在中间,大于$num$的数放在数组的右边。

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

解决答案

三个变量$less$, $cur$ 和 $more$;

$less$ 表示 $0$ ~ $less $为小于$num$的区域;初始为 -1;

$cur$ 表示 当前判断的数在数组的下标;初始为0;并且 0 ~ $cur$的数组区域都是小于等于$num$的值;

$more$ 表示 $more$ ~ $arr.length-1$为大于$num$的区域;初始为 $arr.length$;

graph TD
A[开始] -->B(less初始值为-1)
    A -->F(cur初始值为0)
    A -->G(more初始值为arr.length)
    F -->I{cur是否小于more}
    G -->I
    B --> I
    C{判断arr的cur上的值} -->|小于num| D[cur位置和less+1位置交换 less+=1]
    C -->|等于num| H[cur= cur+1]
    C -->|大于num| E[cur位置和more-1位置交换 more-=1]
    D --> H
    H --> I
    E --> I
    I -->|是| C
    I -->|否| J[结束 返回less+1,more-1]

要考虑一下一些情况:

  1. 如果等于区域不存在

  2. 小于区域不存在

  3. 大于区域不存在

  4. 小于等于区域不存在

  5. 大于等于区域不存在

  6. 小于大于不存在(全是等于)

经典快速排序

原始经典快速排序;

荷兰国旗问题来改进;

经典快排的问题

划分出来的区域不是等规模的:特别在差不多有序情况下进行经典快排则会导致$O(N^2)$;本质上和数据状况是有关系的;

随机快速排序

随机快速排序的细节和复杂度分析

和经典快排不同的地方在于选择partitionnum值;经典快排都是选择一个确定位置的值(第一个值或者最后一个值)来对整个数组进行划分;而这样就和数据状况存在关系。所以随机快速排序随机选择划分整个过程的num值。虽然这样选择的值也可能出现划分出来的区域不是等规模的。但是这只是一个概率事件,我们不能得知其时间复杂度的最差情况;只能用长期期望的方式算出它的时间复杂度。我们长期期望得到的时间复杂度为:$O(N*log N)$;

随机快速排序的组成

  1. 主函数:输入一个要排序的数组

    1
    2
    3
    4
    5
    6
    /*
    快排主函数:
    先判断数组需不需要排序
    然后对 0 ~ arr.length-1 区间里调用2函数
    */
    public static void quickSort(int[] arr)
  2. 对区间里进行快速排序

    1
    2
    3
    4
    5
    6
    7
    8
    /*
    如果左边界小于右边界
    在数组中随机选一个数作为分割数num,将其交换到l最后一个位置去
    按上一步找的数用 3 partition 把数组分为三部分:[小于num的,等于num的,大于num的],返回 [等于num的] 的边界,方便后两步
    对 [小于num的] 执行快速排序
    对 [大于num的] 执行快速排序
    */
    public static void quickSort(int[] arr, int l, int r)
  3. 分割数组

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    /*
    partition需要 less = l-1记录小于num的区域的边界,more = r记录大于num区域的边界 cur=l arr[r]保存着分割数num
    这个思想与框图里的一样:
    【l~less:小于num的区域, less+1~cur-1:等于num的区域, cur~more-1:未分类的区域, more~r-1:大于num的区域】
    只要未分类的区域还存在循环不停止:
    如果arr[cur] < arr[r]:要把它换到小于区域的下一个,而这个值是等于num区域的值;交换 ++less 和 cur++;
    如果arr[cur] > arr[r]:把他换到大于区域前一个,交换过来的这个是未知区域的值;则要继续对cur位置做判断;
    如果arr[cur] = arr[r]:当前数要划分进等于num的区域,直接cur++;
    直接结束,交换more与r位置的数;
    返回:[less+1, more]
    */
    public static int[] partition(int[] arr, int l, int r)

规避数据状况对算法的影响的方法

  1. 随机
  2. 哈希函数

时间复杂度$O(N*log N)$,额外空间复杂度$O(log N)$

空间复杂度为什么是$O(log N)$?为了记录大于num和小于num的位置,并且需要递归记录。所以额外的空间承了一颗二叉树一样得。所以是$O(log N)$

题外话:任何递归函数都可以改写为非递归函数;

递归函数的压栈是对函数进行压栈,消耗的常数级空间和资源都比较大。并且系统栈是有限的,深度递归会造成不安全。

堆排序

堆的表示

堆的数据结构:完全二叉树

物理表示:一个数组,分为以0位置为根节点以1位置为根节点两种表示方式;

以0位置为根节点

i位置的左孩子:$2*i+1$

​ 右孩子:$2*i+2$;

i位置的父节点: $\frac{i-1}{2}$

以1位置为根节点

i位置的左孩子:$2*i$

​ 右孩子:$2*i+1$

i位置的父节点:$\frac{i}{2}$

堆的分类

分为大顶堆和小顶堆

大根堆:在这个完全二叉树中任何一个子树的最大值都在子树的根上。

小根堆:在这个完全二叉树中任何一个子树的最小值都在子树的根上。

建立堆

以大顶堆为例;

思想:给定一个数组把它构建为一个大顶堆;

1
2
3
4
5
6
7
宏观:我们认为0 ~ i-1间已构成大顶堆,然后插入第i个数;i初始值为0,不断插入堆中,不断增长,一直到N-1;
中层:
把一个数插入进完全二叉树:
循环判断:if i是否有父节点 并且 i位置数大于父节点:
与父结点进行交换
else:
结束;
1
2
3
for (int i = 0; i <arr.length ; i++) {
heapInsert(arr, i);
}

tip:这里看到左神代码,可以符合i没有父节点和大于父节点两种情况的判断

1
2
3
4
// 判断i位置和其父节点
while (arr[i] > arr[(i-1)/2]){ // 在i=0时是否合适?

}

​ 经过验证java中的整除除法的整除,如果是负值则会往比较大的方向贴

1
2
3
4
-1 / 40
-3 / 40
-4 / 4 : -1
-5 / 4 : -1

​ 而python不同:

1
2
3
-1 // 4-1
-3 // 4-1
-5 // 4-2

插入堆(heapinsert)

1
public static void heapInsert(int[] arr, int index)

插入堆就是要不停的与父节点进行比较。如果大于就交换,小于则停止;

调整堆(heapify)

1
public static void heapify(int[] arr, int index, int size)

大顶堆中的一个数变小了,要对这样的情况进行调整;把它与他的两个子节点进行比较;如果大于它的左右节点那么就不调整了,如果小于就与较大的子节点进行交换。直到其大于他的左右子节点。当然结束条件不仅仅是大于两个子节点,也有子节点越界的情况。

已知:堆数组arr,调整数的下标 index,堆大小 heapsize

graph TD
A[开始] -->B[左节点下标 left = index * 2 + 1]
B --> C{left < heapsize}
C -->|yes|D[获得左右节点的较大值]
C -->|no|E[结束]
D -->F{index大于子节点}
F -->|yes|G
G -->E
F -->|no|H
H -->I[交换子节点较大值与index]
I -->J[index=较大值]
J -->B

堆的使用

例一:一个数据流不停的输出数;求当前输出数字的中位数;

分析:请求中位数是随时可能出现的;所以用普通线性容器对其进行排序所需的时间复杂度很高。

所以用堆来实现这个过程就很方便:

题解:

需要:一个大根堆存放较小的$\frac{N}{2}$个数;用大根堆把他们的最大值放在根部;

​ 一个小根堆存放较大的$\frac{N}{2}$个数;用小根堆把他们的最小值放在根部;

​ 大根堆和小根堆中元素的个数差不超过1;

分析:当大根堆和小根堆元素个数相同时:中位数为两个堆顶部元素的均方;

​ 当大根堆和小根堆元素个数差1时:中位数为元素较多所在堆的根部;

维护堆

​ 初始:把元素加入进大顶堆;

​ 插入元素:

​ a. 判断插入元素是否小于大顶堆根部,如果是则插入大顶堆,否则插入小顶堆

​ b. 再判断大顶堆和小顶堆元素个数的差;如果大于1,则弹出元素数较大的堆的根,再插入元素数较小的堆中;使其平衡;

堆排序

graph TD
A[开始] --> B{数组大小大于1}
B -->|是|H[构建堆] 
H -->C[将堆中最后一个数与根交换]
C --> D[堆大小减1]
D --> F{堆大小不为空}
F --> |是|E[调整堆做一次heapify]
E -->C
F --> |否|G
B -->|否| G[排序完成]

排序算法的稳定性及其汇总

稳定性:相同的值经过排序之后他们在序列中的相对顺序会不会被打乱;不被打乱就是稳定的;

冒泡排序:可以实现稳定,大数沉底,但是遇到相等的时候不交换就可以实现稳定;

插入排序:可以实现稳定;从后往前插入,遇到相等的就停止。

选择排序:不是稳定的;需要与i位置往后最小值交换,使得其相对顺序会变化;

归并排序:可以实现稳定;元素相等情况下,先把左边数组的相等值优先拷贝进辅助数组,再拷贝右边数组的相等值;

快速排序:不是稳定的;partition的过程也有随机交换的地方;

堆排序:不是稳定的;

稳定性有什么意义? 现实世界有可能需要保证他的原始顺序;

工程中的综合排序算法

工程中使用的排序算法则不是利用某种排序算法,它是一个综合考虑各种情况各种排序算法优劣的算法;

  • 如果需要排序的数组长度很长

    先判断里面装的是基础类型,还是自定义类型?因为基础类型不需要考虑稳定性;

    • 基础类型:用快排
    • 自定义类型:归并排序
  • 数组长度很短则直接用插入排序;因为插入排序所需的常数项操作很低。

有关排序问题的补充

  • 归并排序所需的时间复杂度O(n)的可以变成O(1)的,可以学习:“ 归并排序 内部缓存法 ”;非常难;
  • 快速排序可以做到稳定性,可以学习:“ 01 stable sort ”;非常难;

认识比较器的使用

Arrays.sort 里有一个比较器接口:

1
public static void sort(T[] a,int fromIndex,int toIndex, Comparator c)

通过自定义比较类型的比较器可以实现

1
2
3
4
5
6
7
8
public static class IdAscendingComparator implements Comparator<T>{
@Override
public int compare(T o1, T o2){
return 负数; // 比较时第一个数o1放在o2前面
return 正数; // 比较时第二个数o2放在o1前面
return 0// 认为这样个数一样大
}
}

因为自定义类型不告诉排序函数它用什么比较器,那么排序函数就会用内存地址对他们进行比较;

同样的java里还有优先队列;优先队列也就是一个堆;堆是大顶堆还是小顶堆都是需要用比较器来说明的;

1
PriorityQueue<Student> heap = new PriorityQueue<>(new IdAscendingComparator());

还有TreeSet<Student> treeset = new TreeSet<>(new IdAscendingComparator());

桶排序、计数排序、基数排序

【例】一串数字,他们都是0~60范围里的数。要对这串数字进行排序;

可以实现一个数组用来统计相应位置上的数出现的个数。在利用整个数组得到排序后的结果;

而这里数组中的 i 位置保存数字 i 的个数。这就是一个桶;

桶保存了一种数据状况出现的词频,是容器;

桶排序

而桶排序是一种思想,它不是具体的某一个排序算法。而基数排序与计数排序都是对它的具体实现;

但是可以看到这种排序是有局限性的,它的使用与数据状况关联很大;

计数排序要求被排序的数字在某一个范围里面;不然的话所需的范围极大,所需的桶也极多。这是它不好的地方;

补充问题

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

step-1 : 排序数组有N个数,那么准备N+1个桶

step-2 : 遍历整个数组找到其最大值与最小值

step-3 : 如果最大值与最小值相等则说明数组中都是一样的数,就直接返回0;

step-4 : 如果不相等则分别把最小值放在0号桶里,把最大值放在N号桶里。

step-5 : 把桶按最小值与最大值之间的范围等分为N+1份

分析

​ 设一个桶能装的范围是p,它是由 $\frac{最大值 - 最小值}{N-1}$ 计算而来

​ 由于有N个数放进N+1个桶里。那么起码会出现一个空桶;

​ 相邻的两个数会出现在两个地方:在同一个桶里,在不同的桶里;

​ 相邻的两个数在一个桶里他们的差值不会大于桶的范围:$(1, p-1)$;

​ 两个数在相邻两个桶,他们的差值范围在 $(1, 2*p-1)$;

​ 而两个数中间有一个空桶的相邻数一定大于桶的范围 $(p+1, 3p-1)$;

​ 因为起码会出现一个空桶,所以相邻数的差的最大值不会出现在同一个桶里。所以只需要查看桶之间的差值就好了。

对这个过程进行完整的描述:

step-1 : 排序数组有N个数,那么准备N+1个桶;这个桶只保存有没有进来过数,进来数中最大值,最小值,这三样信息;

step-2 : 遍历整个数组找到其最大值与最小值

step-3 : 如果最大值与最小值相等则说明数组中都是一样的数,就直接返回0;

step-4 : 如果不相等则分别用最小值更新0号桶布尔值,最大值和最小值,用最大值更新N号桶的布尔值,最大值和最小值。

step-5 : 然后依次把数组中的数字填入相对应的桶中;

step-6 : 对桶进行遍历,依次比较当前桶的最小值与上一个非空桶最大值的差,找到其中最大的值;

image-20201020174415858