22-数据结构-内部排序-选择排序

简介：每一趟选择最小或最大的一个，排在前面或后面。主要右简单选择排序和堆排序

一、简单选择排序

1.1简介：

        每趟选择最小的，放在前面，一次类推，代码思想：两个循环，外循环是趟数，内循环是选择最小下标，最后进行交换值，达到排序的目的。

        时间复杂度：O()

        空间复杂度：O(1)

        稳定性：不稳定，交换时，可能与另一个关键字相同的位置发生改变，

        适用性：顺序表，链表都可以

        比较次数与初始序列无关：基数排序、简单选择排序，折半插入排序

1.2代码：

#include <stdio.h>
void swap(int *a,int *b)
{
	int temp=(*a);
	(*a)=(*b);
	(*b)=temp;
}
void SelectSort(int *a,int n)
{
	int i,j;
	for(i=0;i<n-1;i++)//趟数 
	{
		int min=i;
		for(j=i+1;j<n;j++)//查找本趟中最小的一个位置，更新min 
		{
			if(a[j]<a[min])
				min=j;
		}
		//如果min跟开始不同，则交换位置 
		if(min!=i) swap(&a[min],&a[i]);
	}
}
int main()
{
	int a[6]={5,6,8,9,1,2};
	SelectSort(a,6);
	PrintSort(a,6);
	return 0;
 } 

二、堆排序

1.1简介：

        堆分为大根堆和小根堆。大根堆为：逻辑上，是个二叉树，给一维数组按层次遍历，弄成二叉树，然后大根堆是每个子树的根都比左右孩子大。同理小根堆每个子树的根都比左右孩子小。

1.1.1.大小根堆堆排序

1. 堆调整，即从最后一个非叶子结点开始，自下而上，自右而左，以非叶子结点为根，在其树中找最大的，作为根，然后调整，最后调整到整个树的根后，再整体看是否需要再调整，最后所有的根都是其所在树的最大结点为止。
2. 给最大值沉底。初始化调整完，就给第一个元素和最后一个元素互换，此时给最大值换到了最后面，下次再大根堆调整就不带上这个最大值了，每次调整完，互换后，长度减1个。

1.1.2.根堆的插入和删除

        插入的新元素要放在表尾，然后再根据大根堆或小根堆原则，进行堆调整即可。

        在堆中删除元素，直接删除，然后用堆尾的元素补到删除位置处，随后再根据大根堆或小根堆原则，进行堆调整即可。

1.1.3.性能

        时间复杂度：O()

        空间复杂度：O(1)

        稳定性：不稳定，可能给后面相同关键字调整到前面，相对位置发生改变

        选择性：遇到选出前多少个元素的，算法选择堆排序最优。

1.2代码：

1.2.1.初始化大根堆代码

//整体大根堆初始化
void BulidMaxHeap(int *a,int len)
{
	int i;
	for(i=len/2;i>0;--i)//从最后一个非叶子结点开始，依次往前遍历，每次遍历的时候进行堆调整 
	{
		HeadAdjust(a,i,len); 
	}
}
//大根堆调整
void HeadAdjust(int *a,int k,int len)
{
	a[0]=a[k];//a[0]存储原来k的值 
	int i;
	for(i=2*k;i<=len;i=i*2)//判断以k为根的两个孩子谁打 
	{
		if(i<len && a[i]<a[i+1])
		i++;
        //为了防止原a[k]乱跑，拿a[0]进行比较
		if(a[0]>=a[i]) break; //让根与孩子比较，如果根大于孩子，则符合大根堆 
		else//不符合的话 
		{
			a[k]=a[i];//让大的孩子，赋值给根，覆盖掉 
			k=i;	 //然后给原根的坐标挪到孩子处， 
		} 	
	}	
    a[k]=a[0];//原根的坐标挪到孩子处，进入第二轮循环，i=i*2,新的堆看是否符合大根堆 
} 

1.2.2.大根堆排序

void HeadSort(int *a,int len)
{
	BulidMaxHeap(a,len);//初始化大根堆
	//排序
	int i;
	for(i=len;i>0;--i)
	{
		swap(&a[1],&a[i]);
		HeadAdjust(a,1,i-1);//交换后最大值沉底，再进行大根堆调整时，不需要计算最后一个了所以长度为i-1；
} 

1.3.总代码：
 

#include <stdio.h>
//打印大根堆，从下标1打印，0处为哨兵，存储原二叉树，根的值
void  PrintSort(int *a,int n)
{
	int i;
	for(i=1;i<n;i++)
	{
		printf("%d ",a[i]);
	}
	printf("\n");
}
//交换
void swap(int *a,int *b)
{
	int temp=(*a);
	(*a)=(*b);
	(*b)=temp;
}
//堆排序 
//整体大根堆初始化
void BulidMaxHeap(int *a,int len)
{
	int i;
	for(i=len/2;i>0;--i)//从最后一个非叶子结点开始，依次往前遍历，每次遍历的时候进行堆调整 
	{
		HeadAdjust(a,i,len); 
	}
}
//大根堆调整
void HeadAdjust(int *a,int k,int len)
{
	a[0]=a[k];//a[0]存储原来k的值 
	int i;
	for(i=2*k;i<=len;i=i*2)//判断以k为根的两个孩子谁打 
	{
		if(i<len && a[i]<a[i+1])
		i++;
        //为了防止原a[k]乱跑，拿a[0]进行比较
		if(a[0]>=a[i]) break; //让根与孩子比较，如果根大于孩子，则符合大根堆 
		else//不符合的话 
		{
			a[k]=a[i];//让大的孩子，赋值给根，覆盖掉 
			k=i;	 //然后给原根的坐标挪到孩子处， 
		} 	
	}	
    a[k]=a[0];//原根的坐标挪到孩子处，进入第二轮循环，i=i*2,新的堆看是否符合大根堆 
} 
 
void HeadSort(int *a,int len)
{
	BulidMaxHeap(a,len);//初始化大根堆
	//排序
	int i;
	for(i=len;i>0;--i)
	{
		swap(&a[1],&a[i]);
		HeadAdjust(a,1,i-1);//每次排序排一个，随后以1为根的二叉树，进行堆调整	
	} 
} 
int main()
{
	int a[9]={0,53,45,87,32,17,65,78,9};
	HeadSort(a,8);//数组和有效数据
	PrintSort(a,9);//数组和数组长度
	return 0;
 }