关于排序知识点，在算法-基础算法中提到了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 << " "; //依次输出下标即为排好的有序序列
    }
  }
}