O(NlogN)的排序
归并排序
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
| void mergeSort(int arr[],int n){
sort(arr,0,n-1);
}
void sort(int arr[],int l,int r){
if(l==r) return;
int mid=l+((r-l)>>1);
sort(arr,l,mid);
sort(arr,mid+1,r);
merge(arr,l,mid,r);
}
void merge(int arr[],int left,int mid,int right){
int p1=left,p2=mid+1,current=0;
int result[right-left+1];
while(p1<=mid&&p2<=right){
if(arr[p1]<=arr[p2]){
result[current++]=arr[p1++];
}
else{
result[current++]=arr[p2++];
}
}
while(p1<=mid) result[current++]=arr[p1++];
while(p2<=right) result[current++]=arr[p2++];
for(int i=0;i<right-left+1;i++){
arr[left+i]=result[i];
}
}
|
时间复杂度O(NlogN)
时间复杂度比插入选择排序小，因为原来的比较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
| int merge(int arr[],int left,int mid,int right){
int p1=left,p2=mid+1,current=0,sum=0;
int result[right-left+1];
while(p1<=mid&&p2<=right){
if(arr[p1]<arr[p2]){
sum=sum+arr[p1]*(right-p2+1);
result[current++]=arr[p1++];
}
else if(arr[p1]>arr[p2]){
result[current++]=arr[p2++];
}
else result[current++]=arr[p2++];
}
while(p1<=mid) result[current++]=arr[p1++];
while(p2<=right) result[current++]=arr[p2++];
for(int i=0;i<right-left+1;i++){
arr[left+i]=result[i];
}
return sum;
}
int SmallSum(int arr[],int l,int r){
if(l==r) return 0;
int mid=l+((r-l)>>1);
return SmallSum(arr,l,mid)+SmallSum(arr,mid+1,r)+merge(arr,l,mid,r);
}
int getSmallSum(int arr[],int n){
return SmallSum(arr,0,n-1);
}
|
逆序对问题
在一个数组中，左边的数如果比右边的数大，则折两个数构成一个逆序对，请输出逆序对的个数。
LCR 170. 交易逆序对的总数
在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。
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
| int mergeReverse(vector<int>& record,int left,int mid,int right){
int p1=left,p2=mid+1,p=0,result=0;
int help[right-left+1];
while(p1<=mid&&p2<=right){
if(record[p1]>record[p2]){
result=result+(right-p2+1);
help[p]=record[p1];
p++;
p1++;
}
else{
help[p]=record[p2];
p++;
p2++;
}
}
while(p1<=mid){
help[p]=record[p1];
p++;
p1++;
}
while(p2<=right){
help[p]=record[p2];
p++;
p2++;
}
for(int i=0;i<=right-left;i++){
record[left+i]=help[i];
}
return result;
}
int getReverse(vector<int>& record,int left,int right){
if(left==right) return 0;
int mid=left+((right-left)>>1);
return getReverse(record,left,mid)+getReverse(record,mid+1,right)+mergeReverse(record,left,mid,right);
}
int reversePairs(vector<int>& record) {
if(record.size()==0) return 0;
return getReverse(record,0,record.size()-1);
}
|
快排
快排1.0
小于等于num + 大于num
时间复杂度：O(N^2)，原因：划分值num打的很偏，导致只有一侧
快排2.0
小于num + 等于num + 大于num
时间复杂度：O(N^2)，原因：划分值num打的很偏，导致只有一侧
快排3.0
随机选择一个数与最后一位数做交换，再作为划分值——>好情况和坏情况是概率事件，每种情况只占1/N，求每种情况时间复杂度的数学期望
时间复杂度：O(NlogN)
空间复杂度：O(logN) 最差是O(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
|
vector<int> partition(int arr[],int l,int r){
int low=l-1;
int high=r;
int i=l;
while(i<high){
if(arr[i]<arr[r]){
swap(arr,i,low+1);
low++;
i++;
}
else if(arr[i]==arr[r]){
i++;
}
else{
swap(arr,i,high-1);
high--;
}
}
swap(arr,high,r);
return {low+1,high};
}
void quickSort(int arr[],int l,int r){
if(l<r){
srand(time(0));
int idx=(rand()%(r-l+1))+l;
swap(arr,idx,r);
vector<int> p=partition(arr,l,r);
quickSort(arr,l,p[0]-1);
quickSort(arr,p[1]+1,r);
}
}
|
扩展
荷兰旗问题
75. 颜色分类
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，**原地**对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
堆排
堆
完全二叉树：从上到下从左到右依次排满的过程
数据结构：从0开始的连续数组
父节点：(i-1)/2
左节点：2i+1，右节点：2i+2
大根堆/小根堆：根节点最大/最小
Q：插入一个数
1
2
3
4
5
6
7
8
|
void heapInsert(int arr[],int idx){
while(arr[idx]>arr[(idx-1)/2]){
swap(arr,idx,(idx-1)/2);
idx=(idx-1)/2;
}
}
|
Q：去掉最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
void heapify(int arr[],int idx,int heapsize){
int max;
while(2*idx+1<heapsize){
max=2*idx+1;
if(2*idx+2<heapsize&&arr[max]<arr[2*idx+2]){
max=2*idx+2;
}
if(arr[max]<arr[idx]) break;
swap(arr,idx,max);
idx=max;
}
}
|
堆排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| void heapSort(int arr[],int n){
for(int i=0;i<n;i++){
heapInsert(arr,i);
}
int heapSize=n;
swap(arr,0,heapSize-1);
heapSize--;
while(heapSize>0){
heapify(arr,0,heapSize);
swap(arr,0,--heapSize);
}
}
|
时间复杂度O(NlogN)
空间复杂度O(1)
1
2
3
4
|
for(int i=n-1;i>=0;i--){
heapify(nums,i,n);
}
|
桶排序
计数排序
Q：员工年龄排序（0~200）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
void countSort(int arr[],int n){
int num[200]={0};
for(int i=0;i<n;i++){
num[arr[i]]++;
}
for(int i=0;i<200;i++){
while(num[i]>0){
cout<<i<<" ";
num[i]--;
}
}
}
in
|
局限性：不基于比较的排序，取决于数据状态，比如说年龄范围0~200，准备num[200]，所以得知道数范围
基数排序/桶排序
Eg：[17,13,25,100,72]
补全[017,013,025,100,072]
准备十个桶，几进制就几个桶
按个位进桶
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
| 100 |
|
072 |
013 |
|
025 |
|
017 |
|
|
先进先出，按个位出桶[100,072,013,025,017]
按十位进桶
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
| 100 |
013
017 |
025 |
|
|
|
|
072 |
|
|
先进先出，按十位出桶[100,013,017,025,072]
按百位进桶
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
013
017
025
072 |
100 |
|
|
|
|
|
|
|
|
先进先出，按百位出桶[013,017,025,072,100]