看p站用什么浏览器_深圳外贸建站与推广_apple私人免费网站怎么下载_cpa广告联盟

快速排序-高效排序

算法

代码

#include<iostream>
using namespace std;
//数组两边都是闭区间，从0开始，最后一位结束。 
void csort(int* start,int* end){if(start>=end)return;int temp =*start;int* p=start;int* q=end;while(1){while(p<q && *q>=temp)q--;if(p==q) break;*p = *q;++p;while(p<q && *p<temp) p++;if(p==q) break;*q-- = *p;}*p =temp;csort(start,q-1);csort(q+1,end);
} 
void print(int* data,int n){for(int i=0;i<n;i++)cout<<data[i]<<" ";cout<<endl;
}
int main(){int a[]=csort(a,a+sizeof(a)/sizeof(int)-1);print(a,sizeof(a)/sizeof(int));return 0;
}

归并排序

算法

代码

#include<iostream>
#include<cstring>
using namespace std;
//归并排序 
void f(int* a,int* temp,int n){if(n==1) return;int m=n/2;f(a,temp,m);f(a+m,temp,n-m);int* p =a;int*q =a+m;int* r=temp;while(p<a+m && q<a+n){*r++ = (*p < *q) ? *p++ : *q++;}if(p<a+m) memcpy(r,p,(a+m-p)*sizeof(int));if(q<a+n) memcpy(r,q,(a+n-q)*sizeof(int));memcpy(a,temp,n*sizeof(int));
}
//动态分配临时数组，存放排序的元素 
void mergeSort(int a[],int n){int* temp=new int[n];f(a,temp,n);delete [] temp;
}
//打印数组 
void print(int a[],int n){for(int i=0;i<n;++i)cout << a[i]<<" ";cout<<endl;
}
int main(){int a[]={51,12,6,25,3,33,14,49,15,17,28,4,2,13,31};mergeSort(a,sizeof(a)/sizeof(a[0]));print(a,sizeof(a)/sizeof(a[0]));return 0;
} 

堆排序

算法

基础知识

• 堆是完全二叉树，完全二叉树的特点是，只在最后一层右边有缺损的(满二叉树)
  
• 满二叉树。特点是，层数不变，节点数已经无法再多，满员的二叉树。
  
• 大顶（根）堆，根节点比它的孩子大。小顶堆刚好相反
  
• 存贮，用数组来存贮，逻辑实现
  
• 数组表示堆，下标i的父节点下标(i-1)/2，左孩子下标 i×2+1，右孩子下标i×2+2。

思路

• 1把数组转化成大顶堆。堆的根则是最大数，存在数组的坐标0处。
• 2把根与尾数互换，则尾为最大的数。把除去尾数的数组看成一个新数组，把新数组转成大顶堆。
• 3新数组的（首）根与尾互换，重复2的步骤，直到数组中元素的个数为0。
• 4得到的数组即为有序（升序）。

代码

#include<iostream>
using namespace std;
//交换元素值，内联函数 
inline void swap(int* a,int* b){int t=*a;*a=*b;*b=t;
}
//变成大顶堆， 参数为数组指针，数组元素个数,从哪个根节点开调整 
void adjust(int* a,int n,int k){int l=k*2+1;//左孩子 int r=l+1;//右孩子 //左子树越界，右子树必越界，返回 if(l>=n) return;//只右子树越界，比较左孩子与根的大小 if(r>=n){if(a[l]>a[k])swap(a+l,a+k);return;}//左右子树都存在的情况，判断根、左孩、右孩的值，最大的值放在根上 int s=(a[l]>a[r]) ? l:r;if(a[s]>a[k]){swap(a+s,a+k);adjust(a,n,s);//s位置上的大数换走后，破坏原来分支上的大顶堆，则需调整 }
}
void heapSort(int* a,const int N){//从最后节点的父节点开始构建大顶堆，由下往上，直至根节点 for(int i=(N-1)/2;i>=0;i--)adjust(a,N,i);int* p=a+N-1;while(p!=a){swap(a,p);adjust(a,p-a,0);p--;}
} 
//打印数组 
void print(int a[],int n){for(int i=0;i<n;++i)cout << a[i]<<" ";cout<<endl;
}
int main(){int a[]={51,12,6,25,3,33,14,49,15,17,28,4,2,13,31};heapSort(a,sizeof(a)/sizeof(int));//堆排序 print(a,sizeof(a)/sizeof(int));return 0;
}

希尔排序

算法

• 1间隔分组，通常为总长度的一半的间隔，n/2取整。
• 2组内采用插入排序
• 3重新分组，间隔为上次的一半，也取整，重复步骤2。
• 4直到间隔为1的排序完成，则总的完成。
• 通常插入排序算法低效，但当序列基本有序时，直接插入效率相对高效。

代码

#include<iostream>
using namespace std;
void print(int* da,int n){for(int i=0;i<n;i++)cout<<da[i]<<" ";printf("\n");
} 
//step是步长，begin是起始下标
//插入排序，从逻辑数组(按步长组成的新数组)，从第2个元素开始往后循环
//每次循环中，将其前面的数依次与之比较，大于它的数往后移，该次循环结束前把该数放于空位处。 
void f(int a[],int n,int step,int begin){for(int i=begin+step;i<n;i+=step){int t=a[i];int k=i-step;for(;k>=0 && a[k]>t;k-=step){a[i]=a[k];i-=step;}a[i]=t;}
}
void shellSort(int da[],int n){for(int step=n/2;step>0;step/=2){for(int begin=0;begin<step;++begin){f(da,n,step,begin);}print(da,n);}
}
int main(){int da[]={51,12,6,25,3,33,14,49,15,17,28,4,2,13,31};shellSort(da,sizeof(da)/sizeof(int));return 0;
}