模板

冒泡排序

![]()![]()```

include <stdio.h>

include <bits/stdc++.h>

using namespace std;

int a[1005];

int main () {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i <= n; i++)
for (int j = 1; j < n - i + 1; j++)
if (a[j] > a[j + 1])
swap(a[j], a[j + 1]);
for (int i = 1; i <= n; i++)
printf("%d ", a[i]);
return 0;
}


Sham_Devour

选择排序

![]()![]()```
#include &lt;stdio.h&gt;
#include &lt;bits/stdc++.h&gt;

using namespace std;

int a[1005];

int main () {
    int n;
    scanf(&quot;%d&quot;, &amp;n);
    for (int i = 1; i &lt;= n; i++)
        scanf(&quot;%d&quot;, &amp;a[i]);
    for (int i = 1; i &lt;= n; i++) {
        int x = i;
        for (int j = i; j &lt;= n; j++)
            if (a[j] &lt; a[x])
                x = j;
        swap(a[x], a[i]);
    }
    for (int i = 1; i &lt;= n; i++)
        printf(&quot;%d &quot;, a[i]);
    return 0;
}

Sham_Devour

插入排序

![]()![]()```

include <stdio.h>

include <bits/stdc++.h>

using namespace std;

int cnt, a[1005];

void insert (int x) {
int k = cnt + 1;
for (int i = 1; i <= cnt; i++)
if (a[i] > x) {
k = i;
break;
}
for (int i = cnt + 1; i > k; i--)
a[i] = a[i - 1];
a[k] = x;
cnt++;
}

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


Sham_Devour

归并排序

![]()![]()```
#include &lt;stdio.h&gt;
#include &lt;bits/stdc++.h&gt;

using namespace std;

int n, a[1005], t[1005];

void mergeSort (int l, int r) {
    if (l == r)
        return;
    int mid = (l + r) / 2;
    mergeSort(l, mid);
    mergeSort(mid + 1, r);
    int p = l, q = mid + 1, i = l;
    while (p &lt;= mid &amp;&amp; q &lt;= r) {
        if (a[p] &lt; a[q])
            t[i++] = a[p++];
        else
            t[i++] = a[q++];
    }
    while (p &lt;= mid)
        t[i++] = a[p++];
    while (q &lt;= r)
        t[i++] = a[q++];
    for (int i = l; i &lt;= r; i++)
        a[i] = t[i];
}

int main () {
    scanf(&quot;%d&quot;, &amp;n);
    for (int i = 1; i &lt;= n; i++)
        scanf(&quot;%d&quot;, &amp;a[i]);
    mergeSort(1, n);
    for (int i = 1; i &lt;= n; i++)
        printf(&quot;%d &quot;, a[i]);
    return 0;
}

Sham_Devour

快速排序

![]()![]()```

include <stdio.h>

include <bits/stdc++.h>

using namespace std;

int n, a[1005], t[1005];

int getRand (int l, int r) {
return rand() % (r - l + 1) + l;
}

void quickSort (int l, int r) {
if (l >= r)
return;
int flag = a[getRand(l, r)];
int p = l, q = r;
for (int i = l; i <= r; i++) {
if (a[i] < flag)
t[p++] = a[i];
if (a[i] > flag)
t[q--] = a[i];
}
for (int i = l; i < p; i++)
a[i] = t[i];
for (int i = r; i > q; i--)
a[i] = t[i];
for (int i = p; i <= q; i++)
a[i] = flag;
quickSort(l, p - 1);
quickSort(q + 1, r);
}

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


Sham_Devour

拓扑排序+记录层级+判断是否为 DAG

![]()![]()```
#include &lt;stdio.h&gt;
#include &lt;bits/stdc++.h&gt;

using namespace std;

int n, m, cnt, num, elast[5005], in[5005], f[5005], ans[5005];

struct edge {
    int to, len, next;
} e[10005];

queue&lt;int&gt; q;

void add (int u, int v, int w) {
    e[++cnt].to = v;
    e[cnt].len = w;
    e[cnt].next = elast[u];
    elast[u] = cnt;
}

bool topsort () {
    for (int i = 1; i &lt;= n; i++)
        if (in[i] == 0) {
            q.push(i);
            f[i] = 1;
            ans[++num] = i;
        }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = elast[u]; i != 0; i = e[i].next) {
            in[e[i].to]--;
            if (in[e[i].to] == 0) {
                q.push(e[i].to);
                f[e[i].to] = f[u] + 1;
                ans[++num] = e[i].to;
            }
        }
    }
    if (num != n)
        return false;
    return true;
}

int main () {
    scanf(&quot;%d %d&quot;, &amp;n, &amp;m);
    for (int i = 1; i &lt;= m; i++) {
        int u, v;
        scanf(&quot;%d %d&quot;, &amp;u, &amp;v);
        add(u, v, 1);
        in[v]++;
    }
    bool flag = topsort();
    if (!flag) {
        puts(&quot;no solution&quot;);
        return 0;
    }
    for (int i = 1; i &lt;= num; i++)
        printf(&quot;%d &quot;, ans[i]);
    puts(&quot;&quot;);
    sort(f + 1, f + 1 + num);
    for (int i = 1; i &lt;= num; i++)
        printf(&quot;%d &quot;, f[i]);
    return 0;
}

Sham_Devour

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。