历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

排序——为你排忧解难

作者：

cht , 2020-04-19 20:47:51 , 所有人可见 , 阅读 1151

8

3

排序

大家好，cht又来唠叨算法了

今天我们说说

排序！

咳咳，我们先说说最简单的三种排序:

快速排序

归并排序

冒泡排序

cht在这里提示大家,模板不能死记硬背哦

1、冒泡排序

作为如此老套的算法，大家应该并不陌生

冒泡排序的思路是什么呢？就是把数列中所有不成顺序的数交换。

（其实就是暴力算法）

时间复杂度 O(n²)

没有听懂的同学们再来看看图吧。

批注 2020-04-18 181555.png

注意！这里的排序是倒向的（a > b > c）。

接下来给大家看看动态图

现在大家应该都明白什么是冒泡排序了吧。

接下来我们来看看c++代码（我的代码和动态图不同）

#include<iostream>
#include<algorithm>//swap函数

using namespace std;

const int N = 100010;//...+10!!!

int n;//需要排列的数的个数
int q[N];//排序数组

int main()
{
    scanf("%d",&n);//提速，最好用scanf
    for(int i = 0; i < n; i ++) scanf("%d",&q[i]);
    //模板区（自己搞的，有错误请多多指正）
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n && j != i; j ++)//双指针算法
            if(q[i] < q[j])
                swap(q[i],q[j]);
    for(int i = 0; i < n; i ++) printf("%d ",q[i]);
    printf("\n");
    return 0;
}

2、快速排序

算法基础课标准算法

（详细请见算法基础课——快速排序）

快排的思想就是分治

通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

请看图：

批注 2020-04-18 204000.png

请看动态图

接下来说说流程

1、x = q[l + r >> 1],i = l - 1,j = r + 1;

2、分治（小于x的放到左边，大于x的放到右边）。

3、分别递归左右两边。

请看c++代码：

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;//......+10

int n;//需要排序的数的数量
int q[N];//需要排序的数组

void qs(int q[],int l,int r)//函数（模板）
{
    if(l >= r) return;

    int x = q[l + r >> 1], i = l - 1,j = r + 1;//见步骤1
    while(i < j)
    {
        do i ++;while(q[i] < x);//指针i指向的数要小于x
        do j --;while(q[j] > x);//指针j指向的数要大于x
        if(i < j) swap(q[i],q[j]);//不符合条件就交换
    }

    qs(q, l, j);
    qs(q, j + 1, r);//分别递归左右两边
}

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

3、归并排序

算法基础课标准算法

（详细请见算法基础课——快速排序）

此算法的思想与快排一样：分治

请看图解：

批注 2020-04-18 205844.png

请看动图：

接下来说说算法步骤

1、分别递归左右两边

2、归并（双指针）

3、把tmp数组的数放进q数组

请看c++代码

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1000010;

int n;
int a[N];
int tmp[N];//存答案的tmp数组

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

    int mid = l + r >> 1;
    ms(q, l, mid);
    ms(q, mid + 1, r);//分别递归左右两边

    int k = 0;//tmp的第几项
    int i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];//i小，把i放进tmp
        else tmp[k ++ ] = q[j ++ ];//j小，把j放进tmp
    while (i <= mid) tmp[k ++ ] = q[i ++ ];//把i指针剩下的放进tmp
    while (j <= r) tmp[k ++ ] = q[j ++ ];//把j指针剩下的放进tmp

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];//把tmp数组里的数放进q数组
}

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

到这里，我们最简单的三个排序也就说完了，然后给大家看看推荐学完这三个排序学的知识。

1、计数排序

这个排序是用一个tmp数组来存需要排序的数组中每个数的数量。

请看下图：

批注 2020-04-19 173925.png

请看动图：

排序步骤：

1、建立tmp数组

2、计数

3、把计数的结果放回q数组

请看代码（这里非常感谢FfFJ给我指出错误）：

#include<iostream>

using namespace std;

const int N = 100010;

int n;
int q[N];
int res[N];//tmp数组（我这里写的res）

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++) cin >>q[i];

    int tmp = 0;//最大值
    for(int i = 0; i < n; i ++)
    {
        if (q[i] >= tmp) tmp = q[i];
    }

    int k = 0;
    for(int i = 0; i <= tmp; i ++)
    {
        for(int j = 0; j < n; j ++)
        {
            if(q[j] == k)
            {
                res[i] ++;//计数
            }
        }
        k ++;
    }

    int s = 0;
    k = 0;
    for(int i = 0; i < n; i ++)
    {
        for(int j = 1; j <= res[i]; j ++)
        {
            q[s ++] = k;//把结果放回q数组
        }
        k ++;
    }

    for(int i = 0; i < n; i ++) cout << q[i] << " ";
    cout << endl;
    return 0;
}

巨佬“墨染空”的代码：

#include<iostream>

using namespace std;

const int N = 100010;

int n, q[N], cnt[N], mx;

int main() {
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> q[i], cnt[q[i]]++, mx = max(mx, q[i]);
    for (int i = 1; i <= mx; i++) 
        for (int j = 1; j <= cnt[i]; j++) printf("%d ", i);
    return 0;
}

2、选择排序

选择排序通过每次选择数列中最小的数放在数列最前端实现排序

请看图：

批注 2020-04-19 203752.png

请看动图：

说一说模板思路：

首先，算出最大值s（为最小值做准备，一会看了代码大家就明白了）。

第二步，写：for(int i = 1; i < n; i ++)

第三步，在循环里算出最小值以及最小值下标（k,p）。

第四步，将未排序部分的第一项（q[i-1]）和最小值（q[p]）交换。

请看代码：

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;

int n;
int q[N];
int k;//存最小值
int s = 0;//存最大值

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

    for(int i = 0; i < n; i ++)
    {
        if(q[i] > s) s = q[i];//求最大值（第一步）
    }
    k = s;

    int p = 0;//存最小值下标
    for(int i = 1;i < n;i ++)//第二步
    {
        int j = i - 1;
        while(j < n - 1)
        {
            if(q[j] < k)
            {
                k = q[j];
                p = j;//最大值与它的下标（第三步）
            }
            j ++;
        }
        if(q[i - 1] != p)swap(q[i - 1], q[p]);//交换（第四步）
        p = 0,k = s;
    }

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