【算法系列01】:快速排序&&归并排序

2021年05月13日 23:45 __ _ _ _ _

你需要知道，人的事业就如同浪潮，如果你踩到浪头，功名随之而来；而一旦错失，则终其一生都将受困于浅滩与悲哀。

——《洛克菲勒写给儿子的38封信》

大家好哇，这里是小编记录算法模板的宝地啦，其中也会包含小编平时学习的一些心得。现在，让我们一起进入算法的世界吧~

1.快速排序

快速排序 是在冒泡排序基础上的改进，其基本思想是 基于分治 。
在写代码之前最好是找到自己要写代码的大致步骤：

找分界点：可以是数据的两端或中间，当然随机值也可。
调整区间：使得一个区间的数据小于一个值，另一个区间的值大于一个值。
递归处理：分别对两个区间进行递归处理。

To:在找分界点时，当数据加强后最好是不要选择两边端点的值，之前小编便遇到过内存过载的ERROR。
按照教材上说的，我们在进行快排时会使用两个数组，用于存放两个区间的值，存放之前还会对之前的数据进行扫描，对于时间复杂度和空间复杂度都是不小的开销。

y总提供了一种优美的解决方案，即 用两个指针分别指向数据集的两端i、j，再取其分界点x。
大致思路
是i和j分别向中间走，其中当i大于x时便停下来，j小于x时也是【假设从小到大排序】。然后当i和j两个指针都停下来，便交换两边的值。最后当两个指针相遇时，便确保了一个区间的值是小于x的，另一个区间的值大于x的。
快速排序例子： 输入格式输入共两行，第一行包含整数 n。第二行包含 n 个整数（所有整数均在 1∼10的9次方范围内），表示整个数列。** 输出格式
输出共一行，包含 n个整数，表示排好序的数列。 数据范围 1≤n≤100000 输入样例： 5 3 1 2 4 5 输出样例： 1 2 3 4 5 源代码： **

#include <iostream>
const int N=1e6+10;int a[N];
void Sorttest(int l,int r){     if(l>=r){         return ;     }     //判断数据集     int i=l-1,j=r+1;     int x=a[(l+r)/2];     //取中间值     while(i<j){         do i++;while(a[i]<x);         do j--; while(a[j]>x);         if(i<j){             std::swap(a[i],a[j]);             //交换数据         }     }         Sorttest(l,j);Sorttest(j+1,r);         //分别处理两个区间的数据}int main(){using namespace std;    int n,i;    cin>>n;    //输入排序数据集    for(i=0;i<n;i++){        scanf("%d",&a[i]);    }//Sorttest函数进行排序    Sorttest(0,n-1);//使用循环输出排序后的数据    for(i=0;i<n;i++){        printf("%d ",a[i]);    }return 0;}

快速排序模板：

void Sorttest(int l,int r){     if(l>=r){         return ;     }     int i=l-1,j=r+1;     int x=a[(l+r)/2];     while(i<j){         do i++;while(a[i]<x);         do j--; while(a[j]>x);         if(i<j){             std::swap(a[i],a[j]);         }     }         Sorttest(l,j);Sorttest(j+1,r);}

To：可能会有人问为啥会有模板，在处理大部分排序时，模板都能起到很大的作用，平时可以多敲敲模板，关于临界值的处理则需要自己去记忆了。

2.归并排序

归并排序是一种稳定的排序，而快速排序则是一种不稳定的，归并排序也基于分治。

To：原序列中2个数相同，位置不发生变化我们便说这个排序是稳定的；反之则是不稳定的。

大致思路步骤为：

确定分界点，即mid=(l+r)/2。
递归排序左边和右边。
归并：合二为一，将排序后的数据合并，也是归并排序中最重要的一个环节。

在归并排序中，我们也用到 两个指针
，分别指向排好序数据的最左端，并开始比较，值小的就拿出来【以从小到大排序】放入另一个数组中，依次比较，如果遇到相等的数，我们倾向于将第一个序列的值先放入另一个数组中；如果当第一个指针指向序列的最后一个值时，我们便把另一个序列直接补到数组后面。

归并排序例子：
输入格式输入共两行，第一行包含整数 n。第二行包含 n 个整数（所有整数均在 1∼10的9次方范围内），表示整个数列。** 输出格式
输出共一行，包含 n个整数，表示排好序的数列。 数据范围 1≤n≤100000 输入样例： 5 3 1 2 4 5 输出样例： 1 2 3 4 5 源代码： **

#include<iostream>using namespace std;
const int N = 1000010;int a[N], temp[N], n;
void Sorttest(int a[], int l, int r) {    if (l >= r) {        return;    }//判断数据集    int mid = l + r >> 1;//取中间值    Sorttest(a, l, mid);    Sorttest(a, mid + 1, r);//递归左右两边    int k = 0, i = l, j = mid + 1;    while (i <= mid && j <= r)        if (a[i] <= a[j]) {            temp[k++] = a[i++];        } else {            temp[k++] = a[j++];        }//排序：比较大小，将较小的数据放入temp数组中    while (i <= mid) temp[k++] = a[i++];    while (j <= r) temp[k++] = a[j++];//判断某一个序列是否未放入temp数组中，并将其放入    for (i = l, j = 0; i <= r; i++, j++) {        a[i] = temp[j];    }}
int main() {    scanf("%d", &n);    for (int i = 0; i < n; i++) {        scanf("%d", &a[i]);    }
    Sorttest(a, 0, n - 1);
    for (int i = 0; i < n; i++) {        printf("%d ", a[i]);    }    return 0;}

归并排序模板：

void Sorttest(int a[], int l, int r) {    if (l >= r) {        return;    }
    int mid = l + r >> 1;
    Sorttest(a, l, mid);    Sorttest(a, mid + 1, r);
    int k = 0, i = l, j = mid + 1;    while (i <= mid && j <= r)        if (a[i] <= a[j]) {            temp[k++] = a[i++];        } else {            temp[k++] = a[j++];        }    while (i <= mid) temp[k++] = a[i++];    while (j <= r) temp[k++] = a[j++];    for (i = l, j = 0; i <= r; i++, j++) {        a[i] = temp[j];    }}

平时也可多敲敲模板哦！