排序

排序顾名思义，我们可以通过排序对数组进行有序化排列，进一步实现更多排序后的功能

排序中最常用的两种方式分别为

• 快速排序
• 归并排序

快速排序

快速排序主要使用的算法为分治，将一串数据分而治之，最终变成一小段数据进行处理

这里我们主要使用双指针的思想实现

最终实现的目的

在排序的过程中，我们需要定义一个标准值x，将小于x的放在头指针的左边，大于x的放在尾指针的右边

比较过程分析

首先定义一个x，作为比较的条件

我们定义一个头指针，初始位置为l，尾指针，初始位置为r，我们去判断arr[l] < x如果成立让 l不停的递增，如果突然不成立了，我们接着判断arr[r] > x，同理如果不成立了，我们需要判断指针是否交叉，如果没有的话，将arr[l]和arr[r]进行交换操作，最终l >= r return返回

#include <iostream>

using namespace std;

const int N = 100010;

int q[N];

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1,j = r + 1,x = q[l + r >> 1];
    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);
    quick_sort(q, j + 1, r);
}

int main()
{
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

    quick_sort(q, 0, n - 1);

    for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);

    return 0;
}

归并排序

什么是归并排序？

归并排序主要是将数组不停的均等的切割成左右两部分，我们从最底层进行排序，这样就能保证上面的每一层都是有序的两个数组

思想

首先我们需要获取mid值，然后对数组进行切割

mid = l + r >> 1;
merge_sort(q,1,mid),merge_sort(q,mid + 1,r);

由于切割后的两个数组是有序的(为什么有序，因为我们不停的切割最终到最后一层，后面保证有序前面即有序)，我们可以定义两个指针分别指向两个数组的头结点，然后比较，如果谁小，将其放入到新数组中，放入到元素所在的数组头指针向后移动

注意

每一次我们都是对l 到 r之间的所有数字进行排序，我们最后也需要将新数组上的值返还给初始数组的l 到 r之间

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int q[N],t[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]) t[k++] = q[i++];
        else t[k++] = q[j++];
    }

    while(i <= mid) t[k++] = q[i++];
    while(j <= r) t[k++] = q[j++];

    for(int i = 0,j = l;j <= r;i++,j++) {
        q[j] = t[i];
    }

}


int main(){
    int n;
    cin >> n;

    for(int i = 1;i <= n;i++) scanf("%d",&q[i]);

    merge_sort(q,1,n);

    for(int i = 1;i <= n;i++) printf("%d ",q[i]);
    return 0;
}