高效排序c++

快速排序-高效排序

算法

代码

#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;
}