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