关于排序知识点，在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 << " "; //依次输出下标即为排好的有序序列
}
}
}
知识考察
1.将数组 {8，23，4，16，77，-5，53，100} 中元素从大到小按顺序排序，每次可以交换任意两个元素，最少要交换( B )次。 A.4 B.5 C.6 D.7
2.( A )的平均时间复杂度为 O(nlogn)，其中 n是待排序的元素个数 A. 快速排序 B.插入排序 C.冒泡排序 D. 基数排序
3.在待排序的数据表已经为有序时，下列排序算法中花费时间反而多的是( D )。 A.堆排序 B.桶排序 C.冒泡排序 D.快速排序
4.在下列各种排序算法中，不是以“比较”作为主要操作的算法是( D ) A.选择排序 B.冒泡排序 C.插入排序 D.基数排序
5.将5个数的序列排序，不论原先的顺序如何，最少都可以通过( A )次比较，完成从小到大的排序。 A.7 B.8 C.9 D. 10
6.在所有排序方法中,关键字比较的次数与记录的初始排列次序无关的是( D )。 A.希尔排序 B.冒泡排序 C.插入排序 D.选择排序
7.排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列哪种排序算法是不稳定的( D )。 A.冒泡排序 B.插入排序 C.归并排序 D.快速排序
8.体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。每个同学按顺序来到操场时，都从排尾走向排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于( B )算法。 A.快速排序 B.插入排序 C.冒泡排序 D.归并排序
9.使用冒泡排序对序列进行升序排列，每执行一次交换操作系统将会减少1个逆序对，因此序列5,4,3,2,1需要执行( C )次操作，才能完成冒泡排序。 A.0 B.5 C.10 D.15
10.排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列排序算法稳 定的是( B )。 A.选择排序 B.冒泡排序 C.快速排序 D.希尔排序
11.对于给定的序列{a1,a2...ai...aj....ak}，我们把(i,j)称为逆序对当且仅当讠< j且ai > aj。那么序列{1,7,2,3,5,4}的逆序对数为( B )个?。 A.4 B.5 C.6 D.7
12.对于给定的序列 {7,5,1,9,3,6,8,4)，在不改变顺序的情况下，去掉()会使逆序对的个数减少3?( C )。 A.7 B.5 C.3 D.8
13.基于比较的排序时间复杂度的下限是( B )，其中n表示待排序的元素个数。 A.0(n) B.0(nlogn) C.0(logn) D.0(n²)
14.考虑如下递归算法
int solve(int n)
{
if(n<=1) {
return 1;
}
else if(n>=5){
return n*solve(n-2);
}
else {
return n*solve(n-1);
}
}
则调用 solve(7)得到的返回结果为( C )。 A.105 B.840 C.210 D.420
15.在程序运行过程中，如果递归调用的层数过多，可能会由于( A )引发错误。 A.系统分配的栈空间溢出 B.系统分配的队列空间溢出 C.系统分配的链表空间溢出 D.系统分配的堆空间溢出
16.现有一段文言文，要通过二进制哈夫曼编码进行压缩。简单起见，假设这段文言文只由4个汉字“之“、“乎”、“者”、"也“组成，它们出现的次数分别为700、600、300、200。那么，“也”字的编码长度是( C )。 A.1 B.2 C.3 D.4
17.在数据压缩编码中的哈夫曼编码方法，在本质上是一种( B )的策略。 A.枚举 B.贪心 C.递归 D.动态规划
18.( C )就是把一个复杂的问题分成两个或者更多的相同或相似的子问题，再把子问题分成更小的子问题，…，直到最后的子问题可以简单的直接求解。而原问题的解就是子问题解的并。 A.动态规划 B.贪心 C.分治 D.搜索
19.设有100个数据元素，采用折半搜索时，最大的比较次数为( B )。 A.6 B.7 C.8 D.10
20.快速排序最坏情况下的算法时间复杂度为( D )? A.O(logn) B.O(n) C.O(nlogn) D. O(n²)