【算法】图解排序算法之归并排序、快速排序、堆排序
1.归并排序
时间复杂度O(NlogN),额外空间复杂度(N)
求出中间位置,先将左侧排好序,再将右侧排好序,最后将整体整合,不断重复上述过程直到将整个数组排序
如何整合:
定义两个指针指向左右两个子数组最左侧的位置
public static void process(int[] arr, int L, int R) {
if (L == R) {
return;
}
int mid = L + ((R-L) >> 1);
process(arr, L, mid);
process(arr, mid+1, R);
merge(arr, L, mid, R);
}
public static void merge(int[] arr, int L, int M, int R) {
int[] help = new int[R-L+1];
int i = 0; //help的指针
int p1 = L;
int p2 = M+1;
while (p1 <= M && p2 <= R) {
help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= M) {
help[i++] = arr[p1++];
}
while (p2 <= R) {
help[i++] = arr[p2++];
}
for (i = 0; i < help.length; i++) {
arr[L+i] = help[i];
}
}
使用master公式求时间复杂度
T(N) = 2T(N/2) + O(N)
1.1.归并排序的扩展
- 小和问题
问:
在一个数组中,每一个数左边比当前数小的数累加起来,叫做这个数组的小和。求一个数组的小和
例子:[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
答:
转换思路,求每个数x1右边有n1个数比x1大,则我们对ni*xi求和,和即为所求
对于1、3来说,当左侧比右侧小时产生小和,此时1的右侧只有3比1大,所以产生一个1个1作为小和,把1拷贝进help数组,把3拷贝进数组
然后初始化一个新的help数组,参考归并排序,先将左子数组的最左边元素1与右侧数组的最左边元素4比较,1<4所以产生1个1作为小和,把1拷贝到数组,再将左侧子数组指向最左边元素的指针向右移一位,3<4所以产生1个3作为小和,把3拷贝进数组,把4拷贝进数组
...
最后134和25归并
只有排序了才能通过下标的方式算出有几个数比x大,而不是遍历地将右子数组的数一个一个与x比较
public static int process(int[] arr, int l, int r) {
if (l == r) {
return 0;
}
int mid = l + ((r - l) >> 1);
return process(arr, l, mid) + process(arr, mid + 1, r) + merge(arr, l, mid, r);
}
//归并
public static int merge(int[] arr, int l, int mid, int r) {
int[] help = new int[r - l + 1];
int i = 0;
int p1 = l;
int p2 = mid + 1;
int res = 0;
while (p1 <= mid && p2 <= r) {
res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= mid) {
help[i++] = arr[p1++];
}
while (p2 <= r) {
help[i++] = arr[p2++];
}
for (i = 0; i < help.length; i++) {
arr[l + i] = help[i];
}
return res;
}
- 逆序对问题
在一个数组中,左边的数如果比右边的数大,则这两个数构成一个逆序对。打印所有逆序对
2.快速排序
2.1.荷兰国旗问题
问题一
问:
给定一个数组arr和一个数num,请把小于等于num的数放在数组的左边,大于num的数放在数组的右边。要求时间复杂度O(N),额外空间复杂度O(1)
答:
准备一个变量edge,表示小于等于区域的右边界,起初置于整个数组的左侧。i表示当前比较的位置,起初置于edge的右侧,即索引0处
(1) [i] <= num
把当前数与edge位置的后一个数交换,然后edge向右扩一个位置,i++
(2) [i] > num
i++
问题二
问:
给定一个数组arr和一个数num,请把小于num的数放在数组左边,等于num的数放在数组中间,大于num的数放在数组右边。要求时间复杂度O(N),额外空间复杂度O(1)
答:
定义两个边界,edgeL为小于区域的右边界,edgeR为大于区域的左边界
(1) [i] < num
把当前数与edgeL位置的后一个数交换,然后edgeL向右扩一个位置,i++
(2) [i] == num
i++
(3) [i] > num
把当前数与edgeR位置的前一个数交换,然后edgeR向左扩一个位置,i原地不动
2.2.快排1.0
时间复杂度O(N^2)
在当前数组中取最右侧的数x,将小于x的数放在x左侧这个数组的左边(左半个数组),将大于x的数放在x左侧这个数组的右边(右半个数组),此时将x与右半个数组的最左侧的数交换,发现x将当前数组划分为两个部分,左侧的数小于x,右侧的数大于x,x当前的位置就是它排完序后最终的位置
2.3.快排2.0
时间复杂度O(N^2)
2.4.快排3.0
时间复杂度O(NlogN),额外空间复杂度O(logN)
随机选一个数做划分(随机主元),由于数字是随机的,所以无法人为制造出最坏情况
public static void quickSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
quickSort(arr, 0, arr.length-1);
}
public static void quickSort(int[] arr, int l, int r) {
if (l < r) {
//随机生成一个主元并交换到数组的右侧
swap(arr, l + (int)(Math.random()*(r-l+1)), r);
int[] p = partition(arr, l, r);
quickSort(arr, l, p[0] - 1);
quickSort(arr, p[1] + 1, r);
}
}
public static int[] partition(int[] arr, int l, int r) {
int less = l-1;
int more = r;
while (l < more) {
if (arr[l] < arr[r]) {
swap(arr, ++less, l++);
} else if (arr[l] > arr[r]) {
swap(arr, --more, l);
} else {
l++;
}
}
swap(arr, more, r);
return new int[] {less+1, more};
}
3.堆结构
堆在逻辑概念上是完全二叉树结构。完全二叉树要么是满二叉树,要么是从左往右依次变满的二叉树
怎么实现完全二叉树这个结构呢?一个数组从零出发的连续一段可以对应为完全二叉树
[i] 的左孩子是 [2*i+1]
[i] 的右孩子是 [2*i+2]
[i] 的父节点是 [(i-1)/2]
堆是一种比较特殊的完全二叉树,分为大根堆和小根堆
大根堆:每一棵子树的最大值都是头节点的完全二叉树
小根堆:每一棵子树的最小值都是头节点的完全二叉树
3.1.构造堆的过程
构造大根堆的过程:
此时已经不再是大根堆了,需要调整。tempNum的位置为i,它要与自己的父节点(i-1)/2去比较,如果比自己的父节点大就交换,交换后继续与当前父节点比较,直到自己是整棵树的根节点或自己比当前父节点小则停止比较
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;
}
}
while语句虽然只有一个条件,但是排斥了两种情况,第一种情况是当前节点的值比父节点的值小或相等,第二种情况是当前节点是整棵树的根节点,此时index == (index-1)/2,index == 0
3.2.基于堆的操作
3.2.1.删除大根堆的最大值
用堆中最后一个数替换掉第一个数,并heapSize--
将此时的堆顶元素的值与它的两个子节点中最大的节点的值比较,如果堆顶元素小,那么就交换,继续向下比较,直到该节点已经成为叶子结点(没有左右子节点)或该节点比左右子节点都大时停止比较
public static void heapify(int[] arr, int index, int heapSize) {
//数组的范围并非堆的范围,我们使用heapSize来管理堆的大小
int left = 2*index+1;
//while判断了i下面还有没有子节点
while (left < heapSize) {
//两个孩子中谁的值更大,谁就把下标给largest
int largest = left+1 < heapSize && arr[left+1] > arr[left] ? left+1 : left;
//父子之间谁的值大,谁就把下标给largest
largest = arr[largest] > arr[index] ? largest : index;
if (largest == index) {
break;
}
swap(arr, largest, index);
index = largest;
left = 2*index+1;
}
}
3.3.堆排序
时间复杂度O(NlogN),额外空间复杂度O(1)
要使用堆排序对一个数组排序,先把数组转化为一个大根堆。转化完以后将数组0位置的元素与heapSize-1位置的元素交换,且heapSize--,不断重复构造大根堆的过程,直到heapSize==0
public static void heapSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length; i++) {
heapInsert(arr, i);
}
int heapSize = arr.length;
swap(arr, 0, --heapSize);
while (heapSize > 0) {
heapify(arr, 0, heapSize);
swap(arr, 0, --heapSize);
}
}
3.3.1.计算堆排序的时间复杂度
假设数组长度为2N,后N个元素每个元素的调整代价是logN,所以建大根堆的过程的时间复杂度为O(2N * logN * c) = O(NlogN);heapify的时间复杂度也是O(NlogN),所以整个排序的时间复杂度为O(NlogN)
假设一次性给出整个数组的所有元素,把整个数组变成大根堆,我们可以从整个数组的最后一个元素出发,向下进行heapify,向前重复这个过程,实际上叶子结点的每一个数都不需要进行heapify,因为它没有子节点,直到重复到了倒数第二层的节点,依次把每一棵小树变成大根堆。由于我们从下向上执行“构造大根堆”这个过程,因此每次只要至多经历一个heapify的过程,当前树即可变成大根堆
我们假设有一棵满二叉树,有N个节点,它有N/2个叶子结点,这些叶子节点heapify的时候不移动,由于我们遍历了它们一次,认为进行1次操作;倒数第二层节点有N/4个,我们遍历每个倒数第二层节点并且它们至多向下heapify一步,认为进行2次操作;倒数第三层节点有N/8个,遍历每一个倒数第三层节点并且它们至多向下heapify两步,认为进行3次操作......
T(N) = N/2 + N/4 * 2 + N/8 * 3 + N/16 * 4 + ... (1)
2T(N) = N/2*2 + N/2 * 2 + N/4 * 3 + N/8 * 4 + ... (2)
(2) - (1) = T(N) = N + N/2 + N/4 + N/8 + ...
等比数列求和,结果为O(N)
3.3.2.堆排序的扩展
问:
已知一个几乎有序的数组,几乎有序是指,如果要把数组排好序的话,每个元素移动的距离可以不超过k,并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数组进行排序
答:
准备一个小根堆,遍历数组的前k+1个元素,然后把这k+1个数放在小根堆中,排完序后数组的最小值一定在小根堆索引为0的位置,此时把这个数弹出(从小根堆中移除)放在数组的索引为0的位置上,然后把索引为k+1的元素(第k+2个元素)放入小根堆中拍完序后数组中第二小的值一定在此时小根堆索引为0的位置,总之,每一次排序之后当前小根堆索引为0的元素都是待排序的数据中的最小的值,直到所有元素都曾在小根堆中出现过后,把小根堆中的最小值依次弹出,直到小根堆为空
优先级队列即小根堆
PriorityQueue<Integer> heap = new PriorityQueue<>();
(1) 如何扩容:
当数组长度为100不够用时,扩容到200,不够用扩容到400,扩容的次数是logN水平的,但是每一次扩容是N水平的,那么整体扩容的代价就是O(N*logN),我们要把扩容的代价平均下来,算在每一次添加一个数的头上(一共有N个数),除以N,因此扩容的代价是O(logN)
(2)
系统提供的堆结构是一个黑盒,我们无法高效地在改变该堆结构中的某一个值后仍然令它维持堆结构
public void sortedArrDistanceLessK(int[] arr, int k) {
//默认小根堆
PriorityQueue<Integer> heap = new PriorityQueue<>();
int index = 0;
for (: index <= Math.min(arr.length, k); index++) {
heap.add(arr[index]);
}
int i = 0;
for (; indedx < arr.length; i++, index++) {
heap.add(arr[index]);
arr[i] = heap.poll();
}
while (!heap.isEmpty()) {
arr[i++] = heap.poll();
}
}