哈喽，大家好，我是bigbigli。
上个月的今天，我发布了一篇文章
《CSP-J大纲解读》。
关于排序知识点，在算法-基础算法中提到了CSP-J中所考察的排序知识点，有选择排序、冒泡排序、插入排序及计数排序。
今天我们用一篇文章来复习CSP-J中所有排序知识，这里假设共n个元素，所有元素是从小到大排列。
选择排序
从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置
然后再从剩余的未排序元素中寻找到最小元素，然后放到已排序的序列的后面。
以此类推，直到全部待排序的数据元素的个数为零。
void Selection(int a[],int n){
//a为存放元素的数组，n为有多少个元素
for(int i=1;i<n;i++){
//外层循环是当前数组空间的元素a[i]，它要与后面所有的元素比较大小，最后一个数不需要再比较
for(int j=i+1;j<=n;j++){
//a[j]需要从i的后面一个数开始，一直需要与a[i]相比较
//一直比较到最后一个数a[j]，保证a[i]经过比较后是最小的数
if(a[i]>a[j]) swap(a[i],a[j]);
//如果发现后面的数小，就将其移到下标为i的空间，保证a[i]是最小的数
}
}
}
冒泡排序
小的元素会经由交换慢慢“浮”到顶端，就像泡泡一样，故名“冒泡排序”。
它的工作原理是，重复地走访过要排序的元素，依次比较两个相邻的两个元素，如果前面的数比后面的数大就把他们交换过来。
走访元素的工作重复地进行，直到没有相邻元素需要交换。
void Bubblen(int a[],int n){
for(int i=1;i<n;i++){
//外层循环每循环一次，都能找到一个当前最大的数放到顶端（末尾）
for(int j=1;j<=n-i;j++){
//每两个相邻的数比较，比较完一轮，找到最大值，下次就少比较一轮（j-i）
if(a[j]>a[j+1]){
//相邻的两个数比较，小的放在前面
swap(a[j],a[j+1]);
}
}
}
}
插入排序
插入排序的工作方式像许多人排序一手扑克牌。
开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。
为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较，当找到一个比他小的牌，就将这张牌插到它的前面。
void Insertion(int a[],int n){
for(int i=2;i<=n;i++){
//假设第一张牌已经是有序的，从第二张开始插入
int j=i-1,key=a[i];
//新的牌(key)要与之前所有的牌比较，直到比到第一张（j=1）
while(j>=1&&key<a[j]){
//如果新的牌(key)小于前面的牌，那么就一直循环
a[j+1] = a[j];//将大于key的牌往后移
j--;//当前下标往前移(j--)
}
}
}
计数排序
给定这n个数一个有限范围（这里假设范围为1~10000），开一个不小于10000的数组，将其中所有元素初始化为0。
假设这n个数中有个数为k，则将数组下标为k的值增加1。
也就是说，当我们输入一个数，就将对应的数组下标的空间元素增加1。
int a[10010]; //初始化数组所有元素
void counting(int a[],int n){
int k;
for(int i=1;i<=n;i++){
cin >> k;//每次输入的数为k
a[k]++; //将下标为k的元素增加1，表示有一个数为k
}
for(int i=1;i<=10000;i++){
//因为元素的取值范围是1~10000，所有的空间都要遍历一遍，看看有没有出现这个下标
for(int j=1;j<=a[i];j++){
//a[i]为下标出现的次数
cout << i << " "; //依次输出下标即为排好的有序序列
}
}
}
关于排序的知识就讲到这里啦，如有想要继续了解的知识可以在下方留言哦！
网友评论