博客

简单选择排序（不稳定）

时间复杂度O(n2)

#include<iostream>
using namespace std;
void swap(int &a,int &b)
{
	int temp;
	temp=a;
	a=b;
	b=temp;
}
void selectsort(int a[],int n)
{
	for(int i=0;i<n;i++)
	{
		int k=i;
		for(int j=i+1;j<n;j++) //寻找最小值    
		    if(a[k]>a[j])
	                k=j;
		if(k!=i)             
		     swap(a[i],a[k]);  //最小值与待排数据交换位置
	}
}
int main()
{
	int a[]={1,5,3,51,24,0};
	selectsort(a,6);
	for(int i=0;i<6;i++)
	cout<<a[i]<<" ";
}

堆排序（不稳定）

只能用于顺序排序，不能用于链式排序

时间复杂度O(nlog2n)

#include<iostream>
using namespace std;
void HeapAdjust(int a[],int s,int m)//筛选法调整堆（大顶堆）
{
	int tmp,j;
	tmp=a[s];
	for(j=2*s;j<=m;j*=2)      //筛选较大的孩子结点
	{
		if(j<m&&a[j]<a[j+1])
		++j;
		if(tmp>=a[j])
		break;
		a[s]=a[j]; s=j;
	}
	a[s]=tmp;                 //交换位置
}
void CreatHeap(int a[],int n) //建初堆（一个结点的树必是堆，完全二叉树中，所有序号大于n/2的结点都是叶子）
{
	for(int i=n/2;i>0;--i)    
	HeapAdjust(a,i,n);
}
void HeapSort(int a[],int n)  //堆排序
{
	int i,x;
	CreatHeap(a,n);
	for(i=n;i>1;--i)
	{                         //将堆顶值与最后序号的值交换位置
	x=a[1];
	a[1]=a[i];
	a[i]=x;
	HeapAdjust(a,1,i-1);
	}
}
int main()
{
	int a[9]={0,49,38,65,97,76,13,27,49};
	HeapSort(a,8);            //将数组从下标为1的位置开始存储数字 
	for(int i=1;i<9;i++)
	cout<<a[i]<<" ";
}