排序算法

Cealivanus Kwan Lv3
  2024-11-06 21:06:37 2024-11-06 21:06:37 创建   2024-12-19 21:32:49 2024-12-19 21:32:49 更新      

插入排序

简单插入排序 InsertSort
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
37
38
39
40
41
#include <bits/stdc++.h>
#define fast                          \
    std::ios::sync_with_stdio(false); \
    std::cin.tie(nullptr);
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int a[N];

void InsertSort(int a[],int n)
{
    int i,j;
    for(int i=2;i<=n;i++)
    {
        a[0]=a[i];
        j=i-1;
        while(a[0]<a[j])
        {
            a[j+1]=a[j];
            j--;
        }
        a[j+1]=a[0];
    }
}

int main()
{
    fast;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    InsertSort(a,n);
    for(int i=1;i<=n;i++)
    {
        cout<<a[i]<<' ';
    }
    return 0;
}
二分（折半）插入排序 BinaryInsertSort
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
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
#define fast                          \
    std::ios::sync_with_stdio(false); \
    std::cin.tie(nullptr);
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int a[N];

//折半插入排序
void BinaryInsertSort(int a[],int n)
{
    int l,r,mid;
    for(int i=2;i<=n;i++)
    {
        a[0]=a[i];
        l=1,r=i-1;
        while(l<=r)
        {
            mid=(l+r)>>1;
            if(a[0]<a[mid]) r=mid-1;
            else l=mid+1;
        }
        for(int j=i-1;j>=l;j--)
        {
            a[j+1]=a[j];
        }
        a[l]=a[0];
    }
}

int main()
{
    fast;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    BinaryInsertSort(a, n);
    for (int i = 1; i <= n; i++)
    {
        cout << a[i] << ' ';
    }
    return 0;
}
希尔排序 ShellSort
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
#define fast                          \
    std::ios::sync_with_stdio(false); \
    std::cin.tie(nullptr);
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int a[N], tmp[N];
//希尔排序
void ShellSort(int n, int num)
{
    int i, j, k, gap;
    for (int m = 0; m < num; m++)
    {
        gap = tmp[m];
        for (k = 1; k <= gap; k++)
        {
            for (i = k + gap; i <= n; i += gap)
            {
                a[0] = a[i];
                j = i;
                while (j - gap > 0 && a[j - gap] > a[0])
                {
                    a[j] = a[j - gap];
                    j -= gap;
                }
                a[j] = a[0];
            }
        }
    }
}

int main()
{
    fast;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }

    // 初始化增量序列
    int num = 0;
    for (int gap = 1; gap <= n / 3; gap = 3 * gap + 1)
    {
        tmp[num++] = gap;
    }

    ShellSort(n, num);

    for (int i = 1; i <= n; i++)
    {
        cout << a[i] << ' ';
    }
    return 0;
}

选择排序

简单选择排序 SelectSort
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
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
#define fast                          \
    std::ios::sync_with_stdio(false); \
    std::cin.tie(nullptr);
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int a[N];

//简单选择排序
void SelectSort(int a[],int n)
{
    int i,j,k,tmp;
    for(i=1;i<=n-1;i++)
    {
        k=i;
        for(j=i+1;j<=n;j++)
        {
            if(a[j]<a[k])
            {
                k=j;
            }
        }
        if(k!=i){
            int tmp=a[i];
            a[i]=a[k];
            a[k]=tmp;
        }
    }
}

int main()
{
    fast;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }

    SelectSort(a,n);

    for (int i = 1; i <= n; i++)
    {
        cout << a[i] << ' ';
    }
    return 0;
}
冒泡排序 BubbleSort
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
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
#define fast                          \
    std::ios::sync_with_stdio(false); \
    std::cin.tie(nullptr);
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int a[N];

void BubbleSort(int a[],int n)
{
    int i,j,flg;
    int tmp;
    flg=1;
    i=1;
    while(i<=n&&flg)
    {
        flg=0;
        for(j=n;j>=i;j--)
        {
            if(a[j]<a[j-1])
            {
                flg=1;
                tmp=a[j];
                a[j]=a[j-1];
                a[j-1]=tmp;
            }
        }
        i++;
    }
}

int main()
{
    fast;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    BubbleSort(a, n);
    for (int i = 1; i <= n; i++)
    {
        cout << a[i] << ' ';
    }
    return 0;
}
快速排序 QuickSort
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
#define fast                          \
    std::ios::sync_with_stdio(false); \
    std::cin.tie(nullptr);
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int a[N];

//快速排序
int QuickPass(int a[],int l,int r)
{
    int i=l,j=r;
    a[0]=a[i];
    while(i!=j)
    {
        while(a[j]>=a[0]&&i<j)
            j--;
        if(i<j)
        {
            a[i]=a[j];
            i++;
        }
        while(a[i]<=a[0]&&i<j)
        {
            i++;
        }
        if(i<j)
        {
            a[j]=a[i];
            j--;
        }
    }
    a[i]=a[0];
    return i;
}

void QuickSort(int a[],int s,int t)
{
    int i;
    if(s<t){
        i=QuickPass(a,s,t);
        QuickSort(a,s,i-1);
        QuickSort(a,i+1,t);
    }
}

int main()
{
    fast;
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    QuickSort(a, 1,n);
    for (int i = 1; i <= n; i++) cout << a[i] << ' ';
    return 0;
}

其他排序

堆排序 HeapSort
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
#define fast                          \
    std::ios::sync_with_stdio(false); \
    std::cin.tie(nullptr);
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int a[N];

// 堆排序
// 调整l到r至大根堆
void HeapAdjust(int a[], int l, int r)
{
    int i, j, tmp;
    i = l;
    j = 2 * i;
    tmp = a[i];
    for (; j <= r; j *= 2)
    {
        if (j < r && a[j] < a[j + 1])
        {
            j++;
        }
        if (tmp >= a[j])
            break;
        else
        {
            a[i] = a[j];
            i = j;
        }
    }
    a[i] = tmp;
}

// 创建大根堆
void HeapCreate(int a[], int n)
{
    int i;
    for (i = n / 2; i > 0; i--)
    {
        HeapAdjust(a, i, n);
    }
}

// 堆排序——升序排序
void HeapSort(int a[], int n)
{
    int i, tmp;
    HeapCreate(a, n);
    for (int i = n; i > 1; i--)
    {
        tmp = a[1];
        a[1] = a[i];
        a[i] = tmp;
        HeapAdjust(a, 1, i - 1);
    }
}

int main()
{
    fast;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }

    HeapSort(a, n);

    for (int i = 1; i <= n; i++)
    {
        cout << a[i] << ' ';
    }
    return 0;
}
归并排序 MergeSort
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
#define fast                          \
    std::ios::sync_with_stdio(false); \
    std::cin.tie(nullptr);
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int a[N], tmp[N];

//归并排序
//合并两个有序表
void Merge(int *a, int *tmp, int l, int mid, int r)
{
    int i = l, j = mid + 1, k = l;
    while (i != mid + 1 && j != r + 1)
    {
        if (a[i] > a[j])
        {
            tmp[k++] = a[j++];
        }
        else
        {
            tmp[k++] = a[i++];
        }
    }
    while (i != mid + 1)
    {
        tmp[k++] = a[i++];
    }
    while (j != r + 1)
    {
        tmp[k++] = a[j++];
    }
    for (i = l; i <= r; i++)
    {
        a[i] = tmp[i];
    }
}

//归并排序
void MergeSort(int *a, int *tmp, int l, int r)
{
    if (l < r)
    {
        int mid = l + (r - l) / 2;
        MergeSort(a, tmp, l, mid);
        MergeSort(a, tmp, mid + 1, r);
        Merge(a, tmp, l, mid, r);
    }
}

int main()
{
    fast;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }

    MergeSort(a,tmp,1,n);

    for (int i = 1; i <= n; i++)
    {
        cout << a[i] << ' ';
    }
    return 0;
}

此外，还有基数排序等等……

  • 标题: 排序算法
  • 作者: Cealivanus Kwan
  • 创建于 : 2024-11-06 21:06:37
  • 更新于 : 2024-12-19 21:32:49
  • 链接: https://redefine.ohevan.com/2024/11/06/排序算法/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
目录
排序算法