【从头学数据结构和算法】选择排序及其优化(c++实现)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【从头学数据结构和算法】选择排序及其优化(c++实现),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2242字,纯文字阅读大概需要4分钟。
内容图文
c++实现的选择排序及其优化
普通选择排序
原理
每次从为排序区间选择一个最小的数据与前面的交换。
性质
- 时间复杂度
——最好、最坏和平均:O(n^2) - 空间复杂度
——O(1):原地排序 - 稳定性
——不稳定!!!
代码
template<typename T>
void select_sort0(T *a, int len) {
// 首先检查数据的合法性(TODO 不完善).
if (a == NULL || len <= 1) {
return;
}
int min = 0; // 当前待排序的数据中最小值的下标
int j = 0; // 内层循环(移动数据)计数变量
T temp = 0; // 用于数据交换的临时变量
// 对未排序区间进行遍历
for (int i = 0; i < len; ++i) {
min = i;
// 在未排序区间中查找最小值
for (j = i+1; j < len; ++j) {
if (a[j] < a[min]) {
// 更新最小值下标
min = j;
}
}
// 数据交换
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
优化1:一次找最大最小两值
原理
与普通的相同,只不过每次找最小和最大两值,然后交换两端的数据
性质
- 时间复杂度
——最好、最坏和平均:O(n^2)【耗时是普通方法的一半左右】 - 空间复杂度
——O(1):原地排序 - 稳定性
——不稳定!!!
代码
template<typename T>
void select_sort1(T *a, int len) {
// 首先检查数据的合法性(TODO 不完善).
if (a == NULL || len <= 1) {
return;
}
int min = 0; // 当前待排序的数据中最小值的下标
int max = 0; // 当前待排序的数据中最小值的下标
int j = 0; // 内层循环(移动数据)计数变量
int k = len; // 记录已排序空间中最大值的交换位
T temp = 0; // 用于数据交换的临时变量
// 对未排序区间进行遍历 (每次更新头尾的位置)
for (int i = 0; i < k; ++i,--k) {
min = i;
max = i;
// 在未排序区间中查找最小值和最小值
for (j = i+1; j < k; ++j) {
if (a[j] < a[min]) {
// 更新最小值下标
min = j;
}
if (a[j] > a[max]) {
// 更新最大值下标
max = j;
}
}
if (min != i) {
// 数据交换-最小值
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
if (max == i) {
// 防止之前的已经被换掉
max = min;
}
if (max != k-1) {
// 数据交换-最大值
temp = a[k-1];
a[k-1] = a[max];
a[max] = temp;
}
}
}
测试
以2000个整数进行测试,记录时间,同时assert是否与algorithm中sort结果相同。测试代码略,可见完整代码中。
测试结果时间(同时,assert未报错)如下图所示:
![在这里插入图片描述]
可见,优化效率提升基本接近于2倍,而且选择排序本身也比冒泡排序要快(详情见[【从头学数据结构和算法】冒泡排序及其优化(c++实现)]
完整代码
排序及优化及测试 完整代码在:
https://github.com/zhangdanzhu/basic_data-structure_algorithm/blob/master/sort/cpp/selection_sort.cpp
内容总结
以上是互联网集市为您收集整理的【从头学数据结构和算法】选择排序及其优化(c++实现)全部内容,希望文章能够帮你解决【从头学数据结构和算法】选择排序及其优化(c++实现)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。