本文介绍三种排序方式:“希尔排序”、“快速排序”、“堆排序”

希尔排序

希尔排序是第一批打破O(n2)的算法之一,在20世纪中期就提出来了,它的平均复杂度O(n1.3),一般的交换排序,倘若一个很长的序列最大值在第一个,那么这个值就要交换n-1次才能到达正确位置,这是很浪费时间的,而希尔排序很好的解决了这一点,它的思想是给这个序列分组,把每一组都排成有序,然后再分,直到分的组数为n(序列长度)个为止,它巧妙在于分组的方式,并不是相邻的是一组,而是相隔几个分成一组,这样当交换序列时可以跳着交换,大大加快了时间,虽然可能一个小的值交换到后面去了,离他的最终位置变远了,但是就算遇到这种情况也可以跳着回来,总之时间平均上加快了很多。

具体实现

首先确定分组间隔,最科学的间隔:从n/2开始,每次除以2直到最终等于1。不要问我为什么,我也不知道

确定了间隔就是简单的对每一组都进行插入排序了

代码

void Xier(node &L){
	for(int k=L.length/2;k>0;k/=2){  //分组间隔
		for(int m=1;m<=k;m++){  //k组
        	for(int i=m+k;i<=L.length;i+=k){  //对每一组进行插入排序
                int temp=L.arr[i],p;  //将L.arr[i]插入到序列中
                for(p=i-k;p>=1 && L.arr[p]>temp;p-=k) L.arr[p+k]=L.arr[p];  //找到插入位置,并把插入位置后面的数后移一位
                L.arr[p+k]=temp;  //插入进去
            }
        }
	}
}

上面的代码是4重for循环,这里可以优化成三重,因为插入排序是从前往后,不需要一组一组进行,可以同时进行:

改进代码

void Xier(node &L){
	for(int k=L.length/2;k>0;k/=2){
		for(int i=k+1;i<=L.length;i++){  //这里去掉一重循环,改掉初始化为k+1,递增方式改为i++
			int temp=L.arr[i],p;
			for(p=i-k;p>=1 && L.arr[p]>temp;p-=k) L.arr[p+k]=L.arr[p];
			L.arr[p+k]=temp;
		}
	}
}

快速排序

一直用sort从没手写过快排(逃),虽然之前写过,但是这次还是无限debug

大致思路

每次找到一个基准值,定义两个哨兵,一个从前往后搜,一个从后往前搜,前面找比基准值大的,后面的找比基准值小的,当两面都找到时就交换,最后把基准值和哨兵位置交换(出来循环哨兵一定站到同一个位置),这样下来序列就被分为了(左面部分)都比基准值小(基准值)(右面部分)都比基准值大。然后再对基准值的左面和右面的进行同样的操作。

代码

void Quick(node &L,int l,int r){
	if(l>=r) return ;  //当序列中存在两个值才进行排序
	int temp=L.arr[l];  //最左面的值作为基准值
	int i=l,j=r;  //两个哨兵
	while(i<j){
		while(i<j && L.arr[j]>=temp) j--;  //优先从右开始找,原因一会单独拿出来说
		while(i<j && L.arr[i]<=temp) i++;
		swap(L.arr[i],L.arr[j]);  //交换两个哨兵
	}
	swap(L.arr[i],L.arr[l]);  //基准值归位
	Quick(L,l,i-1);  //处理左面
	Quick(L,i+1,r);  //处理右面
}

为什么一定要右哨兵先动?

这是困扰了我很久的问题!因为我们选择最左面的位置作为基准值!

看这个例子: 2 1 3 4 5

从左开始的话就是先找到3,然后从右开始找不到比2小的就也走到了3这个位置,但是3是比2大的!不能和2交换否则就出错了,基准值左面有比基准值还大的数!所以当先找比基准值大的数时可能会指针停留在这个数,最后不能进行交换,但是如果先找比基准值小的最后即使指针停留在这个数这里也是可以交换的

堆排序

原始思想: 把序列看成一个完全二叉树,每一个数都是树的叶子节点,然后相邻节点进行比较得到较大的作为父亲节点,如此下来,二叉树的根节点就是序列最大值,然后把这个值的来源处叶子节点设为最小值,如此反复即可得到从大到小的序列,因为找了n次,每次往上递是logn,时间复杂度为O(nlog(n)),特别巧妙的算法。

改进后:

不拿序列每一个数作为树的底层,而是每一个节点,建立一颗二叉树满足当前节点值大于左右孩子节点值,这样的二叉树叫做大根堆,那么根节点就是最大值,这里每次得到序列最大值之后是把它和序列末尾值进行交换,交换后把堆进行调整保持大根堆的模样,然后继续调整从1到n-1的二叉树为大根堆,如此反复得到最终的非递减序列

堆调整函数(每次交换后)

//和插入排序非常相似,把根节点插入到合适位置,其他位置后移一位
void HeapAdjust(node &L,int s,int e){
	int temp=L.arr[s];  //得到根
	for(int i=2*s;i<=e;i*=2){  //往下一层一层调整
		if(i<e && L.arr[i+1]>L.arr[i]) i++;  //得到左右孩子较大的
		if(temp>L.arr[i]) break;  //如果父亲节点大于左右孩子较大的那个则堆满足大根堆了
		L.arr[s]=L.arr[i];  //否则就把父亲节点赋值为左右孩子较大的那个
		s=i;  //更新父亲
	}
	L.arr[s]=temp;  //最后把根节点插入到最终位置
}

对于一个给定序列还要建初始堆,所谓建初始堆,就是把这个序列的从右往左第一个非叶子节点子树给调整了,然后往上一层一层调整,最终大根树就建好了

建初始树(堆排序开始时)

void Heap(node &L){
	//建初堆 
	for(int i=L.length/2;i>0;--i) HeapAdjust(L,i,L.length);  //调整第一个非叶子节点子树
	for(int i=L.length;i>1;--i){  
		swap(L.arr[1],L.arr[i]);  //交换根节点和序列末尾值
		HeapAdjust(L,1,i-1);  //调整前面的
	}
}

全代码

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
const int MAXN=1e3;
const int INF=0x3f3f3f3f;
const double eps=1e-4;
struct node{
	int arr[MAXN];
	int length;
};
//交换函数 
void swap(int &a,int &b){
	int c=a;
	a=b;
	b=c;
}
//希尔排序 
void Xier(node &L){
	for(int k=L.length/2;k>0;k/=2){
		for(int i=k+1;i<=L.length;i++){
			int temp=L.arr[i],p;
			for(p=i-k;p>=1 && L.arr[p]>temp;p-=k) L.arr[p+k]=L.arr[p];
			L.arr[p+k]=temp;
		}
	}
}
//快速排序 
void Quick(node &L,int l,int r){
	if(l>=r) return ;
	int temp=L.arr[l];
	int i=l,j=r;
	while(i<j){
		while(i<j && L.arr[j]>=temp) j--;
		while(i<j && L.arr[i]<=temp) i++;
		swap(L.arr[i],L.arr[j]);
	}
	swap(L.arr[i],L.arr[l]);
	Quick(L,l,i-1);
	Quick(L,i+1,r); 
}
//堆调整 
void HeapAdjust(node &L,int s,int e){
	int temp=L.arr[s];
	for(int i=2*s;i<=e;i*=2){
		if(i<e && L.arr[i+1]>L.arr[i]) i++;
		if(temp>L.arr[i]) break;
		L.arr[s]=L.arr[i];
		s=i;
	}
	L.arr[s]=temp;
}
//堆排序 
void Heap(node &L){
	//建初堆 
	for(int i=L.length/2;i>0;--i) HeapAdjust(L,i,L.length);
	for(int i=L.length;i>1;--i){
		swap(L.arr[1],L.arr[i]);
		HeapAdjust(L,1,i-1);
	}
}
//排序 
void Sort(node &CL,node &DL,node &EL){
	Xier(CL);
	Quick(DL,1,DL.length);
	Heap(EL);
}
//打印排序后序列 
void Print(node CL,node DL,node EL){
	cout<<"希尔排序:\n";
	for(int i=1;i<=CL.length;i++) cout<<CL.arr[i]<<' ';
	cout<<'\n';
	cout<<"快速排序:\n";
	for(int i=1;i<=DL.length;i++) cout<<DL.arr[i]<<' ';
	cout<<'\n';
	cout<<"堆排序:\n";
	for(int i=1;i<=EL.length;i++) cout<<EL.arr[i]<<' ';
	cout<<'\n';
}
int main()
{ 
	node CL,DL,EL;
	cout<<"请输入序列长度:\n"; 
	cin>>CL.length;
	DL.length=EL.length=CL.length;
	cout<<"请输入序列:\n";
	for(int i=1;i<=CL.length;i++){
		cin>>CL.arr[i];
		DL.arr[i]=CL.arr[i];
		EL.arr[i]=CL.arr[i];
	}
	Sort(CL,DL,EL);
	Print(CL,DL,EL);
	return 0;
 }

一个好奇的人