选择排序

简单选择排序

简单选择排序不能再简单了，基本思想就是先外层循环n，作用是每循环一遍找出一个数最小的（分为无序区和有序区），在无序区中找到最小的那个数，再给到有序区。当然，找到无序区中最小的数那样也需要在无序区中在循环遍历一遍，这样时间复杂度就是o（n2），是稳定排序。 下面贴出教材的简单选择排序代码

代码语言：javascript复制

void SelectSort(RecType R[],int n)
{
	int i,j,k;
	RecType temp;
	for (i=0;i<n-1;i  )    	 	//做第i趟排序
	{
		k=i;
		for (j=i 1;j<n;j  )  	//在当前无序区R[i..n-1]中选key最小的R[k]
			if (R[j].key<R[k].key)
				k=j;           	//k记下目前找到的最小关键字所在的位置
			if (k!=i)          		//交换R[i]和R[k]
			{
				temp=R[i];
				R[i]=R[k];
				R[k]=temp;  
			}
		printf("  i=%d: ",i); DispList(R,n);
	}
}

堆排序

下面贴出教材的堆排序代码

代码语言：javascript复制

void sift(RecType R[],int low,int high)
{
	int i=low,j=2*i;     					//R[j]是R[i]的左孩子
	RecType temp=R[i];
	while (j<=high) 
	{
		if (j<high && R[j].key<R[j 1].key) 	//若右孩子较大,把j指向右孩子
			j  ;    						//变为2i 1
		if (temp.key<R[j].key) 
		{
			R[i]=R[j];              		//将R[j]调整到双亲结点位置上
			i=j;                    		//修改i和j值,以便继续向下筛选
			j=2*i;
		}
		else break;                 		//筛选结束
	}
	R[i]=temp;                      		//被筛选结点的值放入最终位置
}
 
void HeapSort(RecType R[],int n)
{
	int i;
	RecType tmp;
	for (i=n/2;i>=1;i--)	//循环建立初始堆,调用sift算法 n/2 次
		sift(R,i,n); 
	printf("初始堆:"); DispList1(R,n);
	for (i=n;i>=2;i--)		//进行n-1趟完成推排序,每一趟堆排序的元素个数减1
	{	tmp=R[1];			//将最后一个元素与根R[1]交换
		R[1]=R[i];
		R[i]=tmp;
		printf("第%d趟: ",n-i 1); DispList1(R,n);
		sift(R,1,i-1);		//对R[1..i-1]进行筛选,得到i-1个节点的堆
		printf("筛选为:"); DispList1(R,n);
	}
}
 
 
int main()
{
	int n=10;
	RecType R[MAXL];
	KeyType a[]={15,18,29,12,35,32,27,23,10,20};
	CreateList1(R,a,n);
	printf("排序前:"); DispList1(R,n);
	HeapSort(R,n);
	printf("排序后:"); DispList1(R,n);
	return 1;
}

废江博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 转载请注明原文链接：选择排序

遍历 博客 排序

0 人点赞