先看两个问题：
问题一
问题二
问题一：前部设置一个小于等于该数字num的区域，数组中大于num中的直接跳过，小于num的数字与小于等于区域的下一位置互换，该区域往后扩大一个位置
问题二：前部设置一个小于该数字num的区域，后部设置一个大于该数字num的区域，数组中等于num的直接跳过，遇到小于num的与小于区域的下一个位置交换，小于区域往后扩大一个位置，cur也++（cur指向数组中正在处理的数字）；遇到大于num的数，和大于区域的前一个数交换，大于区域向左扩大一个位置，继续考察cur（此时cur指向被换过来的新数字），如此反复直到cur和大于区域相遇
荷兰国旗代码
经典快速排序
数组最后位置的数x作为划分值，小于等于x的放左边，大于x的放右边，然后划分出来的左右两边继续这样递归（取各自位置最后一个数划分）直到整体有序
改进快速排序
数组最后位置的数x作为划分值，等于x的放中间，小于x的放左边，大于x的放右边，然后划分出来的左右两边继续这样递归（取各自位置最后一个数划分，等于x区域不变）直到整体有序
图解
随机快速排序（最常用最重要的排序，代码比较简洁，意味着常数项小）
经典快速排序问题在于总是用最后一个数字，结果每次只能排出来一个数字，算法复杂度变成了O(N^2)，如果那个数字选的好两边规模一样，利用master公式可以得到算法时间复杂度O(N*logN)，和之前归并排序一样
把最后一个数字改成随机选一个数，算法复杂度介于上述两者之间，变成一个概率问题，长期期望变成O(N*logN)，并且额外空间复杂度O(logN)，这是针对随机快排的：
额外空间主要是返回记录的等于区域位置，类似二分的思想，最差情况每个位置都返回，空间复杂度为O(N)，最好情况同上为O(logN)，结合概率知道长期期望是O(logN)
由上述随机快速排序的过程可以得出想绕开数据原有分布状况时可以有以下两种主要操作：①数据状况不可控，随机选择；②哈希函数处理，绕开原始数据状况
工程上准备递归函数的代价很高，系统会记录所有有关无关信息，而且系统栈记录到一定数目会报错不安全，工程上不常见递归，但任何递归都可以改成非递归，工程上都是自己写
堆排序（heap，堆）
时间复杂度O(N*logN)，额外空间复杂度O(1)
堆结构：①heapInsert与heapify②堆结构的增大和减少③建立堆的过程时间复杂度为O(N)④优先级队列结构就是堆结构
堆就是完全二叉树，任何一个非叶节点两个分支都存在，记为满二叉树，满二叉树属于完全二叉树；如果是满二叉树最下面一层从左往右依次补齐，也属于完全二叉树
完全二叉树反例
堆可用数组实现：
数组实现完全二叉树
这棵树没有实际落地，但是可以通过数组脑补出一颗二叉树，注0的父节点是自己
大根堆：完全二叉树中，任何一颗子树的最大值是子树的头部
小根堆：完全二叉树中，任何一颗子树的最小值是子树的头部
heapInsert建立大根堆：将数组中的数一个个按完全二叉树的结构填写，一旦子节点比父节点大则互换，这样每添加一个数字都形成大根堆
heapInsert建立大根堆的代码
建立大根堆时，每加进来一个节点的时间复杂度为O(logN)，所有节点相加即O(log1)+O(log2)+...+O(logN)=O(N)，即建立一个大根堆的复杂度为O(N)
heapify：如果数组中某一个数变小了，则把它与两个子节点中最大的交换
heapify代码
减堆操作：堆顶和最后一个数交换，最后一个数弹出，堆顶的数进行heapify
求中位数：一个数接一个数的出来，求出来若干数时的中位数。设置一个大根堆和一个小根堆，若两个堆中的数目相差超过1，对数目多的堆进行减堆操作，时刻保持较小的n/2个数在大根堆，较大的n/2个数在小根堆，这样的话中位数就是两个堆顶的计算
堆排序：交换堆顶和最后一个数，最后一个数排出堆结构，这个最大的数就放在数组的后面，然后堆顶进行heapify，如此操作直到整个数组有序
堆排序代码
网友评论