ps网站页面设计教程,网站建好用电脑做服务器,深圳市宝安区建设工程交易中心,谷歌浏览器下载安装2023最新版文章目录 1. 基础概念#x1f351; 内部排序和外部排序 2. 直接插入排序3. 动图演示4. 代码实现5. 性能分析 无论是日常生活还是很多科学领域当中#xff0c;排序都是会经常面对的问题#xff0c;比如按成绩对学校的学生排序#xff0c;按薪水多少对公司员工排序等。
根据… 文章目录 1. 基础概念 内部排序和外部排序 2. 直接插入排序3. 动图演示4. 代码实现5. 性能分析 无论是日常生活还是很多科学领域当中排序都是会经常面对的问题比如按成绩对学校的学生排序按薪水多少对公司员工排序等。
根据在排序过程中待排序的数据是否全部被载入到内存中排序分为内部排序和外部排序。下面各种排序算法涉及的主要是内部排序包含各种经典的内部排序算法。
将按照对 数据操作方式 的不同来分类讲解。 1. 基础概念
所谓排序Sort就是将一组数据也称元素按照一定的规则调换位置使这组数据按照递增或递减的顺序重新排列。例如数据库中有一个 “学生表”可以针对该表中的 “年龄” 字段进行排序那么这个待排序的字段就称为键key或者关键字。排序一般是为了让查找数据的效率变得更高。
这里涉及一个排序算法的稳定性问题。依旧以 “学生表” 为例假如表中数据如下 在上图所示的学生表中需要针对表中的 “年龄” 字段键按照某种排序算法进行递减或者递增排序。此时排序前张三和赵六的年龄都是 27 岁且张三这条记录位于赵六之前而在排序后如果张三这条记录依旧位于赵六之前那我们就说这种排序算法是 稳定 的如下图所示 反之如果排序后赵六这条记录位于张三之前那我们就说这种排序算法是不稳定的如下图所示 所以所谓 稳定的排序算法指的就是关键字相同的元素在排序后相对位置不变。针对排序算法的稳定性有两点说明
有些排序算法基于其实现的原理确实是无法做到稳定这种算法当然称为不稳定。有些排序算法是可以做到稳定的。但是如果稍微调整一下它的实现代码让它变得不稳定也是很容易的。当无法判断一个算法是否稳定时可以书写测试代码来进行稳定性测试。 内部排序和外部排序
在排序算法实现时虽然很多时候都是用整数进行举例但在真正的项目中往往要排序的并不是单纯的数字而是一组对象按照对象的某个关键字来排序所以排序的稳定性也是一个必须要考虑的问题。
想象一下两个用户在某个电子商城中购买了相同的商品他们的下单时间一个在前一个在后如果按照订单中商品价格排序那么这两张订单因为购买的是相同的商品价格相同所以排序后应该会相邻但因为采用稳定的排序算法所以排序后这两个订单依旧会按照原来下单的时间顺序排列。
根据在排序过程中待排序的数据是否全部被载入到内存中排序分为 内部排序内排序 和 外部排序外排序。
内部排序 是指在整个排序过程中待排序的所有数据记录都被载入到内存中。
外部排序 是指在整个排序过程中因为排序的数据太多比如大数据而不能同时载入到内存中导致整个的排序过程需要在内存和外存比如磁盘之间进行多次数据交换。因为磁盘和内存的读写速度相比往往要慢上数十甚至数百倍所以外部排序往往需要尽量减少磁盘的读写次数。
这些经典的内部排序算法有好多种每种排序算法都有相应的优缺点适合在不同的情况下使用。而这些算法的分类方式也有很多种比如按照数据操作方式来划分按照时间复杂度来划分等。
大部分经典排序算法都仅适用于顺序存储的线性表而不太适用于链式存储的线性表。对于大多数排序算法在排序过程中有两种基本操作
比较两个关键字的大小将记录从一个位置移动到另外一个位置
一般来说比较两个关键字大小是必须的但将记录从一个位置移动到另外一个位置也许可以通过一些变通的方式来实现从而提高排序算法的执行效率。而效率对于排序算法当然是最重要的。
2. 直接插入排序
所谓 插入类 排序就是向有序序列已经排好序的序列中依据关键字的比较结果寻找合适的位置插入新的记录构成新的有序序列直至所有记录插入完毕。
插入类排序可以细分为很多种每种之间的差别主要体现在插入位置的查找以及插入新数据导致原有数据的移动方面。我们先来看第一种。
直接插入排序 每次将一个记录按其关键字的大小插入到已经排好序的序列中直至全部记录插入完毕。这种排序方式将待排数据依次和数组中已经排好序的记录进行比较并确定自己的位置。
假设现在有 10 个元素的整型数组int arr[] {16, 1, 45, 23, 99, 2, 18, 67, 42, 10}现在我们希望对这个数组中的元素进行从小到大排序。
根据直接插入排序算法的思想我们首先认为数组中的第 1 个元素16包含在已经排好序的序列中。然后从数组中的第 2 个元素开始依次针对数组中的元素寻找合适的位置插入到已经排好序的序列中就行了。
所以就会有下面的操作步骤
先看 11 比 16 小所以 1 插入到 16 之前16 后移。这是因为已经排好序的序列中目前只有 16所以只需要将 16 后移数组 arr 目前的情形是{1, 16, 45, 23, 99, 2, 18, 67, 42, 10}。接着看 4545 比 1 和 16 都大所以 45 位置不动数组 arr 目前的情形是{1, 16, 45, 23, 99, 2, 18, 67, 42, 10}。接着看 2323 比 16 大但比 45 小所以 23 插入到 45 之前45 后移数组 arr 目前的情形是{1, 16, 23, 45, 99, 2, 18, 67, 42, 10}。接着看 9999 目前最大所以位置不动数组 arr 目前的情形是{1, 16, 23, 45, 99, 2, 18, 67, 42, 10}。接着看 22 比 1 大但比 16 小所以 2 插入到 16 之前16、23、45、99 依次后移数组 arr 目前的情形是{1, 2, 16, 23, 45, 99, 18, 67, 42, 10}。接着看 1818 比 16 大但比 23 小所以 18 插入到 23 之前23、45、99 依次后移数组 arr 目前的情形是{1, 2, 16, 18, 23, 45, 99, 67, 42, 10}。接着看 6767 比 45 大但比 99 小所以 67 插入到 99 之前99 后移数组 arr 目前的情形是{1, 2, 16, 18, 23, 45, 67, 99, 42, 10}。接着看 4242 比 23 大但比 45 小所以 42 插入到 45 之前45、67、99 依次后移数组 arr 目前的情形是{1, 2, 16, 18, 23, 42, 45, 67, 99, 10}。接着看 1010 比 2 大但比 16 小所以 10 插入到 16 之前16、18、23、42、45、67、99 依次后移数组 arr 目前的情形是{1, 2, 10, 16, 18, 23, 42, 45, 67, 99}。
以上就是直接插入排序算法的完整工作过程描述。
把一个无序数组 {16, 1, 45, 23, 99, 2, 18, 67, 42, 10} 最终变得有序 {1, 2, 10, 16, 18, 23, 42, 45, 67, 99}只需要从前向后遍历数组中的每个元素再为每个元素找到合适的位置就可以了。
3. 动图演示
这里我对 21, 3, 6, 17, 12, 1, 49, 10, 45, 43 这组数据进行直接插入排序每趟的排序过程如下 4. 代码实现
直接插入排序的实现代码有很多种比如有的资料会采用哨兵位的方式来实现。所谓哨兵位就是在数据结构中留出一个特殊位置避免在算法实现过程中引入临时变量。下面采用的是非哨兵的实现方式。
代码实现
//直接插入排序从小到大
templatetypename T
void InsertSort(T arr[], int len) {if (len 1) //不超过1个元素的数组没必要排序return;for (int i 1; i len; i) //从第2个元素下标为1开始比较{if (arr[i] arr[i - 1]){T temp arr[i]; //暂存arr[i]值防止后续移动元素时值被覆盖 int j;for (j i - 1; j 0 arr[j] temp; --j) //检查所有前面排好序的元素{arr[j 1] arr[j]; //所有大于temp的元素都向后移动}arr[j 1] temp; //复制数据到插入位置注意j因为被减了1这里加回来}}return;
} 在主函数中加入测试代码
int main()
{int arr[] {16, 1, 45, 23, 99, 2, 18, 67, 42, 10}; int len sizeof(arr) / sizeof(arr[0]); //数组中元素个数InsertSort(arr, len); //对数组元素进行直接插入排序//输出排好序的数组中元素内容cout 直接插入排序结果为;for (int i 0; i len; i) {cout arr[i] ;}cout endl;return 0;
}运行结果如下 5. 性能分析
从代码中可以看到直接插入排序实现比较简单。因为只有一些临时变量参与运算所以其空间复杂度为 O ( 1 ) O(1) O(1)对于时间复杂度方面主要来自于关键字比较和位置移动操作。对于具有 n 个元素的数组外循环次数是 n-1 次。
在最好的情况下即数组中元素已经是排好序的情况下外循环需要循环 n-1 次每次也只需要一次关键字比较if (arr[i] arr[i - 1]) 语句不需要进行任何元素移动所以最好情况时间复杂度为 O ( n ) O(n) O(n)。
在最坏情况下即数组中元素正好是逆序排列的情况下外循环需要循环 n-1 次每次循环都要比较和移动元素若干次所以最坏情况时间复杂度为 O ( n 2 ) O(n^2) O(n2)。平均情况时间复杂度也为 O ( n 2 ) O(n^2) O(n2)。
此外从代码中可以看到即使遇到了关键字相同的两条记录这两条记录的相对顺序也不会发生改变所以这个排序算法是稳定的。直接插入排序比较适合待排序记录数量比较少时的情形如果待排序记录的数量比较大就要考虑通过减少比较和移动数据次数对这种排序实现方法进行优化。
