关于排序知识点,在算法-基础算法中提到了CSP-J中所考察的排序知识点,有选择排序、冒泡排序、插入排序及计数排序。

今天我们用一篇文章来复习CSP-J中所有排序知识,这里假设共n个元素,所有元素是从小到大排列。

文章来源:大李编程

https://www.bilibili.com/video/BV1dX4y1g7cZ?t=617.5

选择排序

从待排序的数据元素中选出最小的一个元素,存放在序列的起始位置

然后再从剩余的未排序元素中寻找到最小元素,然后放到已排序的序列的后面。

以此类推,直到全部待排序的数据元素的个数为零。

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 << " "; //依次输出下标即为排好的有序序列
    }
  }
}