排序算法（C++）
本帖最后由 aaron0919 于 2022-8-28 12:17 编辑排序算法(上)
1. 选择排序
基本思想：
每一趟从带排序的数据元素中选出最小（或最大）的一个元素，顺序放在待排序的数列的最前，直到全部待排序的数据元素排完
排序过程：
初始关键字
第一趟排序后13
第二趟排序后13 27
第三趟排序后13 27 38
第四趟排序后13 27 38 49
第五趟排序后13 27 38 49 49
第六趟排序后13 27 38 49 49 65
第七趟排序后13 27 38 49 49 65 76
最后排序结果13 27 38 49 49 65 76 97
实现步骤：
①读入数据存放在 a 数组中。
②在 a~a 中选则值最小的元素，与第 1 位置元素做交换，则把最小值元素放入 a 中。
③在 a~a 中选则值最小的元素，与第 2 位置元素做交换，则把最小值元素放入 a 中， ……
④直到第 n-1 个元素与第 n 个元素比较排序为止。
程序实现方法：用两层循环完成算法，外层 i 控制当前序列最小值存放的数组位置，内层循环 j 控制从 i+1 到 n 序列中选择最小的元素所在位置 k 。
程序如下：
#include <iostream>
using namespace std;
const int MAX = 10001;
int temp, a, n;
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) //我喜欢已 1 开始
{
cin >> a; //读入数据存放在 a 数组中
}
for (int i = 1; i <= n; i++) //外层 i 控制当前序列最小值存放的数组位置
{
int k = i;
for (int j = i + 1; j <= n; j++) //内层循环 j 控制从 i+1 到 n 序列中选择最小的元素所在位置 k
{
if (a < a)
{
k = j;
}
}
if (k != i) //如果需要交换
swap(a, a); //交换他们
}
for (int i = 1; i <= n; i++)
{
cout << a << " "; //输出
}
return 0;
}
2. 冒泡排序
基本思想：
有 n 个数，从第 1 个开始，依次比较相邻的两个数，若逆序就交换这两个数……直到 n-1 与 n 比较完，这是一轮排序。
经过一轮比较后，把最大的数排到最后面，即将最大的数像冒泡一样逐步冒到相应位置。
原来 n 个数的排序问题就变成了 n-1 个数的排序问题。
第二次排序：
从第 1 个开始，依次比较相邻的两个数，若逆序就交换这两个数……直到 n-2 与 n-1 比较完，这是第二轮排序。
排序过程：
例如有 6 个数要排序：
6 5 3 4 1 2
第一轮排序：
5 6 3 4 1 2
^^
5 3 6 4 1 2
^^
5 3 4 6 1 2
^^
5 3 4 1 6 2
^^
5 3 4 1 2 6 第一轮排序结束，最后的 6 固定下来
^^
第二轮排序：
5 3 4 1 2 6
3 5 4 1 2 6
^^
3 4 5 1 2 6
^^
3 4 1 5 2 6
^^
3 4 1 2 5 6第二轮排序结束，最后的 5 固定下来
^^
第三轮排序：
3 4 1 2 5 6
3 4 1 2 5 6
^^
3 1 4 2 5 6
^^
3 1 2 4 5 6第三轮排序结束，最后的 4 固定下来
^^
第四轮排序：
3 1 2 4 5 6
1 3 2 4 5 6
^^
1 2 3 4 5 6第四轮排序结束，最后的 3 固定下来
^^
第五轮排序：
1 2 3 4 5 6
1 2 3 4 5 6第五轮排序结束，最后的 2 固定下来
^^
五轮排序后， 6 六个数就已经排完了。排序过程中，大数慢慢地往后，相当于气泡上升，所以叫冒泡排序。
实现步骤：
①读入数据存放在 a 数组中。
②比较相邻的两个数，如果前面的数大于后面的数，就交换它们。
③对数组的第 1 个数到第 n 个数进行一次遍历后，最大的一个”数“就冒到数组第 n 个位置。
④n-- ，n 如果不为 1 就重复 ② 、 ③ ，否则排序完成。
程序实现方法：用两层循环完成算法，外层 i 控制每轮比较多少次的比较，内层循环 j 控制每轮 i 次比较相邻的两个元素是否逆序，否则交换它们。
程序如下：
#include <iostream>
using namespace std;
const int MAX = 10001;
int temp, a, n;
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a; //读入数据存放在 a 数组中
}
for (int i = n; i > 1; i--) //外层 i 控制每轮比较多少次的比较
{
for (int j = 1; j < i; j++) //内层循环 j 控制每轮 i 次比较相邻的两个元素是否逆序，否则交换它们
{
if (a > a)//比较相邻的两个元素是否逆序，否则交换它们
{
swap(a, a); //交换他们
}
}
}
for (int i = 1; i <= n; i++)
{
cout << a << " "; //输出
}
return 0;
}
其实还可以改进。
void bubble_sort(int* arr, int size) {
for (int i = 0; i < size; i++) {
int flag = 1; // 0:需要排序1:不需要排序
for (int j = 0; j < size - i - 1; j++) {
if (arr > arr) {
flag = 0;
int temp = arr;
arr = arr;
arr = temp;
}
}
if (flag) break;
}
}
3. 插入排序
基本思想：
想打牌一样，拿到一张牌，就把这张牌插到合适的位置，这样某完牌，牌就是有序的，也就是插入排序。
当读入一个数时，在已排好的序列中，找到正确位置，再插入。
有一点很重要：不能覆盖以前的数，得把后面的数挪一挪。
排序过程：
例如有 8 个数要排序：
36 25 48 12 65 43 20 58
那么：
第 0 步 [36] 25 48 12 65 43 20 58
第 1 步 [25 36] 48 12 65 43 20 58
第 2 步 48] 12 65 43 20 58
第 3 步 [12 25 36 48] 65 43 20 58
第 4 步 65] 43 20 58
第 5 步 43 48 65] 20 58
第 6 步 20 25 36 43 48 65] 58
第 7 步 58 65]
实现步骤：
①读入数据存放在 a 数组中。
②将 a[ i ] 插入适当位置，将后面的数往后挪
③若 i 不等于 n ，执行 ③ ，否则结束
程序实现方法：用两层循环完成算法，外层 i 控制插入多少次，内层循环 j 控制每轮 a[ i ] 插入的位置，找到就插入。
程序如下：
#include <iostream>
using namespace std;
const int MAX = 10001;
int temp, a, n, i, j, k;
int main()
{
cin >> n;
for (i = 1; i <= n; i++)
{
cin >> a; //读入数据存放在 a 数组中
}
for (i = 1; i <= n; i++) //外层 i 控制插入多少次
{
for (j = i - 1; j >= 1; j--) //内层循环 j 控制每轮 a 插入的位置
{
if (a < a) //找到合适的位置
{
break; //找到就退出
}
}
if (j != i - 1)
{
int temp = a; //将比 a 大的数往后挪
for (k = i - 1; k > j; k--)
{
a = a; //将 a 放到正确的位置上
}
a = temp;
}
}
for (i = 1; i <= n; i++)
{
cout << a << " "; //输出
}
return 0;
}
4. 桶排序
基本思想：
桶的思想：
【LeetCode——桶的思想】https://mbd.baidu.com/ma/s/0Y59DVhk
若序列的值在一个明显有范围内的（无符号）整数内，可设计若干个有序痛。
桶号就是数据的值，桶内就是个数
只需输入完按顺序输出就行了
排序过程：
无
实现步骤：
无
程序如下：
#include <iostream>
using namespace std;
const int MAX = 10001;
int temp, a, n, i, j, k;
int main()
{
cin >> n;
for (i = 1; i <= n; i++)
{
int t;
cin >> t;
a++; //对应桶号加一
}
for (i = 1; i <= MAX - 1; i++)
{
while (a-- > 0)
{
cout << i << " ";
}
}
return 0;
}
#include <algorithm>
sort(a + i, a + j, comp); //表示 a 数组的 i 到 j 已 comp(自定义比较函数，可为空) 排序
例如：
把 a 数组的前十个数从大到小排序
bool comp(int x,int y)//自定义比较函数
{
return x>y;
}
sort(a, a + 10, comp);
排序算法下 来啦 柿子饼同学 发表于 2022-8-26 13:54
来啦
谢谢，最近好忙 @liuzhengyuan 期待完善桶排序！{:10_275:} liuzhengyuan 发表于 2022-8-26 21:06
期待完善桶排序！
理解桶的思想后就不需要讲解了 liuzhengyuan 发表于 2022-8-26 21:06
期待完善桶排序！
其实需要完善的是冒泡 aaron0919 发表于 2022-8-26 21:15
其实需要完善的是冒泡
。{:10_323:} {:5_108:}
页:
[1]