您现在的位置是：主页 > news > 国外做网站推广/图片优化软件

国外做网站推广/图片优化软件

admin2025/5/5 15:11:04【news】

简介国外做网站推广,图片优化软件,百度搜索关键词统计,app开发软件哪个好问题：输入：n个数：a1,a2,a3,...,an 输出：n个数的排列:a1,a2,a3,...,an，使得a1<a2<a3<...<an。各种排序算法最坏与平均（期望）时间复杂度直接插入排序算法：将一个记录插入到…

国外做网站推广,图片优化软件,百度搜索关键词统计,app开发软件哪个好问题：输入：n个数：a1,a2,a3,...,an 输出：n个数的排列:a1,a2,a3,...,an，使得a1<a2<a3<...<an。各种排序算法最坏与平均（期望）时间复杂度直接插入排序算法：将一个记录插入到…

问题：

输入：n个数：a1,a2,a3,...,an
输出：n个数的排列:a1',a2',a3',...,an'，使得a1'<=a2'<=a3'<=...<=an'。

各种排序算法最坏与平均（期望）时间复杂度

直接插入排序算法：

将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。

适用范围：对于少量元素的排序。

编程思想：

直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。

c++实现

#include <iostream>using namespace std;void print(int a[], int n ,int i){  cout<<"第"<<i<<"次循环:";  for(int j= 0; j<6; j++){  cout<<a[j] <<" ";  }  cout<<endl;  
}  
void Insert_sort(int a[],int n)
{for(int i=1;i<n;i++){int key=a[i];int j=i-1;while(j>=0 && a[j]>key)//将a[j]>key换成a[j]<key即可实现降序{a[j+1]=a[j];j--;}a[j+1]=key;print(a,n,i);}}
int main()
{  int a[6] = {31,41,59,26,41,58};  Insert_sort(a,6);  print(a,6,6);  
}

直接插入排序过程

希尔排序算法：

先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。

C++实现：

#include <iostream>using namespace std;
void print(int a[], int n )
{  for(int j= 0; j<8; j++)cout<<a[j] <<" ";  cout<<endl;  
}
void shell_sort(int a[],int n)
{for(int gap=n/2;gap>0;gap/=2){for(int j=gap;j<n;j++){if(a[j]<a[j-gap]){int tmp=a[j];int k=j-gap;while(k>=0 && a[k]>tmp){a[k+gap]=a[k];k-=gap;}a[k+gap]=tmp;print(a,n);}}}
}
int main()
{int a[8]={2,4,5,7,1,2,4,6};print(a,8);shell_sort(a,8);return 0;
}

排序结果：

归并排序算法：

归并排序算法采用分治模式，分解待排序的n个元素的序列成各具有n/2个元素的两个序列，使用归并排序递归的排序两子序列，合并两个已排序的子序列以产生最终的排序。

c++实现（参考http://blog.sina.com.cn/s/blog_4d3a41f401010jbf.html）

#include <iostream>  using namespace std;  
void print(int data[], int n)
{  for(int j= 0; j<n; j++)cout<<data[j] <<"  ";    cout<<endl;  
} 
void merge(int *data, int p, int q, int r)  
{  int n1, n2, i, j, k;  int *left=NULL, *right=NULL;  n1 = q-p+1;   n2 = r-q;  left = (int *)malloc(sizeof(int)*(n1));   right = (int *)malloc(sizeof(int)*(n2));  for(i=0; i<n1; i++)  //对左数组赋值left[i] = data[p+i];for(j=0; j<n2; j++)  //对右数组赋值 right[j] = data[q+1+j]; i = j = 0;k = p;while(i<n1 && j<n2) //将数组元素值两两比较，并合并到data数组  {  if(left[i] <= right[j])  data[k++] = left[i++];  else  data[k++] = right[j++];  }  for(; i<n1; i++) //如果左数组有元素剩余，则将剩余元素合并到data数组  data[k++] = left[i];  for(; j<n2; j++) //如果右数组有元素剩余，则将剩余元素合并到data数组  data[k++] = right[j];
}  void mergeSort(int *data, int p, int r)  
{  int q;  if(p < r) //只有一个或无记录时不须排序   {  q = (int)((p+r)/2);      //将data数组分成两半     mergeSort(data, p, q);   //递归拆分左数组  mergeSort(data, q+1, r); //递归拆分右数组 merge(data, p, q, r);    //合并数组}  
}  
int main()
{int data[9]={2,4,5,7,1,2,3,6,4};print(data,9);mergeSort(data,0,8);print(data,9);return 0;
}

排序结果：

堆排序算法：

堆排序利用了最大堆（或最小堆）堆顶记录的关键字最大（或最小）的特征。

首先利用build_heap将输入数组a[1,...,n]建成最大堆

其次通过将最大堆中的根节点a[1]与a[n]进行交换；

然后利用max_heapify维护最大堆，使其剩余的a[1,..,n-1]构成新的最大堆。（由于去掉根结点，新的根结点可能违背最大堆的性质）

c++实现：

#include <iostream>
#include<algorithm>using namespace std;
void print(int a[], int n)
{  for(int j= 0; j<n; j++) cout<<a[j] <<"  ";  cout<<endl;  
} 
void max_heapify(int *a,int i,int heap_size)
{int left,right,largest;left=(i<<1)+1;right=left+1;largest=i;if(left<=heap_size && a[left]>a[largest])largest=left;if(right<=heap_size && a[right]>a[largest])largest=right;if(largest!=i){swap(a[i],a[largest]);max_heapify(a,largest,heap_size);	}print(a,heap_size+1);
}
void build_heap(int *a,int heap_size)
{int tmp=heap_size/2;for(int i=tmp;i>=0;i--)max_heapify(a,i,heap_size);
}
void heap_sort(int *a,int heap_size)
{build_heap(a,heap_size);for(int i=heap_size;i>=0;i--){swap(a[0],a[i]);max_heapify(a,0,i-1);	}
}
int main()
{int a[8]={2,4,5,7,1,2,3,6};int size=sizeof(a)/sizeof(int);heap_sort(a,size-1);print(a,8);return 0;
}

排序结果：

冒泡排序算法:

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

具体原理

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

C++实现：

bubble_sort()经典的冒泡排序实现.

bubble_sort_x()在某次遍历中如果没有数据交换，说明整个数组已经有序。因此通过设置标志位来记录此次遍历有无数据交换就可以判断是否要继续循环。

bubble_sort_x1()记录某次遍历时最后发生数据交换的位置，这个位置之后的数据显然已经有序了。因此通过记录最后发生数据交换的位置就可以确定下次循环的范围了

#include <iostream>
#include <algorithm>
using namespace std;void print(int a[], int n)
{  for(int j= 0; j<n; j++)  cout<<a[j] <<"  ";   cout<<endl;  
}  
void bubble_sort(int a[],int n)
{for(int i=0;i<n;i++){for(int j=1;j<n-i;j++){if(a[j-1]>a[j])swap(a[j-1],a[j]);}print(a,n);}
}
void bubble_sort_x(int a[],int n)
{bool flag;int k=n;flag=true;//设置一个标志，while(flag){flag=false;//如果有一趟没有发生交换则返回falsefor(int j=1;j<k;j++)if(a[j-1]>a[j]){swap(a[j-1],a[j]);flag=true;//如果发生交换则返回true}k--;print(a,n);}
}
void bubble_sort_x1(int a[],int n)
{int pos,k;pos=n;while(pos>0){k=pos;pos=0;for(int j=1;j<k;j++)if(a[j-1]>a[j]){swap(a[j-1],a[j]);pos=j;//记录某次遍历时最后发生交换的位置，确定下次循环的范围}print(a,k);}}
int main()
{int a[8]={2,4,5,7,1,2,3,6};bubble_sort(a,8);//经典的冒泡排序
//	bubble_sort_x(a,8);
//	bubble_sort_x1(a,8);
//	print(a,8);return 0;
}

排序结果：

bubble_sort

bubble_sort_x

bubble_sort_x1

快速排序算法：

快速排序算法与归并排序算法一样，也采用了分治思想，例如，对一数组a[p,...,r]进行快速排序，即分解a[p,...,r]为a[p,...,q-1]和a[q+1,...,r]是得a[p,...,q-1]中的元素都小于等于a[q],a[q+1,...,r]中的元素都大于等于a[q].，然后通过递归调用快速排序，对数组a[p,...,q-1]和a[q+1,...,r]进行排序，上述都是对原址排序，所以不需要合并排序，数组a[p,...,r]已经有序。

C++实现：

#include <iostream>using namespace std;void print(int a[], int n)
{  for(int j= 0; j<n; j++)cout<<a[j] <<"  ";   cout<<endl;  
}
void swap(int *a, int *b)  
{  int tmp = *a;  *a = *b;  *b = tmp;  
}  
int partition(int a[], int p, int r)  
{  int x = a[r];       //主元，围绕其划分数组  int i=p-1;for(int j=p;j<=r-1;j++){if(a[j]<=x){i=i+1;swap(&a[i], &a[j]);//交换元素（地址）}  print(a,8);}swap(&a[i+1], &a[r]);    return i+1;  
}   
void quick_sort(int a[], int p, int r)
{  if(p < r){  int q = partition(a,p,r);  quick_sort(a,p,q-1);quick_sort(a,q+1,r);}  
}    
int main()
{int a[8] = {2,8,7,1,3,5,6,4};    quick_sort(a,0,7);  print(a,8);  return 0;
}

排序结果：