目录
排序应用
常见的排序算法
BubbleSort冒泡排序
整体思路
图解分析
代码实现
每趟
写法1
写法2
代码NO1
代码NO2优化
时间复杂度
排序概念
排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。
- 稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次 序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排 序算法是稳定的;否则称为不稳定的。
- 内部排序:数据元素全部放在内存中的排序。
- 外部排序:数据元素太多不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序。
排序应用
排序的应用场景很多: 学校医院品牌的排名等等。
算法当中也常用,二分查找,去重算法等等。
常见的排序算法
- 冒泡排序
- 直接插入排序&VS冒泡排序
- 希尔排序(在插入排序的基础上)
- 选择排序VS堆排序
- 快速排序
- 归并排序
- 补充:外排序
- 排序的OJ题目
- 排序的思想:先单趟再多趟,注意结束条件❗先局部再整体
BubbleSort冒泡排序
整体思路
- 通过对待排序序列从前向后(从下标较小的元素开始),依次对相邻两个元素的值进行两两比较,若发现逆序则交换,使值较大的元素逐渐从前移向后部,就如果水底下的气泡一样逐渐向上冒泡。
- 一趟:两两比较(若顺序则不交换,若逆序则交换)
- 整体:重复上述过程,直到全部数组元素都每趟完成。
- 优化:若某一趟发现,数组元素已经顺序不用继续冒泡下去,停止冒泡。(效率提高)
图解分析
代码实现
每趟
- n个数的下标是0~n-1
- i每次从0开始,则比较的是下标为i和i+1的数值
- i每次从1开始,则比较的是下标为i-1和i的数值
- 注意:i每次从第一个数值开始冒泡,不是第j格数值开始冒泡
写法1
//写法1
for (int i = 0; i < n-1; i++)
{
if (a[i] > a[i + 1])//i=n-1就越界了
{
Swap(&a[i], &a[i + 1]);
}
}
写法2
//写法2
for (int i = 1; i < n; i++)
{
if (a[i - 1] > a[i])//i=n-1没有越界,
{
Swap(&a[i - 1], &a[i]);
}
}
代码NO1
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void BubbleSort(int* a, int n)
{
for (int j = 0; j < n; j++)
{
//一趟
for (int i = 0; i < n - 1 - j; i++)//i要从第一个开始交换
{
if (a[i] > a[i + 1])//i=n-1就越界了
{
Swap(&a[i], &a[i + 1]);
}
}
}
代码NO2优化
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void BubbleSort(int* a, int n)
{
for (int j = 0; j < n; j++)
{
//一趟
bool exchange = false;
for (int i = 0; i < n - 1 - j; i++)//i要从第一个开始交换
{
if (a[i] > a[i + 1])//i=n-1就越界了
{
Swap(&a[i], &a[i + 1]);
exchange = true;
}
}
if (exchange == false)
{
break;
}
}
}
时间复杂度
时间复杂度:经典的O(N^2)
文章来源:https://www.toymoban.com/news/detail-826197.html
🙂感谢大家的阅读,若有错误和不足,欢迎指正!文章来源地址https://www.toymoban.com/news/detail-826197.html
到了这里,关于排序前言&冒泡排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!