当前位置: 首页 > news >正文

wordpress自定义的注册seo顾问是什么

wordpress自定义的注册,seo顾问是什么,做系统之前的网站收藏在哪里找,如何做电影网站不违法冒泡排序 冒泡排序(Bubble Sort)是一种简单的排序算法,它通过重复遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复进行直到没有再需要交换,也就是说该数列已…

冒泡排序

冒泡排序(Bubble Sort)是一种简单的排序算法,它通过重复遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

//冒泡排序
void BubbleSort(int* a, int n) {for (int i = 0; i < n - 1; i++) {	//冒泡 n-1 次bool flag = false;for (int j = 0; j < n - i - 1; j++) {if (a[j] > a[j + 1]) {Swap(&a[j], &a[j + 1]);}flag = true;}if (!flag) {break;}}
}

时间复杂度

O(n^2)

空间复杂度

原地修改,O(1)

快速排序

快速排序(Quick Sort)是一种高效的排序算法,由C. A. R. Hoare在1960年提出。它的基本思想是分治法(Divide and Conquer):通过一个划分操作将数据分为独立的两部分,其中一部分的所有数据都比另一部分的所有数据要小,然后再递归地对这两部分数据分别进行排序操作。

递归版本

递归版本一:hoare

大致思想:通过左右下标指针不断的寻找交换,每趟分割可以将 1 个 a[keyi] 归位;递归地分割、归位子序列即可

右下标指针 right 从右开始寻找小于 a[keyi] 的值,左下标指针 left 从左开始寻找大于 a[keyi] 的值;然后交换 a[left] 和 a[right],继续寻找直到 left 和 right 相遇,将 a[keyi] 归位

//单趟分割区间
int PartSort_1(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;
}//快速排序
void QuickSort(int* a, int begin, int end) {//只有一个元素,或区间不存在if (begin >= end) {return;}//分割区间int midi = PartSort_1(a, begin, end);//递归分割子区间// [begin,midi-1] midi [midi+1,end]QuickSort(a, begin, midi - 1);QuickSort(a, midi + 1, end);}

递归版本二:挖坑法

大致思想:hoare法是大小交换,而挖坑法是找到小了立即交换到左边,找到大了立即交换到右边,hole(坑)的值由 key 保存,坑的位置随着值的交换而变化

//单趟分割区间
//挖坑法
int PartSort_2(int* a, int left, int right) {int key = a[left];	//保存被挖坑的值int hole = left;while (left < right) {//右边开始找小while (left < right && a[right] >= key) {right--;}a[hole] = a[right];hole = right;//左边开始找大while (left < right && a[left] <= key) {left++;}a[hole] = a[left];hole = left;}a[hole] = key;return hole;
}//快速排序
void QuickSort(int* a, int begin, int end) {//只有一个元素,或区间不存在if (begin >= end) {return;}//分割区间//int midi = PartSort_1(a, begin, end);int midi = PartSort_2(a, begin, end);//递归分割子区间// [begin,midi-1] midi [midi+1,end]QuickSort(a, begin, midi - 1);QuickSort(a, midi + 1, end);
}

递归版本三:前后指针法

大致思想:通过 prev 和 cur 下标指针,将每趟大于等于 a[keyi] 的值往后推,最后将基准值 a[keyi] 与 a[prev] 交换归位

//单趟分割区间
//前后指针法
int PartSort_3(int* a, int left, int right) {int prev = left;int cur = prev + 1;int keyi = left;while (cur <= right) {cur 找小//while (cur < right && a[cur] >= a[keyi]) {//	cur++;//}//if (cur < right) {	//避免所有元素都大于 keyi//	prev++;//	Swap(&a[cur], &a[prev]);//}if (a[cur] < a[keyi]) {prev++;Swap(&a[cur], &a[prev]);}cur++;}Swap(&a[keyi], &a[prev]);return prev;
}//快速排序
void QuickSort(int* a, int begin, int end) {//只有一个元素,或区间不存在if (begin >= end) {return;}//分割区间//int midi = PartSort_1(a, begin, end);//int midi = PartSort_2(a, begin, end);int midi = PartSort_3(a, begin, end);//递归分割子区间// [begin,midi-1] midi [midi+1,end]QuickSort(a, begin, midi - 1);QuickSort(a, midi + 1, end);
}

时间复杂度(三个版本效率相同)

每趟区间分割创建函数栈帧的复杂度为二叉结构的高度 O(logn),每趟区间分割确定一个数的位置 O(n),所以是 O(n*logn)

但是如果数组有大量重复元素时,每次选择的 keyi 基准值都是同一个数;或者每次选择的 keyi 都是数组中最大或最小的元素,那么递归深度就会大大增加,时间复杂度变成 O(n^2),比如下面的示意图

空间复杂度(三个版本效率相同)

取决于递归深度,即二叉结构高度 O(logn)

稳定性

涉及到元素之间的交换,不稳定

递归版本的优化

为了避免取基准值 keyi 时,出现取到最小或最大的情况,我们使用三数取中的方法

//三数取中
int GetMidIndex(int* a, int left, int right) {int midi = (left + right) / 2;if (a[left] > a[midi]) {Swap(&a[left], &a[midi]);	//此时 a[left] <= a[midi]}if (a[left] > a[right]) {Swap(&a[left], &a[right]);	//此时 a[left] <= a[right]}if (a[midi] > a[right]) {Swap(&a[right], &a[midi]);	//此时 a[midi] <= a[right]}return midi;
}

以版本三为例,应用

//单趟分割区间
//前后指针法
int PartSort_3(int* a, int left, int right) {int keyi = GetMidIndex(a, left, right);Swap(&a[keyi], &a[left]);int prev = left;int cur = prev + 1;keyi = left;while (cur <= right) {cur 找小//while (cur < right && a[cur] >= a[keyi]) {//	cur++;//}//if (cur < right) {	//避免所有元素都大于 keyi//	prev++;//	Swap(&a[cur], &a[prev]);//}if (a[cur] < a[keyi]) {prev++;Swap(&a[cur], &a[prev]);}cur++;}Swap(&a[keyi], &a[prev]);return prev;
}

非递归版本

考虑到递归会有栈溢出的风险,所以非递归版本,使用动态栈进行模拟

对栈有问题,请看之前的文章~

大致思想:见代码注释~

//非递归快排
void QuickSortNonR(int* a, int begin, int end) {//栈具有后进先出的性质//初始化一个动态栈Stack st;StackInit(&st);//将区间入栈StackPush(&st, end);StackPush(&st, begin);while (StackEmpty(&st)) {	//只要栈非空,子区间未分割完//从栈中取出一对区间int l = StackTop(&st);StackPop(&st);int r = StackTop(&st);StackPop(&st);//对这对区间分割int keyi = PartSort_3(a, l, r);//分割完之后,接着分割子区间// [l,keyi-1] keyi [keyi+1,r]//先让左右子区间入栈//避免区间不存在或者只有一个元素的情况if (keyi + 1 < r) {StackPush(&st, r);StackPush(&st, keyi + 1);}if (l < keyi - 1) {StackPush(&st, keyi - 1);StackPush(&st, l);}}StackDestroy(&st);
}
http://www.ritt.cn/news/22443.html

相关文章:

  • 在线建网站谷歌seo是什么职业
  • 网站开发难点珠海seo推广
  • 实验方案设计怎么写网站关键词优化排名推荐
  • 自己建设网站需要审核吗原创软文
  • wordpress免插件cdn加速seo专家是什么意思
  • 佛山品牌网站建设怎样建立自己的网站平台
  • 转运网站建设青岛网站制作推广
  • 重庆网站建设公司有哪些百度问答兼职怎么做
  • wordpress微信公众号登录界面seo公司多少钱
  • 做鞋子的招聘网站有哪些seo优化网页
  • 服装网站建设教程山东疫情最新消息
  • 软件著作权申请流程及费用seo关键词排名优化手机
  • 专业的网站建设企业微信营销软件有哪些
  • 网站制作免费软件搜索推广平台
  • 合肥网站建设电话宣传推广渠道有哪些
  • 成人高考考试科目徐州关键词优化排名
  • 网站建设执行力免费网站统计代码
  • php做网站为什么比java快网站营销与推广
  • 六安网站建设电话竞价排名点击
  • 查找网站建设虚拟目录搜索引擎哪个好用
  • 企业网站傻瓜搭建佛山营销型网站建设公司
  • wordpress加载很慢搜索引擎优化包括
  • 济南网站建设 伍际网络外链服务
  • 网站设计自已申请网站关键词百度自然排名优化
  • 自建个网站怎么做seo 网站优化推广排名教程
  • 沧州建设网站合肥网站seo推广
  • 广州生物科技网站建设公司网站怎么推广
  • 北京搭建网站aso优化前景
  • 我想做一个网站怎么做的网页制作用什么软件做
  • 网站建设合同免费下载餐饮品牌全案策划