当插入第i(i>=1)个元素时,前面的array[0],array[1],…,array[i-1]已经排好序,此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较,找到插入位置即将array[i]插入,原来位置上的元素顺序后移
具体流程在图中已经画出
插入排序在最坏的情况的时间复杂度是多少呢?
最坏的情况很显然是逆序的情况,要想有序,第二个数需要移动1次,第三个数需要移动2次…,第n个数需要移动(n - 1)次,则由等差数列公式可得 1 + 2 + 3 + …+ (n - 1) = (n - 1)n / 2,因此最坏情况下的时间复杂度为O(N^2)
插入排序在最好的情况下时间复杂度是多少呢?
最好的情况很显然是有序的情况,只需要遍历一次原数组即可,不需要进行移动操作,因此最好的情况时间复杂度为O(N)
插入排序的空间复杂度 : O(1) , 插入排序不需要额外的空间,可在原数组上直接进行修改
插入排序的稳定性 : 稳定,插入排序是可以做到排序之后不改变相同元素的相对顺序的
插入排序的实现过程如下
void InsertSort(int* a,int n)
{
int i = 0;
for(i = 0;i < n - 1;i++)
{
int end = i,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),同理,当数据接近逆序的时候,时间复杂度也可以近似的认为是O(N^2)
基于这个原因,希尔对插入排序进行了优化,毕竟插入排序在逆序的情况下时间复杂度为O(N^2) , 这显然不是我们所想要看到的,于是希尔就想到了对数据进行预排序的操作,经过预排序后的数据接近有序,再对其进行插入排序,这时插入排序的时间复杂度为O(N),那么预排序的时间复杂度如果小于O(N*N),就可以对插入排序达到一定的优化效果
希尔排序的思想为 : 对数据先进行预排序,使数据接近有序后,再进行插入排序
预排序是对数据进行分组插入排序,图示如下
希尔排序的实现过程如下 :
void ShellSort(int* a,int n)
{
int gap = n;
while(gap > 1)
{
// + 1 是为了最后让 gap 能取到 1,进行直接插入排序
gap = (gap / 3) + 1;
int i = 0;
for(i = 0;i < n - gap;i++)
{
int end = i,tmp = a[end + gap];
while(end >= 0)
{
if(tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
可以看到刚开始gap较大时,数据较无序,数据之间的移动较快,大的数被较快的向右边移动,小的数被较快的向左边移动,经过这样移动过后,数据逐渐趋近于有序
随着gap的减小,数据越来越有序,数据间的移动较慢,大的数被较慢的向右边移动,小的数被较慢的向左边移动
最后我们对接近有序的数据进行一次直接插入排序,达到有序的目的
希尔排序的时间复杂度 : 由于希尔排序的时间复杂度取决于gap的取值,所以我们在这里以gap = (gap / 3) + 1 为例分析,刚开始 gap 较大时,数据移动的较快,可以认为单次插入排序为O(1),一共进行(n - n / 3) = 2 / 3 * n 次,即O(N),到最后 gap = 1 进行直接插入排序为O(N)
gap 由 n/3 到 1 共循环 log3(N),故总时间复杂度为 O(N * log3(N))
希尔排序的空间复杂度 : O(1),希尔排序不需要额外的空间,可在原数组上直接进行修改
希尔排序的稳定性 : 不稳定,由图示可以看到,在进行第一趟排序时,两个5被分到了不同的组,第一趟排完之后两个5的相对位置已经改变了
快速排序的思想 : 选中一个数为基准数(一般为最左边或最右边的数),通过一系列的操作使得基准数到达它最终的位置,即基准数左边的数比它小,右边的数比它大
将区间按照基准值划分为左右两半部分的常见方式有:
(1). hoare版本
(2). 挖坑法
(3). 前后指针版本
(1).hoare版本
思想 : 假设选中最左边的数为基准数,left 指针指向最左边,right指针指向最右边,right指针先出发去寻找比基准数小的值(在移动的过程中,left < right) ,然后left指针出发去找比基准数大的值(在移动的过程中,left < right),交换left指针和right指针所指向的值,直到left == right,最后交换left指针所指向的值和基准数
hoare版本实现
void Swap(int* e1,int* e2)
{
int tmp = *e1;
*e1 = *e2;
*e2 = tmp;
}
int hoare(int* a,int left,int right)
{
int keyi = left;
while(left < right)
{
while(left < right && a[right] >= a[keyi])
right--;
while(left < right && a[left] <= a[keyi])
left++;
Swap(&a[left],&a[right]);
}
Swap(&a[left],&a[keyi]);
return left;
}
(2).挖坑法
思想 : 假设选中最左边的数为基准数,left 指针指向最左边,right指针指向最右边,用临时变量tmp保存基准数,right出发去找比基准数小的数,将right所指向的值赋值给left所指向的值,然后left出发去找比基准数大的数,将left所指向的值赋给right所指向的值
挖坑法实现
int hole(int* a,int left,int right)
{
int tmp = a[left];
while(left < right)
{
while(left < right && a[right] >= tmp)
right--;
a[left] = a[right];
while(left < right && a[left] <= tmp)
left++;
a[right] = a[left];
}
a[left] = tmp;
return left;
}
(3).前后指针法
思路 : 假设选中最左边的数为基准数,prev = left, cur = left + 1,cur去找比基准数小的数,和a[++prev]交换,直到cur走到末尾,最后交换a[prev]和a[left]
前后指针实现
int FBP(int* a,int left,int right)
{
int keyi = left,prev = left,cur = left + 1;
for(cur = left + 1;cur <= right;cur++)
{
if(a[cur] < a[keyi])
{
++prev;
Swap(&a[cur],&a[prev]);
}
}
Swap(&a[prev],&a[keyi]);
return prev;
}
经过上面单趟快速排序过后,将我们选中的基准数移动到了正确的位置,然后在基准数的左右区间采取同样的方法进行快速排序
快速排序递归实现
void QuickSort(int* a,int left,int right)
{
// 区间只有一个值或区间不存在
if(left >= right)
return;
int keyi = FBP(a,left,right);
// 递归左区间
QuickSort(a,left,keyi - 1);
// 递归右区间
QuickSort(a,keyi + 1,right);
}
快速排序非递归实现
void QuickNonR(int* a,int begin,int end)
{
Stack st;
StackInit(&st);
// 将初始的begin和end入栈
StackPush(&st, begin);
StackPush(&st, end);
while (!StackEmpty(&st))
{
// 得到区间的右端点
int right = StackTop(&st);
StackPop(&st);
// 得到区间的左端点
int left = StackTop(&st);
StackPop(&st);
// 对该段区间进行单趟快排
int keyi = FBP(a, left, right);
// 将左区间的左右端点入栈
if (left < keyi - 1)
{
StackPush(&st, left);
StackPush(&st,keyi - 1);
}
// 将右区间的左右端点入栈
if (right > keyi + 1)
{
StackPush(&st, keyi + 1);
StackPush(&st, right);
}
}
// 销毁栈
StackDestroy(&st);
}
接下来我们来分析快速排序的时间复杂度
在最好的情况下,我们所选中的基准数都被移动到区间中间的位置,即O(N*logN)
在最坏的情况下,若我们想要排升序,原数据正好为升序,此时时间复杂度为O(N^2)
在最坏的情况下,时间复杂度为O(N^2),这不是我们所想要看到的,我们可以对其进行一些优化,最坏的情况发生的原因是因为我们选择的基准数是最大的或者是最小的,基于这个原因,我们可以在a[left],a[mid],a[right]三数之中选择一个并不是最大的也不是最小的作为我们的基准数,做完优化后,我们可以发现原本最坏的情况在优化过后变为了最好的情况
我们可以将上面讲的三种单趟排序的方法都加上三数取中法来进行优化
三数取中的实现
// 三数取中,选择a[left],a[right],a[mid]中既不是最大的,也不是最小的数
int MiddleIndex(int* a, int left, int right)
{
int mid = left + (right - left) / 2;
if (a[left] < a[mid])
{
// a[left] < a[mid] < a[right]
if (a[mid] < a[right])
return mid;
// a[mid] > a[left] && a[mid] > a[right]
else if (a[left] < a[right])
return right;
else
return left;
}
else
{
// a[mid] > a[left] > a[right]
if (a[mid] > a[right])
return mid;
// a[mid] > a[left] && a[right] > a[left]
else if (a[left] < a[right])
return left;
else
return right;
}
}
快速排序的空间复杂度 : O(logn) ~ O(n),在递归的过程中会消耗栈空间
快速排序的稳定性 : 不稳定,在排序的过程中可能会使相同元素的相对顺序发生改变
思路 : 将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再将有序的子序列进行合并
我们需要将两个已经有序的子序列合并成一个有序序列,比如上图中的最后一次合并,要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列,合并为最终序列[1,2,3,4,5,6,7,8],来看下实现步骤。
归并排序递归实现
void MergeSort(int* a,int* tmp,int left,int right)
{
if(left >= right)
return;
int mid = left + (right - left) / 2;
// 分解
MergeSort(a,tmp,left,mid);
MergeSort(a,tmp,mid + 1,right);
int i = left;
// 归并
int begin1 = left,end1 = mid,begin2 = mid + 1,end2 = right;
while(begin1 <= end1 && begin2 <= end2)
{
// 得到a[begin1]和a[begin2]中较小的数,再移动较小的值
if (a[begin1] < a[begin2])
tmp[i++] = a[begin1++];
else
tmp[i++] = a[begin2++];
}
// 将[begin1,end1]剩余的数放到tmp数组中
while (begin1 <= end1)
tmp[i++] = a[begin1++];
// 将[begin1,end1]剩余的数放到tmp数组中
while (begin2 <= end2)
tmp[i++] = a[begin2++];
// 将tmp数组的值拷贝到a数组中
memcpy(a, tmp, sizeof(int) * i);
}
归并排序非递归实现
思路 : 先将数据一个一个(gap)进行合并, 再两个两个(gap)进行合并,直到 gap < n 为止
其中在合并过程中最后有三种情况需要注意一下 :
(1). 第一组的数据不够gap个,不用再合并了
(2). 第一组的数据够 gap 个,但第二个区间不存在,不用再合并了
(3). 第一组和第二组区间都存在,但第二组区间数据不够 gap 个.
void _MergeSort(int* a,int* tmp,int begin1,int end1,int begin2,int end2)
{
int i = begin1;
while(begin1 <= end1 && begin2 <= end2)
{
// 得到a[begin1]和a[begin2]中较小的数,再移动较小的值
if (a[begin1] < a[begin2])
tmp[i++] = a[begin1++];
else
tmp[i++] = a[begin2++];
}
// 将[begin1,end1]剩余的数放到tmp数组中
while (begin1 <= end1)
tmp[i++] = a[begin1++];
// 将[begin1,end1]剩余的数放到tmp数组中
while (begin2 <= end2)
tmp[i++] = a[begin2++];
// 将tmp数组的值拷贝到a数组中
memcpy(a, tmp, sizeof(int) * i);
}
void MergeSortNonR(int* a,int* tmp,int n)
{
int gap = 1;
while(gap < n)
{
int i = 0;
for(i = 0;i < n;i += 2 * gap)
{
int begin1 = i,end1 = i + gap - 1,begin2 = i + gap,end2 = i + 2 * gap - 1;
// 第二个区间不存在
if(begin2 >= n)
break;
// 第二个区间数据不够gap个,修正区间范围
if(end2 >= n)
end2 = n - 1;
_MergeSort(a,tmp,begin1,end1,begin2,end2);
}
gap *= 2;
}
}
归并排序的时间复杂度 : O(NlogN),归并排序每层复杂度为O(N),一共递归 logN 层,故时间复杂度为O(NlogN)
归并排序空间复杂度 : O(N),归并排序需要使用额外的一个数组
归并排序的稳定性 : 稳定
由归并排序也引出了常见的内排序和外排序问题
内排序:数据量少,可以放到内存中进行排序。
外排序:数据量大,内存中放不下,数据只能放到磁盘文件中,需要排序
假设现在有10亿个整数存放在文件A中,我们可以使用的内存为 512M,怎样对这10亿个整数进行排序呢?
(1). 10亿个整数大约占4GB的内存,而我们可使用的内存只有512M,因此我们每次从文件A中读取 1/8 到内存中,在内存中对这1/8 的数据进行内排序(这里的排序不能选用归并排序,因为归并排序的空间复杂度为O(N)),将排好序的数据写入到一个新的文件中,最终我们就可以得到8个分别有序的小文件,每个文件的大小为512M
(2).对这8个小文件进行归并排序,归并成4个文件(每个文件大小为1GB),归并成2个文件(每个文件为2GB),归并成1个文件(文件大小为4GB)
原理 :
(1). 统计相同元素出现次数
(2). 根据统计的结果将序列回收到原来的序列中
第一种实现 : 绝对映射
绝对映射的缺点也非常明显 :
(1).当数组的最大值很大时,我们所开辟的数组大小也会非常的大
(2).计数排序只能用来排序整数
优化 : 相对映射
void CountSort(int* a,int n)
{
// 选择出最大值,最小值
int i = 0,min = a[0],max = a[0];
for(i = 0;i < n;i++)
{
if(a[i] > max)
max = a[i];
if(a[i] < min)
min = a[i];
}
int range = max - min + 1;
int* count = (int*)malloc(sizeof(int) * range);
memset(count,0,sizeof(int) * range);
for(i = 0;i < n;i++)
{
count[a[i] -min]++;
}
int j = 0;
for(i = 0;i < range;i++)
{
while(count[i]--)
{
a[j++] = i + min;
}
}
}
计数排序的时间复杂度 : O(MAX(N,range))
计数排序的空间复杂度 : O(range)
计数排序稳定性 : 稳定
综上所述 : 计数排序在数据范围集中时,效率很高,但是适用范围及场景有限
文章浏览阅读645次。这个肯定是末尾的IDAT了,因为IDAT必须要满了才会开始一下个IDAT,这个明显就是末尾的IDAT了。,对应下面的create_head()代码。,对应下面的create_tail()代码。不要考虑爆破,我已经试了一下,太多情况了。题目来源:UNCTF。_攻防世界困难模式攻略图文
文章浏览阅读2.9k次,点赞3次,收藏10次。偶尔会用到,记录、分享。1. 数据库导出1.1 切换到dmdba用户su - dmdba1.2 进入达梦数据库安装路径的bin目录,执行导库操作 导出语句:./dexp cwy_init/[email protected]:5236 file=cwy_init.dmp log=cwy_init_exp.log 注释: cwy_init/init_123..._达梦数据库导入导出
文章浏览阅读1.9k次。1. 在官网上下载KindEditor文件,可以删掉不需要要到的jsp,asp,asp.net和php文件夹。接着把文件夹放到项目文件目录下。2. 修改html文件,在页面引入js文件:<script type="text/javascript" src="./kindeditor/kindeditor-all.js"></script><script type="text/javascript" src="./kindeditor/lang/zh-CN.js"_kindeditor.js
文章浏览阅读2.3k次,点赞6次,收藏14次。SPI的详情简介不必赘述。假设我们通过SPI发送0xAA,我们的数据线就会变为10101010,通过修改不同的内容,即可修改SPI中0和1的持续时间。比如0xF0即为前半周期为高电平,后半周期为低电平的状态。在SPI的通信模式中,CPHA配置会影响该实验,下图展示了不同采样位置的SPI时序图[1]。CPOL = 0,CPHA = 1:CLK空闲状态 = 低电平,数据在下降沿采样,并在上升沿移出CPOL = 0,CPHA = 0:CLK空闲状态 = 低电平,数据在上升沿采样,并在下降沿移出。_stm32g431cbu6
文章浏览阅读1.2k次,点赞2次,收藏8次。数据链路层习题自测问题1.数据链路(即逻辑链路)与链路(即物理链路)有何区别?“电路接通了”与”数据链路接通了”的区别何在?2.数据链路层中的链路控制包括哪些功能?试讨论数据链路层做成可靠的链路层有哪些优点和缺点。3.网络适配器的作用是什么?网络适配器工作在哪一层?4.数据链路层的三个基本问题(帧定界、透明传输和差错检测)为什么都必须加以解决?5.如果在数据链路层不进行帧定界,会发生什么问题?6.PPP协议的主要特点是什么?为什么PPP不使用帧的编号?PPP适用于什么情况?为什么PPP协议不_接收方收到链路层数据后,使用crc检验后,余数为0,说明链路层的传输时可靠传输
文章浏览阅读587次。软件测试工程师移民加拿大 无证移民,未受过软件工程师的教育(第1部分) (Undocumented Immigrant With No Education to Software Engineer(Part 1))Before I start, I want you to please bear with me on the way I write, I have very little gen...
文章浏览阅读304次。Thinkpad X250笔记本电脑,装的是FreeBSD,进入BIOS修改虚拟化配置(其后可能是误设置了安全开机),保存退出后系统无法启动,显示:secure boot failed ,把自己惊出一身冷汗,因为这台笔记本刚好还没开始做备份.....根据错误提示,到bios里面去找相关配置,在Security里面找到了Secure Boot选项,发现果然被设置为Enabled,将其修改为Disabled ,再开机,终于正常启动了。_安装完系统提示secureboot failure
文章浏览阅读10w+次,点赞93次,收藏352次。1、用strtok函数进行字符串分割原型: char *strtok(char *str, const char *delim);功能:分解字符串为一组字符串。参数说明:str为要分解的字符串,delim为分隔符字符串。返回值:从str开头开始的一个个被分割的串。当没有被分割的串时则返回NULL。其它:strtok函数线程不安全,可以使用strtok_r替代。示例://借助strtok实现split#include <string.h>#include <stdio.h&_c++ 字符串分割
文章浏览阅读2.3k次。1 .高斯日记 大数学家高斯有个好习惯:无论如何都要记日记。他的日记有个与众不同的地方,他从不注明年月日,而是用一个整数代替,比如:4210后来人们知道,那个整数就是日期,它表示那一天是高斯出生后的第几天。这或许也是个好习惯,它时时刻刻提醒着主人:日子又过去一天,还有多少时光可以用于浪费呢?高斯出生于:1777年4月30日。在高斯发现的一个重要定理的日记_2013年第四届c a组蓝桥杯省赛真题解答
文章浏览阅读851次,点赞17次,收藏22次。摘要:本文利用供需算法对核极限学习机(KELM)进行优化,并用于分类。
文章浏览阅读1.1k次。一、系统弱密码登录1、在kali上执行命令行telnet 192.168.26.1292、Login和password都输入msfadmin3、登录成功,进入系统4、测试如下:二、MySQL弱密码登录:1、在kali上执行mysql –h 192.168.26.129 –u root2、登录成功,进入MySQL系统3、测试效果:三、PostgreSQL弱密码登录1、在Kali上执行psql -h 192.168.26.129 –U post..._metasploitable2怎么进入
文章浏览阅读257次。本文将为初学者提供Python学习的详细指南,从Python的历史、基础语法和数据类型到面向对象编程、模块和库的使用。通过本文,您将能够掌握Python编程的核心概念,为今后的编程学习和实践打下坚实基础。_python人工智能开发从入门到精通pdf