CSP-J初赛知识点 十大排序算法 结构体和联合体区别

排序（Sorting）是计算机程序设计中的?种重要操作，其功能是对?个数据元素集合或序列重新排列成?个按数据元素某个项值有序的序列。

1、选择排序

选择排序的思想就是：从当前数中选出?个最?或者最?的值排在最前?，然后从剩下的数 中选出剩下数的最值排在已经排序的数的后?，算法时间复杂度O(n^2)。

2、冒泡排序

冒泡排序的思想就是：?如说要升序排列，那么就依次相邻两个数?较??，然后把?的数 放在后?，依次类推。冒泡排序时间复杂度0(n^2)

3、插?排序

插?排序思想就是：依次遍历数组，假设前?已经有?部分排过序的，当前待排数字跟前? 的数字依次?较??，将其插在对应顺序位置，算法时间复杂度0（n^2）在实际?作中这种 排序算法不可取。

4、希尔排序

希尔排序的思想就是：希尔排序是对插?排序的改进，可以把当前数据分组，每个分组都有 ?定间隔，?如说原来数组的?标范围是0,1,2,3,4,5,6,7,8,9.我??把它们分成两组，0-4 ?组，5-9?组，这样的话，间隔就是5,我们令0,5,；1,6；2,7；3,8；4,9,它们两两?较??。然 后再减?间隔范围，或者说增多分组个数，?如此时，间隔为2,那么?较下标为0,2,4,6,8 的??，然后?较下标为1,3,5,7,9的??。到最后间隔变为1,就变成了完全的插?排序了。希尔排序的算法时间复杂度O(n^2)

5、快速排序

快速排序利?分治的思想，在数组中设置?个游标，从数组的两端来遍历数组，将元素和游 标相?，意图达到两组数据?边游标?，?边?游标?。那么此时的游标就处于两组数组的 中间。然后依次对前后两组数据排序，此时当然可以利?递归了。时间平均复杂度是 O(n*logn),排序算法貌似是公认最实?最好的排序算法，在?多数情况下都能解决问题，提 ?效率，当然也有糟糕的时候，此时的算法时间复杂度达到O(n^2)

6、归并排序

归并排序的思想就是把数组分成两组，前后两组分别排序，两组排完序后再把两组合并起来， 当然可以利?递归的思想来实现归并排序，算法时间复杂度O(n*logn)

7、堆排序

?先说明什么是堆，堆其实就?个?叉树，其中要满??节点?于或者?于?节点。把数组 中元素按照堆来遍历，修正堆后，那么最?或者最?的元素就在根节点上了。我们把根节点 移除，按照相同的?法再次得到最值，依次类推，直到剩下?个元素位置。算法时间复杂度 是 O(n*logn)

8、基数排序

基数排序和后?要说的计数排序，桶排序都是??较排序，因此他们能够突破?较排序的时 间上限O(n*logn),达到时间复杂度为O(n)的程度，但是这?种排序都有限制性条件，不能 看到他们的时间复杂付貌似?别的低?个等级就觉得他们是最好的排序算法了。三者的思想 类似，都是?到了桶的概念。基数排序针对的是?负整数，将所有的数字依次?较个位，? 位，百位，直到最?位，每?次?较都能得到?个排序，由于越往?位，这个位上数字影响 权重越?，所以能够起到对前?顺序的修正。

9、计数排序

计数排序的思想也很简单，就是针对所有的整数。取?个从最?值到最?值的间隔，然后遍 历数组，把当前元素放在下标为(当前元素值-最?值）的位置。

10、桶排序

桶排序的思想就是先把数据分成?个个分组，这?个个分 组就是?个个桶，当然这些桶是有顺序的，要不然桶排序作为??较排序算法，连唯?的顺序都没有并且也不?较还排什么序啊。对于?次分桶后的数据可以采?递归或者其他的排序 算法实现对每个桶内数据排序。最后按照桶号将所有数据依次连接就是排完顺序的数据了

排序的稳定性：?个排序算法，若可使排序前后关键字相同的项相对顺序不变，则称该排序算法是稳定的排序算法。

结构体和联合体区别

#include<bits/stdc++.h>
using namespace std;
struct node//结构体
{
  int l,r;
  double s;
};


union node2//联合体
{
  int l,r;
  double s;
};


int main()
{
  node a;
  node2 b;
  cout<<sizeof(a)<<endl;
  cout<<sizeof(b)<<endl;
  return 0;
}

结构体和联合体区别：结构体内部每个成员的空间不共用，每个成员都占用固定的空间。联合体内的成员共同占用一个空间。结构体和联合体访问方法一致。

所以如上述程序输出结果：