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

沈阳三好街附近做网站/企业官网首页设计

news 2025/6/30 10:51:44
沈阳三好街附近做网站,企业官网首页设计,如何做网站demo,常宁做网站冒泡排序 基础知识 冒泡排序&#xff1a;比较相邻的元素。如果第一个比第二个大&#xff0c;就交换他们两个。每次最外面的循环&#xff0c;得到一个最小值。时间复杂度&#xff1a;$O(n^2)$https://blog.csdn.net/guoweim...代码实现 #include <iostream> using namespa…

冒泡排序

基础知识

  • 冒泡排序：比较相邻的元素。如果第一个比第二个大，就交换他们两个。每次最外面的循环，得到一个最小值。
  • 时间复杂度：$O(n^2)$
https://blog.csdn.net/guoweim...

代码实现

#include <iostream>
using namespace std;int a[10] = {3,2,7,5,1,9,6,4,0,8};void BubbleSort(int a[], int n){for(int i=0; i<n-1; i++){//控制外循环次数for(int j=0; j<n-1-i; j++){if(a[j+1] < a[j]){int temp = a[j];a[j] = a[j+1];a[j+1] = temp;}}}/*for(int i=0; i<n-1; i++){for(int j=i+1; j<n; j++){if(a[j] < a[i]){int temp = a[i];a[i] = a[j];a[j] = temp;}}}*/
}int main() {int size = sizeof(a)/sizeof(a[0]);cout<<"........before sort........"<<endl;for(int i=0; i<size; i++){cout<<a[i]<<",";}cout<<endl;BubbleSort(a, size);cout<<"........after sort........"<<endl;for(int i=0; i<size; i++){cout<<a[i]<<",";}cout<<endl;return 0;
}

clipboard.png

快速排序

基础知识

  • 快速排序采用的是分治的思想。

  • 基本思路：

    • 在数据集之中，选择一个元素作为“基准”。
    • 所有小于“基准”的元素，都移到“基准”的左边；所有大于“基准”的元素，都移到“基准”的右边。
    • 对“基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

  • 注意：

    • 要先从右边哨兵开始寻找（这样做的是保证哨兵i和哨兵j共同指向的元素比“基准”小）
    • 交换的前提是：哨兵i指向的元素比“基准”大，哨兵j指向的元素比“基准”小，且哨兵i比哨兵j小。
  • 算法复杂度：$O(nlog_2n)$

clipboard.png

代码实现

#include <iostream>
using namespace std;int a[10] = {3,2,7,5,1,9,6,4,0,8};void quickSort(int a[], int left, int right){if(left>right)  return;int temp = a[left];int i = left;int j = right;while(i != j){//注意顺序，保证右边哨兵最先开始while(i<j && a[j]>=temp){j--;}while(i<j && a[i]<=temp){i++;}if(i<j){int temp = a[i];a[i] = a[j];a[j] = temp;}}a[left]  = a[i];a[i] = temp;quickSort(a,left, i-1);quickSort(a, i+1, right);
}int main() {int size = sizeof(a)/sizeof(a[0]);cout<<"........before sort........"<<endl;for(int i=0; i<size; i++){cout<<a[i]<<",";}cout<<endl;quickSort(a, 0, size-1);cout<<"........after sort........"<<endl;for(int i=0; i<size; i++){cout<<a[i]<<",";}cout<<endl;return 0;
}

插入排序

基本知识

  • 插入排序:将一个记录插入到已排序好的有序表中，从而得到一个新的有序序列
  • 时间复杂度：$O(n^2)$

clipboard.png

代码实现

#include <iostream>
using namespace std;int a[10] = {3,2,7,5,1,9,6,4,0,8};
int temp[10];void InsertSort(int a[] , int n){for(int i=0; i<n; i++){for(int j=i; j>0; j--){if(a[j]<a[j-1]){int temp = a[j];a[j] = a[j-1];a[j-1] = temp;}}}
}int main() {int size = sizeof(a)/sizeof(a[0]);cout<<"........before sort........"<<endl;for(int i=0; i<size; i++){cout<<a[i]<<",";}cout<<endl;InsertSort(a, size);cout<<"........after sort........"<<endl;for(int i=0; i<size; i++){cout<<a[i]<<",";}cout<<endl;return 0;
}

clipboard.png

Shell排序

基础知识

  • Shell排序是插入排序的一种，它是针对直接插入排序算法的改进。该方法又称缩小增量排序。
  • 对于n个待排序的数列，取一个小于n的整数gap(gap被称为步长)将待排序元素分成若干个组子序列，所有距离为gap的倍数的记录放在同一个组中；然后，对各组内的元素进行直接插入排序。 这一趟排序完成之后，每一个组的元素都是有序的。然后减小gap的值，并重复执行上述的分组和排序。重复这样的操作，当gap=1时，整个数列就是有序的。
  • 时间复杂度：$O(n^{1.3})$

clipboard.png

代码实现

#include <iostream>
using namespace std;int a[10] = {3,2,7,5,1,9,6,4,0,8};void ShellSort(int a[], int n){int i,j,gap;for(gap = n/2; gap>0; gap /=2){//以下是快速插入排序for(i=gap; i<n; i++){for(j=i; j>0; j -=gap){if(a[j-gap]>a[j]){int temp = a[j-gap];a[j-gap] = a[j];a[j] = temp;}}}}
}int main() {int size = sizeof(a)/sizeof(a[0]);cout<<"........before sort........"<<endl;for(int i=0; i<size; i++){cout<<a[i]<<",";}cout<<endl;ShellSort(a, size);cout<<"........after sort........"<<endl;for(int i=0; i<size; i++){cout<<a[i]<<",";}cout<<endl;return 0;
}

clipboard.png

选择排序

基础知识

  • 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
  • 时间复杂度：$O(n^2)$

clipboard.png

代码实现

#include <iostream>
using namespace std;int a[10] = {3,2,7,5,1,9,6,4,0,8};void SelectSort(int a[], int n){for(int i=0; i<n-1; i++){//每次循环，寻找到i位置最小的值int index = i;//index用来记录最小元素的下标for(int j=i+1; j<n; j++){if(a[j] < a[index]){index = j;}}if(index != i){int temp = a[index];a[index] = a[i];a[i] = temp;}}
}int main() {int size = sizeof(a)/sizeof(a[0]);cout<<"........before sort........"<<endl;for(int i=0; i<size; i++){cout<<a[i]<<",";}cout<<endl;SelectSort(a, size);cout<<"........after sort........"<<endl;for(int i=0; i<size; i++){cout<<a[i]<<",";}cout<<endl;return 0;
}

堆排序

基础知识

  • 堆排序是一种树形选择排序，在排序过程中可以把元素看成是一颗完全二叉树，每个节点都大（小）于它的两个子节点。
  • 当每个节点都大于等于它的两个子节点时，就称为大顶堆，也叫堆有序； 当每个节点都小于等于它的两个子节点时，就称为小顶堆。

  • 完全二叉树的规律：

    • 索引为i的左孩子的索引是 (2*i+1);
    • 索引为i的左孩子的索引是 (2*i+2);
    • 索引为i的父结点的索引是 (i-1)/2;

  • 算法思想：

    • 将长度为n的待排序的数组进行堆有序化构造成一个大顶堆
    • 将根节点与尾节点交换并输出此时的尾节点
    • 将剩余的n -1个节点重新进行堆有序化
    • 重复步骤2，步骤3直至构造成一个有序序列
  • 时间复杂度：$O(nlog_2n)$

clipboard.png
clipboard.png
clipboard.png
clipboard.png

代码实现

#include <iostream>
using namespace std;int a[10] = {3,2,7,5,1,9,6,4,0,8};void swap(int a[], int i, int j){int temp = a[i];a[i] = a[j];a[j] = temp;
}void heapAdjust(int a[], int i, int len){//保证根节点最大int left, right, child;while(2*i+1 <= len){判断当前节点有无左节点，保证当前节点不是叶子节点left = 2*i+1;        right = left+1;child = left;if(left<len && a[left]<a[right]){child++;//左右子节点的最大值}if(a[i]<a[child]){//当前节点比孩子节点要小，需要调整位置swap(a, i, child);}elsebreak;i = child;}
}void heapSort(int a[], int n){for(int i=(n-1)/2; i>=0; i--){//从最后一个非叶子节点开始构建大顶堆，以上图例子(8-1)/2=3,也就是说a[3]以后都是叶子节点。heapAdjust(a, i, n);}n = n-1;//因为下标从0开始，所以尾节点下标是n-1while(n>0){swap(a, 0, n);//交换根节点与尾节点n--;//把尾节点排除在外heapAdjust(a, 0, n);}
}int main() {int size = sizeof(a)/sizeof(a[0]);cout<<"........before sort........"<<endl;for(int i=0; i<size; i++){cout<<a[i]<<",";}cout<<endl;heapSort(a, size);cout<<"........after sort........"<<endl;for(int i=0; i<size; i++){cout<<a[i]<<",";}cout<<endl;return 0;
}

归并排序（合并排序）

基础知识

  • 归并排序采用的是分治的思想；
  • 归并操作即将两个已经排序的序列合并成一个序列的操作；

  • 基本实现：

    • 分解：将当前区间一分为二，并递归的对左右子区间进行分解，直到子区间长度为1；
    • 合并：将两个有序的子区间合并成一个有序的区间。
      clipboard.png
  • 时间复杂度：$nlogn$（理解：分解可以理解为n个节点的完全二叉树层数为$log_2n$,即$O(logn)$;合并可以理解为每层都需要扫描比较一遍所有数据，所以为$O(n)$）

代码实现

#include <iostream>
using namespace std;int a[10] = {3,2,7,5,1,9,6,4,0,8};
int temp[10];void Merge(int a[], int start, int mid, int end, int temp[]){int pb = 0;int p1 = start;int p2 = mid+1;while(p1<=mid && p2<=end){if(a[p1] < a[p2]){temp[pb++] = a[p1++];}else{temp[pb++] = a[p2++];}}while(p1<=mid){temp[pb++] = a[p1++];}while(p2<=end){temp[pb++] = a[p2++];}for(int i=0; i<end-start+1; i++){a[start+i] = temp[i];}
}void MergeSort(int a[], int start, int end, int temp[]){if(start<end){int mid = start + (end - start)/2;MergeSort(a, start, mid, temp);MergeSort(a, mid+1, end, temp);Merge(a, start, mid, end, temp);}
}int main() {int size = sizeof(a)/sizeof(a[0]);cout<<"........before sort........"<<endl;for(int i=0; i<size; i++){cout<<a[i]<<",";}cout<<endl;MergeSort(a, 0, size-1, temp);cout<<"........after sort........"<<endl;for(int i=0; i<size; i++){cout<<a[i]<<",";}cout<<endl;return 0;
}

clipboard.png

桶排序

基础知识

  • 时间复杂度：$O(n+K)$
  • 工作的原理是将数组分到有限数量的桶里。每个桶再个别排序。
  • 桶排序使用线性时间，并不是比较排序。

clipboard.png

代码实现

//一种最简单的桶排序
#include <iostream>
#include <cstring>using namespace std;int a[10] = {3,2,7,5,1,9,6,4,0,8};void bucketSort(int a[], int size, int max){
//size是待排序数组的大小；max是待排序数组中的最大值int buckets[max];memset(buckets, 0, max* sizeof(int));for(int i=0; i<size; i++){buckets[a[i]]++;}int i,j;for(i=0,j=0; i<max; i++){while(buckets[i]>0){buckets[i]--;a[j] = i;j++;}}
}
int main() {int size = sizeof(a)/sizeof(a[0]);cout<<"........before sort........"<<endl;for(int i=0; i<size; i++){cout<<a[i]<<",";}cout<<endl;bucketSort(a, size, 10);cout<<"........after sort........"<<endl;for(int i=0; i<size; i++){cout<<a[i]<<",";}cout<<endl;return 0;
}

计数排序

基础知识

  • 计数排序是一种非基于比较的排序算法，其空间复杂度和时间复杂度均为$O(n+k)$，其中k是整数的范围。快于任何比较排序算法。
  • 它是基数排序的一个关键部分。

clipboard.png

代码实现

#include <iostream>
#include <cstring>using namespace std;int a[6] = {0,7,2,6,0,8};int getMax(int a[], int size){int max = a[0];for(int i=1; i<size; i++){if(max<a[i]){max = a[i];}}return max;
}
void countSort(int a[], int size){int max = getMax(a, size)+1;int output[size];memset(output, 0, size* sizeof(int));int buckets[max];memset(buckets, 0, max* sizeof(int));for(int i=0; i<size; i++){buckets[a[i]]++;}for(int i=0; i<max; i++){buckets[i+1] += buckets[i];}cout<<buckets[max]<<endl;for(int i=0; i<size; i++){output[buckets[a[i]]-1] = a[i];buckets[a[i]]--;}for (int i = 0; i < size; ++i) {a[i] = output[i];}
}int main() {int size = sizeof(a)/sizeof(a[0]);cout<<"........before sort........"<<endl;for(int i=0; i<size; i++){cout<<a[i]<<",";}cout<<endl;countSort(a, size);cout<<"........after sort........"<<endl;for(int i=0; i<size; i++){cout<<a[i]<<",";}cout<<endl;return 0;
}

基数排序

基础知识

  • 主要思想：将所有待比较数值(注意,必须是正整数)统一为同样的数位长度，数位较短的数前面补零。 然后，从最低位开始, 依次进行一次稳定排序。（从低位开始的原因是：如果要从高位排序，那么次高位的排序会影响高位已经排好的大小关系。在数学中， 数位越高，数位值对数的大小的影响就越大。）

clipboard.png

  • 举个例子：

clipboard.png
clipboard.png

代码实现

#include <iostream>
using namespace std;int a[10] = {13,2,90,165,211,768,89,889,0,28};int getMax(int a[], int size){int max = a[0];for(int i=1; i<size; i++){if(max<a[i]){max = a[i];}}return max;}void countSort(int a[], int size, int exp){int output[size];//注意这是动态数组，在堆上分配，需要delete。for(int i=0; i<size; i++){output[i] = 0;}/** int output[size];** delete output;* */int buckets[10]={0};for(int i=0; i<size; i++){buckets[(a[i]/exp)%10]++;}for(int i=0; i<10; i++){buckets[i+1] +=buckets[i];}for(int i=size; i>=0; i--){/*这里需要注意，从大开始递减。原因是：buckets[(a[i]/exp)%10](临时数组的下标)的值是递减的；第一轮循环以后，个位值大的在数组下标大。因此相同十位的数，数组下标大的先进临时数组。*/output[buckets[(a[i]/exp)%10]-1] = a[i];//因为索引是从0开始的，所以要减1buckets[(a[i]/exp)%10]--;}for(int i=0; i<size; i++){a[i] = output[i];}//delete output;
}void radixSort(int a[], int size){int exp;int max = getMax(a, size);for(exp=1; max/exp>0; exp *= 10){countSort(a,size,exp);}
}int main() {int size = sizeof(a)/sizeof(a[0]);cout<<"........before sort........"<<endl;for(int i=0; i<size; i++){cout<<a[i]<<",";}cout<<endl;radixSort(a, size);cout<<"........after sort........"<<endl;for(int i=0; i<size; i++){cout<<a[i]<<",";}cout<<endl;return 0;
}

总结

内排序与外排序

  • 内排序：指在排序期间数据对象全部存放在内存的排序。以上讲的都是内部排序。
  • 外排序：指在排序期间全部对象太多，不能同时存放在内存中，必须根据排序过程的要求，不断在内，外存间移动的排序。

基于比较的排序

  • 基于比较的排序：插入排序，选择排序，交换排序，归并排序。基于比较的排序算法是不能突破$O(nlog_2n)$的。n个数有$n!$个可能的排列情况，也就是说基于比较的排序算法的判定树有$n!$个叶子结点，比较次数至少为$log(n!)=O(nlogn)$(斯特林公式)。
  • 基于线性的排序（非比较排序）：计数排序，桶排序，基数排序。不受$O(nlog_2n)$$的影响。其时间复杂度依赖于数据的范围。非基于比较的排序算法的使用都是有条件限制的，例如元素的大小限制等。

clipboard.png

参考：https://www.cnblogs.com/zyb42...
http://www.jmfq.cn/news/4792141.html

相关文章：

  • 物流网站怎么做/哪个行业最需要推广
  • 新网站如何做排在前面/开发小程序
  • wordpress发不出邮件/湖南关键词优化品牌价格
  • 程序员做任务的网站/女生学电子商务好吗
  • 网站logo在哪里修改/做关键词推广
  • 做面料那几个网站/盐城seo排名
  • 做网站需要买服务器么/网站死链检测工具
  • 郑州网站建设网站/数字营销包括哪六种方式
  • 网站的流程图/站长综合查询工具
  • 做网站用什么工具/太原seo霸屏
  • 阿里云可以做网站么/如何自己开个网站平台
  • 网页设计与网站开发方向/域名注册信息怎么查
  • 什么网站做任务的q币/最权威的排行榜网站
  • 单位门户网站建设存在问题/百度一下官网网址
  • 网站网页制作公司网站/百度快照怎么看
  • 国家工信部网站域名查询系统/搜索引擎营销的案例
  • 外贸服装网站模板/站长百度
  • 个人网页制作毕业论文/官网排名优化方案
  • 长春做个人网站做不了/全网seo
  • 哪个网站可以做电视背景墙/百度搜索页面
  • 南京 网站设计/宁波网络营销公司
  • 珠海建网站的联系方式/百度推广工具
  • 无锡公司网站制作/百度推广服务
  • 做网站小程序在哪点拉客户/谷歌浏览器下载手机版
  • 网站建设的申请/常用的seo工具推荐
  • 美橙网站产品详情/免费引流推广的方法
  • 51ppt模板网免费/seo站内优化最主要的是什么
  • 广东企业网站建设公司/阿里云注册域名
  • wordpress侧栏导航/网站关键字优化
  • 如何开科技软件/网站seo如何做好优化