前i个元素是有序的，将第i+1个元素逐个往前比较，比到比一个数大的就插入到这个数后面，即这个数后面的数到i个数全部往后移
例：DS内排—直插排序
题目描述
给定一组数据，使用直插排序完成数据的升序排序。
–程序要求–
若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio
程序中若include多过一个头文件，不看代码，作0分处理
不允许使用第三方对象或函数实现本题的要求
输入
数据个数n，n个数据
输出
直插排序的每一趟排序结果
输入样例1
7 34 23 677 2 1 453 3
输出样例1
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 main()
{
int n;
cin>>n;
int a[205];
//辅助的量
a[0]=-99999999;
for(int i=1;i<=n;i++) cin>>a[i];
//遍历待插入的元素
for(int i=2;i<=n;i++)
{
//待插入的元素
int x=a[i];
//往前比较
for(int j=i-1;j>=0;j--)
{
//插入
if(x>=a[j])
{
//后移
for(int k=i-1;k>=j+1;k--) a[k+1]=a[k];
a[j+1]=x;
for(int k=1;k<=n;k++) (k==1)?cout<<a[k]:cout<<" "<<a[k];
cout<<endl;
break;
}
}
}
return 0;
}
前i个元素是有序的，定义low和high，将第i+1个元素与(low+high)/2进行比较，进行二分查找，直到low=high，然后比较该数与待插入的数，选择插到其前面还是后面
又叫缩小增量排序
例：B. DS排序–希尔排序
题目描述
给出一个数据序列，使用希尔排序算法进行降序排序。
间隔gap使用序列长度循环除2直到1
输入
第一行输入t，表示有t个测试示例
第二行输入n，表示第一个示例有n个数据(n>1)
第三行输入n个数据，都是正整数，数据之间用空格隔开
以此类推
输出
对每组测试数据，输出每趟排序结果。不同组测试数据间用空行分隔。
输入样例1
2
6
111 22 6 444 333 55
8
77 555 33 1 444 77 666 2222
输出样例1
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<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
for(int i=0;i<t;i++)
{
int n;
cin>>n;
int a[205];
memset(a,0,sizeof(a));
for(int j=0;j<n;j++) cin>>a[j];
//增量
int gap=n/2;
while(gap)
{
//每组的起始位置
for(int j=0;j<gap;j++)
{
for(int k=j;k<n;k+=gap)
{
int big=-99999999;
int loc;
for(int m=k;m<n;m+=gap)
{
big=max(big,a[m]);
if(big==a[m]) loc=m;
}
swap(a[loc],a[k]);
}
}
for(int j=0;j<n;j++) (j==0)?cout<<a[j]:cout<<" "<<a[j];
cout<<endl;
//改变增量
gap=gap/2;
}
cout<<endl;
}
return 0;
}
升序排序时，每次排序，比较两个数将大的数往后，不断操作一次排序就会把最大的元素放在最后，再找第二大的，直到待排序序列只有一个元素
例：C. 冒泡排序
题目描述
给定一个包含从0到n-1各一次的数组，若使用冒泡排序将其排为升序，问其中需要进行多少次交换
输入
测试数据有多组，
每组由两行组成：第一行包含正整数n（n <= 5000）; 下一行包含从0到n-1的n个整数的序列。
输出
对于每组测试数据，
输出交换次数
输入样例1
10
1 3 6 9 0 8 5 7 4 2
输出样例1
22
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
//多组输入
while(scanf("%d",&n)!=EOF)
{
int a[5005];
for(int i=0;i<n;i++) cin>>a[i];
int num=0;
//待放入元素的地方
for(int i=n-1;i>=0;i--)
{
for(int j=0;j<i;j++)
{
if(a[j]>a[j+1])
{
swap(a[j],a[j+1]);
num++;
}
}
}
cout<<num<<endl;
}
return 0;
}
具体操作看代码
例：D. DS排序–快速排序
题目描述
给出一个数据序列，使用快速排序算法进行从小到大的排序
–程序要求–
若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio
程序中若include多过一个头文件，不看代码，作0分处理
不允许使用第三方对象或函数实现本题的要求
输入
第一行输入t，表示有t个测试示例
第二行输入n，表示第一个示例有n个数据
第三行输入n个数据，都是正整数，数据之间用空格隔开
以此类推
输出
每组测试数据，输出每趟快排的结果，即每次排好一个数字结果（长度为1的子序列，不用排，不用输出）。不同测试数据间用空行分隔。
输入样例1
2
6
111 22 6 444 333 55
8
77 555 33 1 444 77 666 2222
输出样例1
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>
using namespace std;
//快排函数
void quicksort(int a[],int left,int right,int n)
{
//枢轴量
int flag=a[left];
int low=left,high=right;
while(low<high)
{
//找一个小于枢轴量的数放在这个位置
if(a[low]==flag)
{
while(a[high]>=flag&&high>low) high--;
if(high==low) break;
swap(a[low],a[high]);
low++;
continue;
}
//找一个大于枢轴量的数放在这个位置
if(a[high]==flag)
{
while(a[low]<=flag&&low<high) low++;
if(high==low) break;
swap(a[low],a[high]);
high--;
continue;
}
}
for(int i=0;i<n;i++) (i==0)?cout<<a[i]:cout<<" "<<a[i];
cout<<endl;
//递归
if(high-1-left>=1) quicksort(a,left,high-1,n);
if(right-high-1>=1) quicksort(a,high+1,right,n);
}
int main()
{
int t;
cin>>t;
for(int i=0;i<t;i++)
{
int n;
cin>>n;
int a[205];
for(int i=0;i<n;i++) cin>>a[i];
//快排
quicksort(a,0,n-1,n);
cout<<endl;
}
return 0;
}
若要得到升序，每次从待排序序列中选择一个最小的放在待排序序列的第一个位，待排序序列减小1，直到待排序序列长度为1
例：A. DS排序–简单选择排序
题目描述
给出一个数据序列，使用简单选择排序算法进行升序排序。
输入
第一行输入t，表示有t个测试示例
第二行输入n，表示第一个示例有n个数据(n>1)
第三行输入n个数据，都是正整数，数据之间用空格隔开
以此类推
输出
对每组测试数据，输出每趟排序结果。不同组测试数据间用空行分隔。
输入样例1
2
5
12 58 36 47 96
10
1 3 6 9 0 8 5 7 4 2
输出样例1
12 58 36 47 96
12 36 58 47 96
12 36 47 58 96
12 36 47 58 96
0 3 6 9 1 8 5 7 4 2
0 1 6 9 3 8 5 7 4 2
0 1 2 9 3 8 5 7 4 6
0 1 2 3 9 8 5 7 4 6
0 1 2 3 4 8 5 7 9 6
0 1 2 3 4 5 8 7 9 6
0 1 2 3 4 5 6 7 9 8
0 1 2 3 4 5 6 7 9 8
0 1 2 3 4 5 6 7 8 9
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
for(int i=0;i<t;i++)
{
int n;
cin>>n;
int a[20005];
for(int j=0;j<n;j++) cin>>a[j];
//待放入的位置
for(int j=0;j<n-1;j++)
{
//选择最小的记录位置
int small=a[j];
int loc=j;
for(int k=j+1;k<n;k++)
{
if(small>a[k])
{
small=a[k];
loc=k;
}
}
swap(a[j],a[loc]);
for(int k=0;k<n;k++) (k==0)?cout<<a[k]:cout<<" "<<a[k];
cout<<endl;
}
cout<<endl;
}
return 0;
}
大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列。
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列。
例：B. DS内排—堆排序
题目描述
给定一组数据，使用堆排序完成数据的降序排序。（建小顶堆)。
输入
数据个数n，n个整数数据
输出
初始创建的小顶堆序列
每趟交换、筛选后的数据序列，输出格式见样例
输入样例1
8 34 23 677 2 1 453 3 7
输出样例1
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<bits/stdc++.h>
using namespace std;
struct Node
{
int value;
Node* left=NULL;
Node* right=NULL;
};
//筛选
void choose(Node* node)
{
//叶子节点
if(!node->left&&!node->right) return ;
//左孩子空，右孩子非空
else if(!node->left)
{
if(node->value<=node->right->value) return ;
else
{
swap(node->value,node->right->value);
//继续筛选
choose(node->right);
}
}
//右孩子空，左孩子非空
else if(!node->right)
{
if(node->value<=node->left->value) return ;
else
{
swap(node->value,node->left->value);
//继续筛选
choose(node->left);
}
}
//左右孩子都非空
else
{
if(node->value<=node->left->value&&node->value<=node->right->value) return ;
//和更小的交换
else
{
if(node->left->value<=node->right->value)
{
swap(node->value,node->left->value);
choose(node->left);
}
else
{
swap(node->value,node->right->value);
choose(node->right);
}
}
}
}
//打印
void print(Node* node,int n,vector<int> &v)
{
cout<<n;
queue<Node*> q;
q.push(node);
while(!q.empty())
{
Node* no=q.front();
q.pop();
cout<<" "<<no->value;
if(no->left) q.push(no->left);
if(no->right) q.push(no->right);
}
//将已排好序的逆序输出
for(int i=v.size()-1;i>=0;i--) cout<<" "<<v[i];
cout<<endl;
}
//构建完全二叉树并转化为最小堆
Node* buildTree(int a[],int n,vector<int> &v)
{
//根据索引找到节点
map<int,Node*> m;
int index=1;
queue<Node*> q;
Node* node=new Node;
node->value=a[0];
m[0]=node;
q.push(node);
//构建完全二叉树
while(!q.empty())
{
Node* no=q.front();
q.pop();
if(index<n)
{
no->left=new Node;
no->left->value=a[index++];
q.push(no->left);
m[index-1]=no->left;
}
if(index<n)
{
no->right=new Node;
no->right->value=a[index++];
q.push(no->right);
m[index-1]=no->right;
}
}
//最后一个有叶子节点的节点的位置
int idx=(n-1)/2;
for(int i=idx;i>=0;i--)
{
//筛选操作
choose(m[i]);
}
//打印操作
print(node,n,v);
return node;
}
//交换操作
void exchange(Node* node,vector<int> &v,int n,int k)
{
//即将输出的数的父母索引
int idx=k/2;
int index=0;
//记录待排序堆的最后一个节点
Node* last=node;
//记录即将输出的数的父母节点
Node* par;
queue<Node*> q;
q.push(node);
while(!q.empty())
{
Node* no=q.front();
q.pop();
index++;
//记录父母节点
if(index==idx) par=no;
if(no->left) q.push(no->left);
if(no->right) q.push(no->right);
last=no;
}
v.push_back(node->value);
node->value=last->value;
//将最后一个节点置为空
if(par->right) par->right=NULL;
else par->left=NULL;
//筛选
choose(node);
//打印
print(node,n,v);
}
int main()
{
int n;
cin>>n;
int a[205];
//放入已排好序的数
vector<int> v;
for(int i=0;i<n;i++) cin>>a[i];
//构建初始堆
Node* node=buildTree(a,n,v);
//交换操作
for(int i=0;i<n-1;i++) exchange(node,v,n,n-i);
return 0;
}
先分两个数两个数为一组进行排序，再归并两组，即四个数四个数为一组，直到所有数为一组
例：C. DS内排—2-路归并排序
题目描述
输入一组字符串，用2-路归并排序按字典顺序进行降序排序。
输入
测试次数t
每组测试数据：数据个数n，后跟n个字符串，字符串不含空格。
输出
对每组测试数据，输出2-路归并排序的每一趟排序结果。每组测试数据的输出之间有1空行。
输入样例1
2
6 shenzhen beijing guangzhou futian nanshan baoan
10 apple pear peach grape cherry dew fig haw lemon marc
输出样例1
shenzhen beijing guangzhou futian nanshan baoan
shenzhen guangzhou futian beijing nanshan baoan
shenzhen nanshan guangzhou futian beijing baoan
pear apple peach grape dew cherry haw fig marc lemon
pear peach grape apple haw fig dew cherry marc lemon
pear peach haw grape fig dew cherry apple marc lemon
pear peach marc lemon haw grape fig dew cherry apple
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
for(int i=0;i<t;i++)
{
int n;
cin>>n;
string arr[205];
for(int j=0;j<n;j++) cin>>arr[j];
//间距
for(int j=2;j<n;j*=2)
{
for(int k=0;k<n;k+=j)
{
//降序排序
sort(arr+k,arr+k+j,greater<string>());
}
for(int k=0;k<n;k++) (k==0)?cout<<arr[k]:cout<<" "<<arr[k];
cout<<endl;
}
//最后一次所有数为一组
sort(arr,arr+n,greater<string>());
for(int k=0;k<n;k++) (k==0)?cout<<arr[k]:cout<<" "<<arr[k];
cout<<endl<<endl;
}
return 0;
}
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。
每次进行按照关键字进行筛选再收集起来