基础算法（一）
前言
蒟蒻复习，如有错请指出
一、基础排序
1.冒泡排序
冒泡排序是一种基础的排序算法，其主要原理是通过不断比较相邻元素并交换位置，将较大的元素逐渐推向序列的末尾，从而实现整个序列的排序。
冒泡排序的基本思想是：
对相邻的元素进行两两比较，顺序相反则进行交换，这样，每一趟会将最小或最大的元素浮到顶端，最终达到完全有序。
具体步骤如下：
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
举个栗子
：
用冒泡排序把下面五个数排序为从小到大的递增序列
5 4 3 2 1
第一步：将最大的数字5浮到底端
4 3 2 1 5
第二步：将次大的数字4浮到最大的数字5前面
3 2 1 4 5
第三步：将数字3浮到次大的数字4前面
2 1 3 4 5
第四步：将次小的数字2浮到数字3前面
1 2 3 4 5
理解了冒泡排序的排序过程，再来看看使用代码如何使用冒泡排序吧！
采用例题
- 冒泡排序
题目ID：1231
这一题和6318有一些不同，这一题只需要输出排序之后的数字序列
代码实现
for ( int i = 1 ; i <= n-1 ; i++) {
for ( int j = 1 ; j <= n - i ; j++) {
if ( a[j] > a[j+1]) {
swap( a[j] , a[j+1]);
}
}
}
如果题目有要求输出中间过程，那么代码的输出就应当在最后一个for循环里；只需输出排序之后序列的在结束代码之前使用for循环进行输出就好啦~
2.选择排序
选择排序的思想是：
首先在未排序序列中找到最值元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最值元素，然后放到已排序序列的末尾。
直到全部排序结束为止。
在此就不举栗了
采用例题
- 选择排序
题目ID：1160
代码实现
for( int i = 0; i < n - 1 ; i++) {
int minn = i;
for (int j = i + 1 ; j < n ; j++)
if( a[j] < a[minn]) {
minn = j;
}
swap ( a[i] ,a[minn]);
}
输出也是一样的
3.插入排序
插入排序基本思想是：
每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。
举个栗子（自行
-
4 5 3 2 1
-
3 4 5 2 1
-
2 3 4 5 1
-
1 2 3 4 5
采用例题
- 插入排序
题目ID：1230
代码实现
for ( int i = 2; i <= n; i++) {
int j = i;
while ( j != 1) {
if ( a[j] < a[j-1]) {
swap ( a[j] , a[j-1]);
j--;
} else {
break;
}
}
}
4.桶排序
桶排序的主要思想是对待排序序列的关键字数值进行分块，每一块对应一个桶，然后对每个桶使用插入排序（或其他排序算法）进行排序，最后将所有桶中的元素串联起来即得到有序序列。
桶排序是一种分配排序，通过创建多个桶，并将数据分布到这些桶中，然后对每个桶中的数据进行排序，最后将所有桶中的数据依次取出，得到有序序列。桶排序的基本思想包括以下几个方面：
分块：将待排序的序列按照关键字数值分成若干个子序列，每个子序列称为一个桶。这通常是通过计算数据值与最小值（或最大值）的差异，并根据这个差异将数据分配到相应的桶中。
局部排序：对每个桶中的数据进行排序。这可以使用任何其他的排序算法，如插入排序、快速排序等。每个桶内的排序是独立的。
合并：将所有桶中的数据按照桶的顺序依次取出，合并成一个有序序列。由于桶与桶之间是有序的，因此合并过程也是有序的。
采用例题
- 桶排序
题目ID：8408
代码实现
for ( int i = 1; i <= n; i++){
int b;
cin >> b;
a[b]++;
}
for ( int i = 1; i <= 10000000; i++){
while ( a[i] != 0){
cout << i << " ";
a[i]--;
}
}
未完待续
[我们下期再见！]ヾ(•ω•`)o