浅浅记录一下，学的快排与归并与二分。视频地址：第一章 基础算法（一） - AcWing

快速排序

听名字就知道是很快的算法，听了y总深入浅出的解释，我对于快速排序的理解进一步加深了。在大一上的计导课里，有一个实验就是让我们用人体计算机的方式实现快排。当时，不记得是王老师还是助教说只能使用单指针的快排，然后我琢磨乐好久也没搞明白该怎么排，后面半推半就做完了那个实验。之后，快排就忘得一干二净了哈哈哈哈。现在听了y总的课，我总结出了以下几个要点，记住这几个要点，可以更容易背住模板。

  1. 当递归到最底层，只有一个元素的时候，是不用排序的，所以此时直接return即可，这也是递归的出口，判断条件就是左边界是否大于右边界。
  2. 选取一个分界的数，可以选数组里任何一个数，第一，最后，中间都可以，看情况
  3. 选取左右指针时，要选在两个指针的外边；左指针就在左边界减一处；右指针在有边界加一处。
  4. 对于一次快排，原理就是使所有比 X（选定的数）小的数在X左边；所有比X大的数在X的右边，所以套一层while循环，判断条件是两指针是否相遇。
  5. 然后两个指针开始移动，左指针往右移动，遇到第一个比X大的数停下；右指针同理。
  6. 两个指针停下后，如果没相遇，就交换两个数。
  7. 然后分成两个区间，再递归使用快排。

快排模板

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
#include <iostream>
using namespace std;
const int N = 1e6+10;
int q[N];
int n; 

void quick_sort(int q[],int l,int r){
	if (l >= r) return ;	//递归出口
    
	int i = l - 1;		//左右指针
	int j = r + 1;
	int x = q[l + r >> 1]; //位运算，比直接除以2更快，相当于除以2的一次方
    
	while (i < j){
		do i++;while (q[i] < x);
		do j--;while (q[j] > x);
		if (i < j) swap(q[i],q[j]);
	}
    
	quick_sort(q,l,j);	//这里也可使用i做分界，不过参数会发生变化
	quick_sort(q,j+1,r); 
}





int main(){
	scanf("%d",&n);
	for (int i = 0;i < n;i++) scanf("%d",&q[i]);	//scanf比cin更快
	
	quick_sort(q,0,n - 1);
	
	for (int i = 0;i < n;i++) printf("%d ",q[i]);
	return 0;
}

归并排序

这是我见过比较神奇的一种排序。和快排一样，归并排序核心思想也是分治，但是和快排不同，归并是从底层开始，其有一个明显的特征，就是会出现左右两组数的比较，这也是归并的一个很明显的特征，可以用在很多地方。另外归并排序算是递归这一结构神奇之处的一个非常好的体现，即你可以实现它，但你不一定能理解它，它符合逻辑，但是你不一定能理解为什么。

放张图好理解归并排序

154035112_1_20190212015806351

其核心逻辑就是先把数组一分为二，用归并排序排序好。此时得到两个有序数组，再新建一个临时数组，把两个数组中的元素一个一个按大小插入，合并成一个有序数组。可以看到核心逻辑是非常的简单了。代码模板有几个需要注意的点：

  1. 当递归到最底层，只有一个元素的时候，是不用排序的，所以此时直接return即可，这也是递归的出口，判断条件就是左边界是否大于右边界。
  2. 然后去一个中间值把数组分成两部分后直接用归并排序进行排序
  3. 接下来就是合并两个有序数组，这里需要用到三个指针分别指向两个有序数组和临时数组的开头。
  4. 然后就是三个while把两个数组拼起来的过程。
  5. 最后用一个for循环把排好序的临时数组放回原数组，结束

代码模板

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
#include <iostream>
using namespace std;

const int N = 1e+6;
int q[N],temp[N];
int n;

void merge_sort(int q[],int l, int r ){
    if (l >= r) return ;
    int mid = l + r >> 1;	//将数组一分为二
    
    
    merge_sort(q,l,mid),merge_sort(q,mid+1,r);	//用归并排序将两部分数组给排好序
    
    int k = 0, i = l , j = mid + 1;		//进行一个数组的合并
    while (i <= mid && j <= r){
        if ( q[i] < q[j] ) temp[k++] = q[i++];
        else temp[k++] = q[j++];
    }
    while (i <= mid) temp[k++] = q[i++];	//将没合并完的后半部分直接接上去
    while (j <= r) temp[k++] = q[j++];
    
    for (i = l,j = 0;i<=r;i++,j++) q[i] = temp[j];	//赋值给原数组
    
}

int main(){
    scanf("%d",&n);
	for (int i = 0;i < n;i++) scanf("%d",&q[i]);
	
	merge_sort(q,0,n - 1);
	
	for (int i = 0;i < n;i++) printf("%d ",q[i]);
    return 0;
}