环保网站建设说明书,站长统计app下载免费,做网站需要注意的点,个人做购物商城网站会罚款吗目录
本章内容如下 一:插入排序 1.1插入排序 1.2希尔排序
二#xff1a;选择排序 2.1选择排序 三:交换排序 3.1冒泡排序 一:插入排序 1.1直接插入排序 说到排序#xff0c;其实在我们生活中非常常见…目录
本章内容如下 一:插入排序 1.1插入排序 1.2希尔排序
二选择排序 2.1选择排序 三:交换排序 3.1冒泡排序 一:插入排序 1.1直接插入排序 说到排序其实在我们生活中非常常见比如当我们需要在网上买东西的时候 我们可以按照价格排序也可以按照销量进行排序所以对于我们来说学习排序这个数据结构是非常重要的在本文中我会尽可能按照我的理解将目录中的排序给将清楚。 下面就是我在一个网购网站中进行截取的图片我们可以看到排序无处不见。 现在让我们进入排序的讲解 首先我们讲解的是插入排序 首先我们来认识一下插入排序这个算法插入排序顾名思义就是插入到前(n-1)个有序 数中这就像我们生活中经常玩扑克牌的时候的思想我们玩扑克牌的时候有一种摸牌 思路就是将第一张牌有序然后让后面的牌进行插入使得我们的牌一直有序。 下面我通过一群数字来进行讲解 比如说我们的数组中的值为 9 4 7 2 5 3 1 6 8 这9个数字那么我们如何使得这个数组有序呢 我们通过画图来进行讲解 很明显我们对于插入排序的思想 思路 假设我们要插入第n个数我们需要保证前n-1个数有序然后再进行插入没插入一个数我们就要将该数前面的数与要插入的数经行比较如果大于这个要插入的数那我们就将他玩后面进行移动就可以了。 void InsertSort(int* a, int n)
{//使前n-1个数先有序然后插入第n个数for (int i 0; i n-1; i){int end i;int tmp a[end 1];//一趟插入排序的思路while (end 0){if (tmp a[end]){a[end 1] a[end];end--;}else{break;}}a[end 1] tmp;}
} 现在让我们来算一下插入排序的时间复杂度与空间复杂度吧。 时间复杂度最好O(N), 最坏O(n^2) 首先我们不难发现它的空间复杂度为O(1) 最坏时间复杂度:O(n^2),当一个数组为逆序的时候就是插入排序的最坏的 情况在这种情况下我们一共有N个数字插入一个数我们就需要将前面的 数字全部像后面进行移动一次然后在插入所以总共来说就是N*N. 最好的情况是什么呢最好的情况当然是当数组顺序有序的时候每一个数 只要插入就行了而不需要移动元素插入的时间复杂度为O(1),所以总共 的时间复杂度为O(1*N)O(N).
1.2希尔排序 其实希尔排序的本质也是插入排序希尔排序只是在插入排序上进行的一个优化的 排序我们在上面的插入排序中不难发现当数组有序的时候我们的插入排序的 时间复杂度是非常好的为O(N),而我们的希尔大佬就是看到了这个特点 所以就在插入排序中进行了优化才有了我们著名的一个排序算法叫做希尔排序。 希尔排序的思想是什么呢 其实希尔排序的思想其实也非常简单 先预排序在直接插入排序。 1先对数组进行多组预排序使得数组中的一些子数组接近有序。 2在对数组进行插入排序。 我们用图来讲解一组预排序 我们不难看出在进行一组预排序完成后我们的数组相对于原来的数组就接近有序了 且gap越小的时候我们的数组越接近有序当gap1的时候我们的我们的预排序 就是直接插入排序。 代码如下
//版本一
void ShellSort(int* a, int n)
{int k 0;int gap n;while(gap!1){gap / 2;//最后一次gap一定等于1//多组预排序也就是我们图中红黑绿三组进行预排序for (int j 0; j gap; j){//一组预排序操作for (int i 0; i n - gap; i gap){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}}}c
版本二有点像优化的版本
void ShellSort(int* a, int n)
{int k 0;int gap n;while(gap!1){gapgap/3 1;//最后一次gap一定等于1 //间距为gap的值从前往后直接进行交换for (int i 0; i n - gap; i ){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}} 希尔排序的时间复杂度是多少呢 其实书上也没有给出明确的证明有很多种不同的看法,但是差不多是O(N^1.3)这个我也不会证明需要涉及到高阶的数学。 大家如果有兴趣的话可以去证明一下。 到这里我们的插入排序就讲解完毕了希尔排序需要大家自行的去画图多思考。 -------- 二:选择排序
其实我们的选择排序有两种一种是直接选择排序也是我们讲解的排序还有一种就是堆排序而堆排序我们之前已经讲解过了如果你还没看的话建议先直接去补一下。 堆排序链接https://blog.csdn.net/2201_75964502/article/details/133017420?spm1001.2014.3001.5501 在这里我们主要讲解选择排序的优化版本就是我们遍历一边数组选出两个值 一个最大值我们往后面插入还有一个最小值玩前面插入。 直到我们将数组排序好就可以了。 思想遍历一遍选最大值与最小值然后排序就行了。 图这里只写了1个步骤 代码如下
void SelectSort(int* a, int n)
{int begin 0;int end n-1;while (begin end){int maxi begin;int mini begin;for(int i begin;iend;i){//选最小的下标if (a[mini] a[i]){mini i;}//选最大的下标if (a[maxi] a[i]){maxi i;}}Swap(a[begin], a[mini]);//防止最大值就在begin处if (begin maxi){maxi mini;}Swap(a[maxi], a[end]);begin;end--;}
} 选择排序的时间复杂度O(^2) 因为它的时间复杂度算法是一个等差数列(n)(n-2)_......20 每次都需要遍历数组选两个值固定的 所以选择排序是很稳定的。 ------- 三交换排序 其实我们的交换排序也有两种一种是快速排序另外一种就是我们本章所讲解的 冒泡排序而我们的快速排序由于有几种方法且有点难所以我会独自整理成一篇 文章来进行讲解我们的快速排序。 其实冒泡排序可能是我们见过最多的一种排序它的思想并不难理解 冒泡排序的思想是什么呢 思想 遍历一遍数组两两相邻的元素进行比较将数组中最大元素的值给冒到最 后去一直遍历直到数组变成有序的数组 代码如下 void BubbleSort(int* a, int n)
{int i 0;//一共冒泡几趟for (int i 0; i n-1; i){int exchange 1;//一趟内部for (int j 0; j n-i-1; j){if (a[j] a[j 1]){exchange 0;Swap(a[j], a[j 1]);}}if (exchange 1){//说明原数组有序,就不需要进行排序了break;}}} 冒泡排序的时间复杂度O(N^2) 它非常稳定。因为时间复杂度是固定的 感谢大家的观看如果你觉得对你有帮助的话可以给博主一个赞哦
