【leetcode】(二)认识O(NlogN)的排序-171主机测评

（一）剖析递归行为和递归行为时间复杂度的估算

用递归方法找一个数组中的最大值，系统上到底是怎么做的？

master 公式的使用

T(N) = a*T(N/b) + O(N^d)

1）log(b,a) > d -> 复杂度为 O(N^log(b,a)) 2）log(b,a) = d -> 复杂度为 O(N^d * logN) 3）log(b,a) < d -> 复杂度为 O(N^d)

补充阅读：www.gocalf.com/blog/algorithm-complexity-and-master-theorem.html

1.递归实现找一个数组中的最大值

说明：求中点的位置：一般来说是mid=(L+R)/2，但是如果数组开的长度过大，对（L+R）计算时会产生溢出，故可以写成mid=L+(R-L)/2,采用右移可以写成mid=L+(R-L)>>1。

代码：

package class002;

import java.util.Arrays;

//递归方法实现求数组最大值

public class Code_GetMax {
public static int getMax(int[] arr){
return process(arr,0,arr.length-1);
}
//arr[L..R]范围上求最大值 N
public static int process(int[]arr,int L,int R){
if (L==R){//arr[L..R]范围上只有一个数，直接返回，basecase
return arr[L];
}
// for (int i=L;i<=R;i++){
// System.out.println(arr[i]);
// }
int mid=L+((R-L)>>1);//中点
int leftMax=process(arr,L,mid);
int rightMax=process(arr,mid+1,R);
return Math.max(leftMax,rightMax);
}
public static void main(String[] args){
int []arr1={1,2,3,4};
int []arr2={11,43,32,12,24};
System.out.println("arr1："+ Arrays.toString(arr1));
System.out.println("arr1 max: "+ getMax(arr1));
System.out.println("arr2："+ Arrays.toString(arr2));
System.out.println("arr2 max: "+ getMax(arr2));
}

}

运行结果：

arr1：[1, 2, 3, 4]
arr1 max: 4
arr2：[11, 43, 32, 12, 24]
arr2 max: 43

解释：

对于数组【3，2，5，6，7，4】，对应序列{0，1，2，3，4，5}

开始:

（1）p(0,5)->p(0,2)+p(3,5)

（2）p(0,2)->p（0,1)+p(2,2),此时p(2,2)return;p(3,5)->p(3,4)+p(5,5),此时p(5,5)return;

（3）p(0,1)->p（0,0)+p(1,1),此时p(0,0)return,p(1,1)return;p(3,4)->p(3,3)+p(4,4),此时p(3,3)return,p(4,4)return;

结束。

类似于后序遍历：

后序遍历(PostOrder) 的操作过程如下：若二叉树为空，则什么也不做，否则， 1)后序遍历左子树; 2)后序遍历右子树; 3)访问根结点。

流程图：

[0~5]
/ \\
[0~2] [3~5]
/ \\ / \\
[0~1] [2] [3~4] [5]
/ \\ 5 / \\ 4
[0] [1] [3] [4]
3 2 6 7

2.master 公式的使用

T(N) = a*T(N/b) + O(N^d)

其中，T（N）是母问题的规模（每个大小为N）,T(N/b)是子问题的规模（每个大小为N/b）a是调用次数，O(N^d)是除去调用之外剩下的过程（d = 0：当前层只做常数次操作，比如加减，比较大小；d = 1：当前层需要遍历 N 个数据，比如循环打印数组）。简单说，就是一个问题，N个数据，拆分成a个小问题，每个小问题有N/b个数据。

对于1中的问题，不循环打印一遍数组，a=2，b=2,d=0,T(N) = 2*T(N/2) + O(1)；如果循环打印一遍数组，就变成a=2，b=2,d=1,T(N) = 2*T(N/2) + O(N)。

1）log(b,a) > d -> 复杂度为 O(N^log(b,a)) 2）log(b,a) = d -> 复杂度为 O(N^d * logN) 3）log(b,a) < d -> 复杂度为 O(N^d)

对于1中的问题，不循环打印一遍数组，a=2，b=2,d=0,T(N) = 2*T(N/2) + O(1)，时间复杂度为O(N^log(2,2))=O（N）；如果循环打印一遍数组，就变成a=2，b=2,d=1,T(N) = 2*T(N/2) + O(N),时间复杂度为O（N*logN）。

（二）归并排序

1）整体就是一个简单递归，左边排好序、右边排好序，让其整体有序 2）让其整体有序的过程里用了外排序方法 3）利用master公式来求解时间复杂度 4）归并排序的实质

由master公式可知，归并排序的时间复杂度 O(N*logN)，额外空间复杂度 O(N)

1.时间复杂度

归并排序与选择排序的区别：选择排序每次只比较一个元素的信息，只有一个元素有序，没有把比较的信息传递下来，因此算法复杂度是O(n^2);归并排序通过将元素划分到单一元素，在最小的单元上进行比较，形成了局部有序的单元，在单元合并的时候把比较的信息传递下来，因此时间复杂度为O(N*NlogN)。

2.空间复杂度

申请了一个外部数组，用完即释放(Java特性，C++需要手动释放，注意区别)，因此空间复杂度为O(N)

3.代码

package class002;

import java.util.Arrays;

public class Code_MergeSort {
public static void mergeSort(int[] arr){
if (arr ==null || arr.length<2){
return;
}
process(arr,0,arr.length-1);
}
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;
int p1=L;//左侧区域从L开始
int p2=M+1;//右侧区域从M+1开始
while(p1<=M && p2<=R){
//不越界的情况下，如果p1位置的数小于p2位置的数，将p1位置的数拷贝到help[i]位置上去，且p1向右移动一位，i的位置也右移；
//如果p1位置的数不小于p2位置的数，将p2位置的数拷贝到help[i]位置上去，且p2向右移动一位，i的位置也右移；
//直到发生越界
help[i++]=arr[p1]<=arr[p2] ? arr[p1++]:arr[p2++];
}
//如果越界，则会执行下面两个while循环中的其中一个，谁没越界，则把剩下的数拷贝到help[i]中去
while (p1<=M){
help[i++]=arr[p1++];
}
while(p2<=R){
help[i++]=arr[p2++];
}
//最后，把整个数组拷贝回arr[]中，完成整个过程
for (i=0;i<help.length;i++){
arr[L+i]=help[i];
}
}
public static void main(String[] args){
int []arr1={4,8,9,43,21};
int []arr2={11,43,32,12,24};
System.out.println("arr1："+ Arrays.toString(arr1));
mergeSort(arr1);
System.out.println("arr1 mergeSort: "+Arrays.toString(arr1));
System.out.println("arr2："+ Arrays.toString(arr2));
mergeSort(arr2);
System.out.println("arr2 mergeSort: "+Arrays.toString(arr2));
}
}

运行结果：

arr1：[4, 8, 9, 43, 21]
arr1 mergeSort: [4, 8, 9, 21, 43]
arr2：[11, 43, 32, 12, 24]
arr2 mergeSort: [11, 12, 24, 32, 43]

执行过程：

[4,8,9,43,21]

//拆分：

[4,8,9,43,21]
/ \\
[4,8,9] [43,21]
/ \\ / \\
[4,8] [9] [43] [21]
/ \\
[4] [8]

//合并（同时排序）

[4] + [8]
↓
[4,8]

[4,8] + [9]
↓
[4,8,9]

[43] + [21]
↓
[21,43]

[4,8,9] + [21,43]
↓
[4,8,9,21,43]

4.归并排序的扩展

小和问题和逆序对问题

小和问题在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。例子：[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

逆序对问题在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对，请打印所有逆序对。

（1）小和问题分析：

求小和的过程，实际上是这个数组中的每个数在问题中会被加几次，可以反过来比较每一个数的右边有几个数比这个数大。举例：

[1, 3, 4, 2, 5] 1右边边比1大的数，4个，4*1=4； 3右边比3大的数，2个，2*3=6； 4右边比4大的数，1个，1*4=4； 2右边比2大的数，1个，1*2=2； 5右边比5大的数，没有；所以小和为4+6+4+2=16，等效于原来的例子。

gpt的“矩阵”解释：

因此可以采用归并排序，但与归并排序的一点差别是：面对左组和右组相等的情况，一定要先拷贝右组。

代码：

package class002;

import java.util.Arrays;

public class Code_SmallSum {
public static int smallSum(int[] arr){
if (arr==null|| arr.length<2){
return 0;
}
return process(arr,0,arr.length-1);
}
//arr[L..R]既要排好序，也要求小和
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 m,int r){
int[] help=new int[r-L+1];
int i=0;
int p1=L;
int p2=m+1;
int res=0;
while (p1<=m && p2<=r){
//都不越界时，只有左组比右组小，才产生小和数量增加的情况，
//添加的小和量=当前右组的数有多少个比当前p1所指的数大*p1的值
//如果左组不比右组小，小和增加的量=0
res+=arr[p1]<arr[p2]?(r-p2+1)*arr[p1]:0;
//拷贝：如果左组严格比右组小的时候才拷贝左组，大于等于的时候拷贝右组
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];
}
return res;
}
public static void main(String[] args){
int []arr1={4,8,9,43,21};
int []arr2={11,43,32,12,24,12};
System.out.println("arr1："+ Arrays.toString(arr1));
System.out.println("arr1 smallSum: "+smallSum(arr1));
System.out.println("arr2："+ Arrays.toString(arr2));
System.out.println("arr2 smallSum: "+smallSum(arr2));
}
}

运行结果：

arr1：[4, 8, 9, 43, 21]
arr1 smallSum: 58
arr2：[11, 43, 32, 12, 24, 12]
arr2 smallSum: 67

（三）荷兰国旗问题与快速排序

1.荷兰国旗问题

问题一

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

问题二（荷兰国旗问题）/leetcode75

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

问题一分析：

（1）[i]<=num,将[i]和<=区的下一个数交换,<=区向右扩一个位置，i++;

（2）[i]>num,i++;

问题二分析：

这里相对于问题一多了一个>区域边界。假定数组长度为N（范围[0~N-1]），先设定两个初始区域（>区域和<区域，初始大小为0）位于数组的两端，起始位置接着设置一个“等于比较器k”在数组中不断向右移动：（1）“等于比较器k”遇到第一个比自己小的数，则“<区”向右增加1；“等于比较器k”遇到第一个比自己小的数，则“<区”向右增加1（范围变为[0~0]），“等于比较器k”向右移动一位；（2）“等于比较器k”遇到和自己相等的数，则直接向右移动；（3）"等于比较器k”遇到第一个比自己大的数，则将它和数组末端（[N-1]）进行交换（注意，由于[N-1]只是被交换而没有被检查，所以i必须不动），“>区”向左扩一位（范围变成[N-1~N-1]）——此时用"等于比较器k”检查这个被交换过来的数，如果这个被交换过来的数大于"等于比较器k"，那么这个被交换过来的数向左移动，重复（1）的操作；否则重复（2）的操作；否则重复（3）的操作。当“>区”和“等于比较器k”装上时，流程终止。

程序流程：

（1）[i]<=num,[i]和<区下一个交换，<区右扩，i++;

（2）[i]==num,i++;

（3）[i]>num,[i]和>区前一个交换，>区左扩，i原地不变。

问题一代码：

package class002;

import java.util.Arrays;

public class Code_Partition {

// 问题一：
// <= num 的数放左边
// > num 的数放右边
public static void partition(int[] arr, int num) {

if (arr == null || arr.length < 2) {
return;
}

// <=区的右边界
int lessEqual = -1;

// 当前检查的位置
int i = 0;

while (i < arr.length) {

if (arr[i] <= num) {

// <=区向右扩大一个位置
// 当前数和<=区的新位置交换
swap(arr, ++lessEqual, i);

}

// 无论当前数 <= num 还是 > num
// i都向右移动
i++;
}
}

public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

public static void main(String[] args) {

int[] arr = {7, 3, 5, 2, 8, 5, 1, 9};

int num = 5;

System.out.println("原数组：");
System.out.println(Arrays.toString(arr));

partition(arr, num);

System.out.println("调整后：");
System.out.println(Arrays.toString(arr));
}
}

运行结果：

原数组：
[7, 3, 5, 2, 8, 5, 1, 9]
调整后：
[3, 5, 2, 5, 1, 7, 8, 9]

问题二代码：

package class002;

import java.util.Arrays;

public class Code_NetherlandsFlag {

// 问题二：
// < num 放左边
// == num 放中间
// > num 放右边
public static void netherlandsFlag(int[] arr, int num) {

if (arr == null || arr.length < 2) {
return;
}

// <区的右边界
int less = -1;

// >区的左边界
int more = arr.length;

// 当前检查位置
int i = 0;

while (i < more) {

// 情况1：当前数 < num
if (arr[i] < num) {

// <区右扩
// 当前数和<区下一个位置交换
swap(arr, ++less, i++);

}

// 情况2：当前数 == num
else if (arr[i] == num) {

// 当前数已经属于==区
// 直接向右移动
i++;

}

// 情况3：当前数 > num
else {

// >区向左扩
// 当前数和>区前一个位置交换
swap(arr, i, –more);

// 注意：
// i不能++
//
// 因为从右边交换过来的数
// 还没有检查过
}
}
}

public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

public static void main(String[] args) {

int[] arr = {7, 3, 5, 2, 8, 5, 1, 9, 5};

int num = 5;

System.out.println("原数组：");
System.out.println(Arrays.toString(arr));

netherlandsFlag(arr, num);

System.out.println("调整后：");
System.out.println(Arrays.toString(arr));
}
}

运行结果：

原数组：
[7, 3, 5, 2, 8, 5, 1, 9, 5]
调整后：
[3, 2, 1, 5, 5, 5, 9, 8, 7]

2.三类快速排序

快速排序1.0版本，最好时间复杂度O(N*logN),最差时间复杂度O(N^2)

快速排序2.0版本（荷兰国旗问题），最好时间复杂度O(N*logN)，时间复杂度O(N^2)

原因：(1)两者每次只能解决一个数的位置问题，不能把位置信息进行传递;(2)划分在中间值附近时，子问题规模相同可以用master公式，划分在偏向两边时，子问题规模不同，不能用这个公式。

快速排序3.0版本（随机抽取一个数进行划分），平均时间复杂度O(N*logN)，证明略（算法导论上有）。

代码：

package class002;

import java.util.Arrays;

public class Code02_QuickSort {

public static int[] sortArray(int[] nums) {
if (nums.length > 1) {
quickSort2(nums, 0, nums.length – 1);
}
return nums;
}

// 随机快速排序经典版(不推荐)
public static void quickSort1(int[] arr, int l, int r) {
if (l >= r) {
return;
}
// 随机这一下，常数时间比较大
// 但只有这一下随机，才能在概率上把快速排序的时间复杂度收敛到O(n * logn)
int x = arr[l + (int) (Math.random() * (r – l + 1))];
int mid = partition1(arr, l, r, x);
quickSort1(arr, l, mid – 1);
quickSort1(arr, mid + 1, r);
}

// 已知arr[l….r]范围上一定有x这个值
// 划分数组 <=x放左边，>x放右边，并且确保划分完成后<=x区域的最后一个数字是x
public static int partition1(int[] arr, int l, int r, int x) {
// a : arr[l….a-1]范围是<=x的区域
// xi : 记录在<=x的区域上任何一个x的位置，哪一个都可以
int a = l, xi = 0;
for (int i = l; i <= r; i++) {
if (arr[i] <= x) {
swap(arr, a, i);
if (arr[a] == x) {
xi = a;
}
a++;
}
}
swap(arr, xi, a – 1);
return a – 1;
}

public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}

// 随机快速排序改进版(推荐)
public static void quickSort2(int[] arr, int l, int r) {
if (l >= r) {
return;
}
// 随机这一下，常数时间比较大
// 但只有这一下随机，才能在概率上把快速排序的时间复杂度收敛到O(n * logn)
int x = arr[l + (int) (Math.random() * (r – l + 1))];
partition2(arr, l, r, x);
// 为了防止底层的递归过程覆盖全局变量
// 这里用临时变量记录first、last
int left = first;
int right = last;
quickSort2(arr, l, left – 1);
quickSort2(arr, right + 1, r);
}

// 荷兰国旗问题
public static int first, last;

// 已知arr[l….r]范围上一定有x这个值
// 划分数组 <x放左边，==x放中间，>x放右边
// 把全局变量first, last，更新成==x区域的左右边界
public static void partition2(int[] arr, int l, int r, int x) {
first = l;
last = r;
int i = l;
while (i <= last) {
if (arr[i] == x) {
i++;
} else if (arr[i] < x) {
swap(arr, first++, i++);
} else {
swap(arr, i, last–);
}
}
}

public static void main(String[] args) {
// 测试 quickSort1（经典版）
System.out.println("=== 测试 quickSort1 ===");
int[] arr1 = {5, 3, 8, 4, 2, 7, 1, 6};
System.out.println("排序前: " + Arrays.toString(arr1));
Code02_QuickSort.quickSort1(arr1, 0, arr1.length – 1);
System.out.println("排序后: " + Arrays.toString(arr1));

// 测试 quickSort2（改进版）
System.out.println("\\n=== 测试 quickSort2 ===");
int[] arr2 = {9, 2, 7, 2, 5, 2, 8, 1};
System.out.println("排序前: " + Arrays.toString(arr2));
Code02_QuickSort.quickSort2(arr2, 0, arr2.length – 1);
System.out.println("排序后: " + Arrays.toString(arr2));
}

}

运行结果：

=== 测试 quickSort1 ===
排序前: [5, 3, 8, 4, 2, 7, 1, 6]
排序后: [1, 2, 3, 4, 5, 6, 7, 8]

=== 测试 quickSort2 ===
排序前: [9, 2, 7, 2, 5, 2, 8, 1]
排序后: [1, 2, 2, 2, 5, 7, 8, 9]

【leetcode】(二)认识O(NlogN)的排序