归并排序
归并排序实质是二叉树的后序遍历。
思想：先将左半边数组排好序，再将右半边数组排好序，将两个排好序的数组合并。
代码实现：
- 提前将数组new出来，避免在递归中频繁的分配和释放内存，影响性能
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| public class Merge {
private static int[] temp;
public static void sort(int[] a){
temp = new int[a.length];
sort(a,0,a.length-1);
}
private static void sort(int a[],int start,int end){
int mid = start + (end - start) / 2;
if(end-start<=0){
return;
}
sort(a, start, mid);
sort(a, mid + 1, end);
merge(a, start, mid, end);
}
private static void merge(int a[],int start,int mid,int end){
for(int i=start;i<=end;i++){
temp[i]=a[i];
}
int low=start;
int high=mid+1;
for (int p=start;p<=end;p++){
if(low==mid+1){
a[p]=temp[high++];
}else if(high==end+1){
a[p]=temp[low++];
}else if(temp[low]<=temp[high]){
a[p]=temp[low++];
}else if(temp[low]>temp[high]){
a[p]=temp[high++];
}
}
}
}
|
如何计算这个算法的复杂度？
递归算法的复杂度计算：子问题个数 x 解决一个子问题的复杂度
应用
第 315 题「 计算右侧小于当前元素的个数」
**对 nums[lo..hi] 合并的过程中，每当执行 nums[p] = temp[i] 时，就可以确定 temp[i] 这个元素后面比它小的元素个数为 j - mid - 1**。
这题还是挺难的
第 493 题「 翻转对」
当 nums[lo..mid] 和 nums[mid+1..hi] 两个子数组完成排序后，对于 nums[lo..mid] 中的每个元素 nums[i]，去 nums[mid+1..hi] 中寻找符合条件的 nums[j] 就行了。
快速排序
快速排序实质是二叉树的先序遍历
思想：先将一个元素排好序，再将剩下的元素排好序
为解决构建的二叉搜索树不平衡的问题
- 在排序之前使用洗牌算法将整个数组打乱
- 在partition函数中随机选择一个数作为分界点
洗牌算法
分析洗牌算法正不正确：一个长度为n的数组，产生的结果必须是n!种可能。【每种可能结果出现的概率必须相等】
如果不用数学严格证明概率相等，可以用蒙特卡罗方法地估计出概率是否相等，结果是否足够随机。
记得高中有道数学题：往一个正方形里面随机打点，这个正方形里紧贴着一个圆，告诉你打点的总数和落在圆里的点的数量，让你计算圆周率
这其实就是利用了蒙特卡罗方法：当打的点足够多的时候，点的数量就可以近似代表图形的面积。通过面积公式，由正方形和圆的面积比值是可以很容易推出圆周率的
类似的，我们可以对同一个数组进行一百万次洗牌，统计各种结果出现的次数，把频率作为概率，可以很容易看出洗牌算法是否正确。
快速排序的代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| public class QuickSort {
public static void main(String[] args) {
int nums[] = {4, 6, 3, 7, 1, 8};
shuffle(nums);
sort(nums,0,nums.length-1);
System.out.println(Arrays.toString(nums));
}
public static void sort(int nums[],int lo,int hi){
while(lo>=hi){
return;
}
int p= partition(nums,lo,hi);
sort(nums,lo,p-1);
sort(nums, p + 1, hi);
}
public static int partition(int nums[],int lo,int hi){
int pivot=nums[lo];
int i =lo+1; int j= hi;
while(i<=j){
while(i<hi && nums[i]<=pivot){
i++;
}
while(j>lo && nums[j]>pivot){
j--;
}
if(i>=j){
break;
}
swap(nums,i,j);
}
swap(nums,lo,j);
return j;
}
public static void swap(int nums[],int i,int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public static void shuffle(int nums[]){
Random rand = new Random();
int n = nums.length;
for (int i=0;i<n;i++){
int ind=i+rand.nextInt(n-i);
swap(nums, i, ind);
}
}
}
|
变体-快速选择算法
215. 数组中的第K个最大元素
方法1：二叉堆（优先队列）
1
2
3
4
5
6
7
8
9
10
| public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> queue= new PriorityQueue<Integer>((o1,o2)-> o2-o1);
for(int i=0;i<nums.length;i++){
queue.add(nums[i]);
}
for(int i=0;i<k-1;i++){
queue.poll();
}
return queue.poll();
}
|
时间复杂度：O(nlogk）
方法2:快速选择算法
求排名第k的元素
partition 函数会将 nums[p] 排到正确的位置，使得 nums[lo..p-1] < nums[p] < nums[p+1..hi]
此时nums[p]的排名就知道了为p， 将p和k比较，如果p>k,说明结果在nums[lo..p-1];如果p<k,说明结果在nums[p+1..hi]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| class Solution {
public int findKthLargest(int[] nums, int k) {
int n= nums.length;
int rank = n-k;
int lo=0;
int hi=n-1;
while(lo<=hi){
int p=partition(nums,lo,hi);
if(p==rank){
return nums[p];
}else if(p<rank){
lo=p+1;
}else if(p>rank){
hi=p-1;
}
}
return -1;
}
public int partition(int nums[],int lo,int hi){
int pivot=nums[lo];
int i=lo+1;
int j=hi;
while(i<=j){
while(i<hi && nums[i]<=pivot){
i++;
}
while(j>lo && nums[j]>pivot){
j--;
}
if(i>=j){
break;
}
swap(nums,i,j);
}
swap(nums,j,lo);
return j;
}
public void shuffle(int nums[]){
Random rand = new Random();
int n=nums.length;
for(int i=0;i<n;i++){
int ind=i+rand.nextInt(n-i);
swap(nums,i,ind);
}
}
public void swap(int nums[],int i,int j){
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
}
|
