c++数据结构算法复习基础--10--普通排序算法-冒泡排序-选择排序-插入排序-希尔排序

🕗 发布于 2024-11-11 11:20 算法排序算法 数据结构

普通排序算法

各排序性能对比：
在这里插入图片描述

插入排序的效率最好，尤其是在数据已经趋于有序的情况下，采用插入排序效率最高。

一般中等数据量的排序都用希尔排序，选择合适的增量序列，效率就已经不错了，
如果数据量比较大，可以选择高级的排序算法，如快速排序。也可以多种排序结合使用。

稳定性：在原始的数据序列中，相同元素，经过排序后，他们的前后顺序并没有改变，否则，称之为不稳定的排序。
稳定性对于单个数据无影响，但对于
例如数据5_5，排序过后为 5_6_7_5。两个两个5的位置改变了，但前后顺序并没有变动，这次排序是稳定的排序。
（虽然这两个值一样，但对于有关联的数据和C++的map映射表键值对有关联的数据来说，假设原始数据5_5，其中前一个五映射数据aaa,后一个映射数据bbb。
在原始的序列当作，两个5存在映射关系，这里将左边的叫做k，右边的叫做value，当最开始在原始序列里面放置数据的时候，如果建相同，这里表现为都为5，是按照他们的字典顺序进行排列，这里体现为aaa在前面，bbb在后面。这样一查看筛选5,用5筛选k,对应的value都是按字典序排好的，如果是个稳定的排序，那么5对应的value的前后位置，还是按照对应的字典序排序的。）
在这里插入图片描述

1、冒泡排序算法

理论

在这里插入图片描述

特点

相邻元素两两相比，把值大（小）的元素往下交换。

缺点

冒泡排序是所有排序算法效率最低的，原因在于，数据交换的次数太多！！

稳定性分析

在原始的数据序列中，相同元素，经过排序后，他们的前后顺序并没有改变，否则，称之为不稳定的排序。

代码

#include<iostream>
#include<stdlib.h> //包含随机数函数srand
#include<time.h> //需要用time作为随机数种子

using namespace std;

//冒泡排序算法
void BubbleSort(int arr[], int size)
{
for (int i = 0; i < size; i++)//趟数
{
//一趟的处理
//进行优化，如果某趟没有进行如何的数据交换，那么说明数据已经有序
bool flag = false;
for (int j = 0; j < size - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flag = true;
}

}
if( !flag )
//if (flag = false)
{
//如果没有做任何的数据交换，那么说明数据已经有序了
return;
}
}
}

int main()
{
int arr[10];
srand(time(NULL));

for (int i = 0; i < 10; i++)
{
arr[i] = rand() % 100 + 1;
}

for (int v : arr)
{
cout << v << "  ";
}
cout << endl;

BubbleSort(arr, sizeof(arr) / sizeof(arr[0]));

for (int v : arr)
{
cout << v << "  ";
}
cout << endl;

return 0;
}

测试

在这里插入图片描述

2、选择排序

在这里插入图片描述

特点

每次在剩下的元素中选择值最小（大）的元素，和当前元素进行交换。

缺点

相比于冒泡排序，交换的次数少了，但是比较的次数依旧很多。

代码实现

#include<iostream>
#include<stdlib.h> //包含随机数函数srand
#include<time.h> //需要用time作为随机数种子

using namespace std;

//选择排序算法  时间复杂度O(n^2) 空间复杂度O(n)
void ChoiceSort(int arr[], int size) //O(n^2)
{
for (int i = 0; i < size-1; i++)//O(n)
{
int min = arr[i];
int k = i;
for (int j = i+1; j < size; j++) //O(n)
{
if (arr[j] < min)
{
min = arr[j];
k = j;
}
}
//找到后面剩余序列中的最小值，和开始位置的值进行交换
if (k != i)
{
int tmp = arr[i];
arr[i] = arr[k];
arr[k] = tmp;
}
}
}

int main()
{
int arr[10];
srand(time(NULL));

for (int i = 0; i < 10; i++)
{
arr[i] = rand() % 100 + 1;
}

for (int v : arr)
{
cout << v << "  ";
}
cout << endl;

ChoiceSort(arr, sizeof(arr) / sizeof(arr[0]));

for (int v : arr)
{
cout << v << "  ";
}
cout << endl;

return 0;
}

测试

在这里插入图片描述

3、插入排序

在这里插入图片描述

特点

从第二个元素开始（默认第一个元素有序），把前面的元素序列当作已经有序，然后找合适的位置插入。

优点

在数据越趋于有序的情况下，插入排序是所有排序算法中最高的。
在基础排序算法中，插入排序是普通排序里面效率最高的排序算法，插入排序>冒泡排序&选择排序。
不仅仅没有交换，而且比较的次数也少。

代码实现

//插入排序  
//时间复杂度: 最坏、平均 O(n^2)   最好O(n)   空间：O(1)   稳定性：稳定的
void InsertSort(int arr[], int size)
{
for (int i = 1; i < size; i++)//O(n)
{
int val = arr[i];
int j = i - 1;
for (; j >= 0; j--) //O(n)
{
if (arr[j] <= val)
{
break;
}
arr[j + 1] = arr[j];
}
//val -> j+1
arr[j + 1] = val;
}
//error  这样产生了交换是不是插入排序
/*for (int i = 0; i < size - 1; i++)
{
for (int j = i; j >= 0; j--)
{
if (arr[j + 1] >= arr[j])
{
break;
}
else
{
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}*/
}

测试

int main()
{
int arr[10];
srand(time(NULL));

for (int i = 0; i < 10; i++)
{
arr[i] = rand() % 100 + 1;
}

for (int v : arr)
{
cout << v << "  ";
}
cout << endl;

InsertSort(arr, sizeof(arr) / sizeof(arr[0]));

for (int v : arr)
{
cout << v << "  ";
}
cout << endl;

return 0;
}

在这里插入图片描述

4、希尔排序

特点

可以看作是多路的插入排序，分组的数据越趋于有序，整体上的数据也越趋于有序，插入排序效率完美体现。

前要：对于插入排序，如果数据趋于有序，那么插入排序是所有算法中，效率最高的排序算法。
希尔可以看作是对插入排序的优化，尽可能，先从全局的角度，把数据调整成区域有序，让全局的数据越来越有，即尽最快速度让数据变成趋于有序的，再统一进行一次插入排序。

实现思路

对数据进行分组插入排序
如下数组
在这里插入图片描述

int gap = size/2;   //10/2 = 5

注意：gap的取值，可以根据实际数据情况来定。

将数据分成五组，对每个组内的数据进行插入排序。
在这里插入图片描述
排序后

此时，数据并未有序，但相比较于这次比较前，整体数据更趋于有序。
gap进一步进行缩小。gap = gap/2; //5/2 = 2
此时的数据就变成下图的情况，分成了两组，对每组进行插入排序。

排序后：
在这里插入图片描述
gap进一步进行缩小。gap = gap/2; //2/2 = 1

此时，gap==1；对数据进行最后一遍插入排序。

代码实现

//希尔排序
void ShellSort(int arr[], int size)
{
for (int gap = size / 2; gap > 0; gap /= 2)  //O(logn)
{
for (int i = gap; i < size; i++)  //O(n)
{
int val = arr[i];
int j = i - gap;
for (; j >= 0; j-=gap)    //O(n)
{
if (arr[j] <= val)
{
break;
}
arr[j + gap] = arr[j];
}
arr[j + gap] = val;
}
}
}

测试

int main()
{
int arr[10];
srand(time(NULL));

for (int i = 0; i < 10; i++)
{
arr[i] = rand() % 100 + 1;
}

for (int v : arr)
{
cout << v << "  ";
}
cout << endl;

ShellSort(arr, sizeof(arr) / sizeof(arr[0]));

for (int v : arr)
{
cout << v << "  ";
}
cout << endl;

return 0;
}

在这里插入图片描述

冒泡&选择&插入&希尔算法性能统计

代码实现

#include<iostream>
#include<stdlib.h> //包含随机数函数srand
#include<time.h> //需要用time作为随机数种子
#include<string>
#include<stack>

using namespace std;

//冒泡排序算法
void BubbleSort(int arr[], int size)
{
for (int i = 0; i < size; i++)//趟数
{
//一趟的处理
//进行优化，如果某趟没有进行如何的数据交换，那么说明数据已经有序
bool flag = false;
for (int j = 0; j < size - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flag = true;
}

}
if( !flag )
//if (flag = false)
{
//如果没有做任何的数据交换，那么说明数据已经有序了
return;
}
}
}

//选择排序算法
void ChoiceSort(int arr[], int size)
{
for (int i = 0; i < size-1; i++)
{
int min = arr[i];
int k = i;
for (int j = i+1; j < size; j++)
{
if (arr[j] < min)
{
min = arr[j];
k = j;
}
}

if (k != i)
{
int tmp = arr[i];
arr[i] = arr[k];
arr[k] = tmp;
}
}
}

//插入排序  
//时间复杂度: 最坏、平均 O(n^2)   最好O(n)   空间：O(1)   稳定性：稳定的
void InsertSort(int arr[], int size)
{
for (int i = 1; i < size; i++)//O(n)
{
int val = arr[i];
int j = i - 1;
for (; j >= 0; j--) //O(n)
{
if (arr[j] <= val)
{
break;
}
arr[j + 1] = arr[j];
}
//val -> j+1
arr[j + 1] = val;
}
//这样产生了交换是不是插入排序
/*for (int i = 0; i < size - 1; i++)
{
for (int j = i; j >= 0; j--)
{
if (arr[j + 1] >= arr[j])
{
break;
}
else
{
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}*/
}

//希尔排序
void ShellSort(int arr[], int size)
{
for (int gap = size / 2; gap > 0; gap /= 2)  //O(logn)
{
for (int i = gap; i < size; i++)  //O(n)
{
int val = arr[i];
int j = i - gap;
for (; j >= 0; j-=gap)    //O(n)
{
if (arr[j] <= val)
{
break;
}
arr[j + gap] = arr[j];
}
arr[j + gap] = val;
}
}
}

int main()
{
const int COUNT = 10000;
int* arr = new int[COUNT];
int* brr = new int[COUNT];
int* crr = new int[COUNT];
int* drr = new int[COUNT];

srand(time(NULL));

for (int i = 0; i < COUNT; i++)
{
int val = rand() % COUNT;
arr[i] = val;
brr[i] = val;
crr[i] = val;
drr[i] = val;
}

clock_t begin,end;

begin = clock();
BubbleSort(arr, COUNT);
end = clock();
cout << "BubbleSort spend: " << (end - begin) * 1.0 / CLOCKS_PER_SEC << "s" << endl;

begin = clock();
ChoiceSort(brr, COUNT);
end = clock();
cout << "ChoiceSort spend: " << (end - begin) * 1.0 / CLOCKS_PER_SEC << "s" << endl;

begin = clock();
InsertSort(crr, COUNT);
end = clock();
cout << "InsertSort spend: " << (end - begin) * 1.0 / CLOCKS_PER_SEC << "s" << endl;

begin = clock();
ShellSort(drr, COUNT);
end = clock();
cout << "ShellSort spend: " << (end - begin) * 1.0 / CLOCKS_PER_SEC << "s" << endl;

}

#if 0
int main()
{
int arr[10];
srand(time(NULL));

for (int i = 0; i < 10; i++)
{
arr[i] = rand() % 100 + 1;
}

for (int v : arr)
{
cout << v << "  ";
}
cout << endl;

//BubbleSort(arr, sizeof(arr) / sizeof(arr[0]));
//ChoiceSort(arr, sizeof(arr) / sizeof(arr[0]));
//InsertSort(arr, sizeof(arr) / sizeof(arr[0]));
ShellSort(arr, sizeof(arr) / sizeof(arr[0]));

for (int v : arr)
{
cout << v << "  ";
}
cout << endl;

return 0;
}
# endif

运行结果

数据量为10000时：
在这里插入图片描述
数据量为10w时：

原文地址：https://blog.csdn.net/kyrie_sakura/article/details/143493153

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：PRD2012学习笔记
下一篇：零基础上手WebGIS+智慧校园实例（1）【html by js】

spark.default.parallelism 在什么时候起作用，与spark.sql.shuffle.partitions有什么异同点？
异同主要影响 RDD 的初始并行度，而则专门控制 Spark SQL 中的 Shuffle 分区数。前者在非 SQL 的 RDD 操作中起作用，后者则仅对 SQL 或 DataFrame API 中的
阅读更多2024-11-15
QT 控件大小的自适应（重写resizeEvent方法）
【代码】QT 控件大小的自适应（重写resizeEvent方法）
阅读更多2024-11-15
【每日 C/C++ 问题】
当进程需要访问某个页面时，操作系统会将其加载到物理内存中并更新进程的页表，如果物理内存不足，则可能需要将某些不常用的页面置换出来，供其他进程使用。如果程序要访问虚拟地址的时候，由操作系统转换成不同的物
阅读更多2024-11-15
Linux 批量配置互信
linux服务器批量配置互信
阅读更多2024-11-15
数据结构-布隆过滤器和可逆布隆过滤器
在解决缓存穿透问题时，往往会用到一种高效的数据结构-布隆过滤器，其能够快速过滤掉不存在的非法请求，但其也存在一定的误差，即少量不存在的请求也会被放过去。本文对布隆过滤器家族进行介绍，除了常见的普通布隆
阅读更多2024-11-15
【数据结构】AVL树
本文主要介绍了数据结构中的AVL树
阅读更多2024-11-15
Elasticsearch 重建索引&数据迁移
ES 索引不支持直接修改某个字段类型，如果该索引中已经存在数据。如果要修改字段类型，只能通过重建索引+数据迁移的方式来实现该效果。Index Management 页面找到新建的临时索引，点击名称超链
阅读更多2024-11-15
1300. 转变数组后最接近目标值的数组和
给你一个整数数组 arr 和一个目标值 target ，请你返回一个整数 value ，使得将数组中所有大于 value 的值变成 value 后，数组的和最接近 target （最接近表示两者之差
阅读更多2024-11-15
【AI日记】24.11.14 复习和准备 RAG 项目 | JavaScript RAG Web Apps with LlamaIndex
复习和准备 RAG 项目 | JavaScript RAG Web Apps with LlamaIndex
阅读更多2024-11-15
VUE 实现公告无缝循环滚动
VUE 实现公告无缝向左滚动，当公告的宽度大于当前视图宽度的时候再向左滚动，否则不滚动，当鼠标移入时停止滚动，移开时继续滚动，公告获取后台返回的一个数组，将链接转换为HTML。
阅读更多2024-11-15

c++数据结构算法复习基础--10--普通排序算法-冒泡排序-选择排序-插入排序-希尔排序

普通排序算法

1、冒泡排序算法

理论

特点

缺点

稳定性分析

代码

测试

2、选择排序

特点

缺点

代码实现

测试

3、插入排序

特点

优点

代码实现

测试

4、希尔排序

特点

实现思路

代码实现

测试

冒泡&选择&插入&希尔算法性能统计

代码实现

运行结果

相关文章