各种排序的模板题

文章目录

• • • 问题 A: DS内排—直插排序
    • 问题 B: DS排序--希尔排序
    • 问题 C: 冒泡排序 (Ver. I)
    • 问题 D: DS排序--快速排序
    • 问题 E: DS内排—堆排序
    • 问题 F: 基数排序（内部排序）

问题 A: DS内排—直插排序

题目描述

给定一组数据，使用直插排序完成数据的升序排序。

–程序要求–

若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio
程序中若include多过一个头文件，不看代码，作0分处理
不允许使用第三方对象或函数实现本题的要求
输入
数据个数n，n个数据

输出

直插排序的每一趟排序结果

样例输入

7 34 23 677 2 1 453 3

样例输出

23 34 677 2 1 453 3
23 34 677 2 1 453 3
2 23 34 677 1 453 3
1 2 23 34 677 453 3
1 2 23 34 453 677 3
1 2 3 23 34 453 677

#include<iostream>
using namespace std;

int s[10000] = { 0 };

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }
    for (int i = 1; i < n; i++) {
        int tmp = s[i];//待插数字
        int j = i - 1;
        for (; j >= 0 && s[j] > tmp; j--) {//
            s[j + 1] = s[j];//往后哦诺
        }
        s[j + 1] = tmp;
        for (int k = 0; k < n; k++) {
            if (k == 0)cout << s[k];
            else cout << ' ' << s[k];
        }
        cout << endl;
    }
    return 0;
}

问题 B: DS排序–希尔排序

题目描述

给出一个数据序列，使用希尔排序算法进行降序排序。

间隔gap使用序列长度循环除2直到1

输入

第一行输入t，表示有t个测试示例
第二行输入n，表示第一个示例有n个数据(n>1)
第三行输入n个数据，都是正整数，数据之间用空格隔开
以此类推

输出

对每组测试数据，输出每趟排序结果。不同组测试数据间用空行分隔。

样例输入

2
6
111 22 6 444 333 55
8
77 555 33 1 444 77 666 2222

样例输出

444 333 55 111 22 6
444 333 111 55 22 6

444 555 666 2222 77 77 33 1
666 2222 444 555 77 77 33 1
2222 666 555 444 77 77 33 1

#include<iostream>
using namespace std;

int s[10000] = { 0 };

int main()
{
    int t, len;
    cin >> t;
    while (t--) {
        cin >> len;
        for (int i = 0; i < len; i++)cin >> s[i];
        for(int gap=len/2;gap>=1;gap/=2){
            for (int i = gap; i < len; i++) {
                int tmp = s[i];//待插数字
                int j = i - gap;
                for (; j >= 0 && s[j] < tmp; j -= gap) {//
                    s[j + gap] = s[j];//往后哦诺
                }
                s[j + gap] = tmp;
            }
            for (int i = 0; i < len; i++) {
                if (i == 0)cout << s[i];
                else cout << ' ' << s[i];
            }
            cout << endl;
        }
        cout << endl;
    }
    return 0;
}

问题 C: 冒泡排序 (Ver. I)

题目描述

给定一个包含从0到n-1各一次的数组，若使用冒泡排序将其排为升序，问其中需要进行多少次交换

输入

测试数据有多组，

每组由两行组成：第一行包含正整数n（n <= 5000）; 下一行包含从0到n-1的n个整数的序列。

输出

对于每组测试数据，

输出交换次数

样例输入

10
1 3 6 9 0 8 5 7 4 2

样例输出

22

#include<iostream>
using namespace std;

int s[10000] = { 0 };

int mysort(int len) {
    int sum = 0;
    for (int i = 0; i < len-1; i++) {//len-1 ci
        for (int j = 0; j < len - i-1; j++) {
            if (s[j + 1] < s[j]) {
                int temp = s[j + 1];
                s[j + 1] = s[j];
                s[j] = temp;
                sum++;
            }
        }
    }
    //for (int i = 0; i < len; i++)cout << s[i] << ' ';
    //cout << endl;
    return sum;
}

int main()
{
    int n;
    while (cin >> n) {
        for (int i = 0; i < n; i++)cin >> s[i];
        cout << mysort(n) << endl;
    }
    return 0;
}

问题 D: DS排序–快速排序

题目描述

给出一个数据序列，使用快速排序算法进行从小到大的排序

–程序要求–

若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio
程序中若include多过一个头文件，不看代码，作0分处理
不允许使用第三方对象或函数实现本题的要求

输入

第一行输入t，表示有t个测试示例
第二行输入n，表示第一个示例有n个数据
第三行输入n个数据，都是正整数，数据之间用空格隔开
以此类推

输出

每组测试数据，输出每趟快排的结果，即每次排好一个数字结果（长度为1的子序列，不用排，不用输出）。不同测试数据间用空行分隔。

样例输入

2
6
111 22 6 444 333 55
8
77 555 33 1 444 77 666 2222

样例输出

55 22 6 111 333 444
6 22 55 111 333 444
6 22 55 111 333 444
6 22 55 111 333 444

1 33 77 555 444 77 666 2222
1 33 77 555 444 77 666 2222
1 33 77 77 444 555 666 2222
1 33 77 77 444 555 666 2222
1 33 77 77 444 555 666 2222

#include <iostream>
#include<algorithm>
using namespace std;

int head[10] = { 0 };
int len;


void headAjust(int start,int end) 
{
	int dad = start;
	int son = dad * 2;
	while (son <= end) {
		if (son + 1 <= end && head[son] > head[son + 1])son++;
		if (head[dad] < head[son])return;
		else {
			swap(head[dad], head[son]);
			dad = son;
			son = dad * 2;
		}
	}
}

void headsort() 
{
	//create head
	for (int i = len / 2; i >= 1; i--) {
		headAjust(i,len);
	}
	cout << len;
	for (int i = 1; i <= len; i++)
		cout << ' ' << head[i];
	cout << endl;
	for (int i = len; i > 1; i--) {
		swap(head[1], head[i]);
		headAjust(1, i-1);
		cout << len;
		for (int i = 1; i <= len; i++)
			cout << ' ' << head[i];
		cout << endl;
	}
}

int main() 
{
	cin >> len;
	for (int i = 1; i <= len; i++)cin >> head[i];
	headsort();
	return 0;
}

问题 E: DS内排—堆排序

题目描述

给定一组数据，使用堆排序完成数据的降序排序。（建小顶堆)。

输入

数据个数n，n个整数数据

输出

初始创建的小顶堆序列

每趟交换、筛选后的数据序列，输出格式见样例

样例输入

8 34 23 677 2 1 453 3 7

样例输出

8 1 2 3 7 23 453 677 34
8 2 7 3 34 23 453 677 1
8 3 7 453 34 23 677 2 1
8 7 23 453 34 677 3 2 1
8 23 34 453 677 7 3 2 1
8 34 677 453 23 7 3 2 1
8 453 677 34 23 7 3 2 1
8 677 453 34 23 7 3 2 1

#include <iostream>
using namespace std;

int s[1000] = { 0 };
int len;

void mysort(int l,int r)
{
	if (l < r) {
		int i = l, j = r;// 2 point 
		int x = s[l];
		while (i < j) {
			//from right to left
			while (i < j && s[j] >= x)j--;
			if (i < j)s[i++] = s[j];
			while (i < j && s[i] < x)i++;
			if (i < j)s[j--] = s[i];
		}//when left ,mean i==j
		s[i] = x;
		for (int i = 0; i < len; i++) {
			if (i == 0)cout << s[i];
			else cout << ' ' << s[i];
		}
		cout << endl;
		mysort(l,i-1);
		mysort(i+1,r);
	}
}

int main()
{
	int t;
	cin >> t;
	while (t--) {
		cin >> len;
		for (int i = 0; i < len; i++)cin >> s[i];
		mysort(0,len-1);
		cout << endl;
	}
	return 0;
}

问题 F: 基数排序（内部排序）

题目描述

给定一组数据，对其进行基数升序排序。

输入

测试次数t

每组测试数据一行：数字个数n，后跟n个数字（整数）

注：如果序列中有负数，则每个数字加上最小负数的绝对值，使序列中的数均大于等于0。排序后再减去最小负数的绝对值。

输出

对每组测试数据，输出每趟分配、收集的结果。若分配中该位没有数字，输出NULL。具体输出格式见样例。每组测试数据间以空行分隔。

如果序列中有负数，最后输出减去最小负数绝对值的序列值。

样例输入

2
10 278 109 63 930 589 184 505 269 8 83
6 57 0 93 19 18 99

样例输出

0:->930->^
1:NULL
2:NULL
3:->63->83->^
4:->184->^
5:->505->^
6:NULL
7:NULL
8:->278->8->^
9:->109->589->269->^
930 63 83 184 505 278 8 109 589 269
0:->505->8->109->^
1:NULL
2:NULL
3:->930->^
4:NULL
5:NULL
6:->63->269->^
7:->278->^
8:->83->184->589->^
9:NULL
505 8 109 930 63 269 278 83 184 589
0:->8->63->83->^
1:->109->184->^
2:->269->278->^
3:NULL
4:NULL
5:->505->589->^
6:NULL
7:NULL
8:NULL
9:->930->^
8 63 83 109 184 269 278 505 589 930

0:->0->^
1:NULL
2:NULL
3:->93->^
4:NULL
5:NULL
6:NULL
7:->57->^
8:->18->^
9:->19->99->^
0 93 57 18 19 99
0:->0->^
1:->18->19->^
2:NULL
3:NULL
4:NULL
5:->57->^
6:NULL
7:NULL
8:NULL
9:->93->99->^
0 18 19 57 93 99

#include<iostream>
#include<vector>
#include<cstdlib>
using namespace std;;

void mysort()
{
    int len, maxnum = -10000, min = 10000;
    cin >> len;
    int* nums = new int[len + 100];//存储数据

    //得到最大负数，最大位数
    for (int i = 0; i < len; i++) {
        cin >> nums[i];
        //if(nums[i]<0&&nums[i]<min)min=nums[i];
        if (nums[i] > maxnum)maxnum = nums[i];
    }
    // for(int i=0;i<len;i++){
    //     nums[i]+=abs(min);//全部加上正数
    // }
    for (int i = 10; maxnum > 0; i *= 10, maxnum /= 10) {//循环最大位数次
        vector<vector<int> > s1;//二维vector数组
        for (int p = 0; p < 10; p++) {//填充二维数组
            vector<int> temp;
            s1.push_back(temp);
        }
        for (int j = 0; j < len; j++) {
            int k = nums[j];
            k %= i;
            k = k / (i / 10);
            s1[k].push_back(nums[j]);
        }
        int index = 0;
        for (int k = 0; k < 10; k++) {//输出
            cout << k << ':';
            if (s1[k].empty())cout << "NULL" << endl;
            else {
                for (int q = 0; q < s1[k].size(); q++) {
                    nums[index++] = s1[k][q];//更新nums数组
                    cout << "->" << s1[k][q];
                }
                cout << "->^" << endl;
            }
        }
        for (int i = 0; i < len; i++) {
            if (i == 0)cout << nums[i];
            else cout << ' ' << nums[i];
        }
        cout << endl;
    }

}

int main()
{
    int t;
    cin >> t;
    while (t--) {
        mysort();
        cout << endl;
    }
    return 0;
}