7-12排序

题目描述

题目地址为:https://pintia.cn/problem-sets/15/problems/720

给定\({N}\)个（长整型范围内的）整数，要求输出从小到大排序后的结果。

本题旨在测试各种不同的排序算法在各种数据情况下的表现。各组测试数据特点如下：

  • 数据1：只有1个元素；
  • 数据2：11个不相同的整数，测试基本正确性；
  • 数据3：\({10^3}\)个随机整数；
  • 数据4：\({10^4}\)个随机整数；
  • 数据5：\({10^5}\)个随机整数；
  • 数据6：\({10^5}\)个顺序整数；
  • 数据7：\({10^5}\)个逆序整数；
  • 数据8：\({10^5}\)个基本有序的整数；
  • 数据9：\({10^5}\)个随机正整数，每个数字不超过1000。

输入格式:

输入第一行给出正整数\({N（≤10^5）}\)，随后一行给出\({N}\)个（长整型范围内的）整数，其间以空格分隔。

输出格式:

在一行中输出从小到大排序后的结果，数字间以1个空格分隔，行末不得有多余空格。

输入样例:

1
2
11
4 981 10 -17 0 -20 29 50 8 43 -5

输出样例:

1
-20 -17 -5 0 4 8 10 29 43 50 981

吐槽

这不就是考察的几大经典排序算法吗？

主函数

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
#include<stdio.h>
//冒泡算法
void BubbleSort(int a[],int n);
//插入排序
void InsertionSort(int a[],int n);
//选择排序
void SelectionSort(int a[],int n);
//快速排序
void QuickSort(int a[],int i,int j);
//希尔排序
void ShellSort(int a[],int n);
//归并排序
void MergeSort(int a[],int i,int j,int b[]);

int a[100001];
int b[100001];

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

    //这里添加各种排序算法
    
    for(i=0;i<n;i++){
        if(i==n-1)printf("%d",a[i]);
        else printf("%d ",a[i]);
    }
    return 0;
}

冒泡排序

具体代码

1
2
3
4
5
6
7
8
9
10
11
void BubbleSort(int a[],int n) {
    for(int i = 0; i < n-1; i++) {
        for(int j = 0; j < n-1-i; j++) {
            if(a[j] > a[j+1]) {
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
    }
}

测试结果

插入排序

具体代码

1
2
3
4
5
6
7
8
9
10
void InsertionSort(int a[],int n) {
    for(int i = 1; i < n; i++) {
        int temp = a[i];
        int j;
        for(j = i-1 ; j>=0 && temp < a[j]; j--) {
            a[j+1] = a[j];
        }
        a[j+1] = temp;
    }
}

测试结果

选择排序

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void SelectionSort(int a[],int n) {
    int minIndex = 0;
    for(int i = 0; i < n; i++) {
        minIndex = i;
        for(int j = i+1; j < n; j++) {
            if(a[j] < a[minIndex]) {
                minIndex = j;
            }
        }
        int temp = a[i];
		a[i] = a[minIndex];
		a[minIndex] = temp;
    }
}

测试结果

快速排序

具体代码

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
int partition(int a[],int i,int j) {
    int temp = a[i];

    while (i < j) {
        while(a[j] >= temp && i < j) {
            j--;
        }
        if(i < j) {
            a[i++] = a[j];
        }
        while(a[i] <= temp && i < j) {
            i++;
        }
        if(i < j) {
            a[j--] = a[i];
        }
    }
    a[i] = temp;
    return i;
}
void QuickSort(int a[],int i,int j) {
    int k;
    if (i < j) {
        k = partition(a,i,j);
        QuickSort(a,i,k-1);
        QuickSort(a,k+1,j);
    }
}

测试结果

希尔排序

提醒

希尔排序就是特殊的插入排序，只是之间的间隔增大了。插入排序的间隔为1，而希尔排序是delta

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void ShellSort(int a[],int n) {
    int i,j;
    int temp;
    int gap;
    for(gap = n/2 ; gap > 0 ; gap /= 2 ){
        for(i = gap; i < n; i++) {
            temp = a[i];
            for (j = i - gap; j >= 0 && temp < a[j] ; j -= gap) {
                a[j+gap] = a[j];
            }
            a[j+gap]=temp;
        }
    }
}

测试结果

归并排序

具体代码

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
void Merge(int a[],int s1,int e1,int s2,int e2,int b[]) {
    int k=s1;
	int i=s1;

    while(s1 <= e1 && s2 <= e2) {
        if (a[s1] <= a[s2]) {
            b[k++] = a[s1++];
        } else {
            b[k++] = a[s2++];
        }
    }

    while(s1 <= e1) b[k++] = a[s1++];
	while(s2 <= e2) b[k++] = a[s2++];
    k--;
    while(k >= i) {
        a[k] = b[k];
        k--;
    }
}

void MergeSort(int a[],int i,int j,int b[]) {
    int k;
    if (i < j) {
        k = (i+j)/2;
        MergeSort(a,i,k,b);
        MergeSort(a,k+1,j,b);
        Merge(a,i,k,k+1,j,b);
    }
}

测试结果