烟台免费网站建站模板,办公室装修大概多少钱一平方,简单logo设计图片,川畅科技搜搜 网站设计简介#xff1a;每一趟选择最小或最大的一个#xff0c;排在前面或后面。主要右简单选择排序和堆排序
一、简单选择排序
1.1简介#xff1a; 每趟选择最小的#xff0c;放在前面#xff0c;一次类推#xff0c;代码思想#xff1a;两个循环#xff0c;外循环是趟数每一趟选择最小或最大的一个排在前面或后面。主要右简单选择排序和堆排序
一、简单选择排序
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(i0;in-1;i)//趟数 {int mini;for(ji1;jn;j)//查找本趟中最小的一个位置更新min {if(a[j]a[min])minj;}//如果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个。 1.1.2.根堆的插入和删除 插入的新元素要放在表尾然后再根据大根堆或小根堆原则进行堆调整即可。 在堆中删除元素直接删除然后用堆尾的元素补到删除位置处随后再根据大根堆或小根堆原则进行堆调整即可。
1.1.3.性能 时间复杂度O() 空间复杂度O(1) 稳定性不稳定可能给后面相同关键字调整到前面相对位置发生改变 选择性遇到选出前多少个元素的算法选择堆排序最优。
1.2代码
1.2.1.初始化大根堆代码
//整体大根堆初始化
void BulidMaxHeap(int *a,int len)
{int i;for(ilen/2;i0;--i)//从最后一个非叶子结点开始依次往前遍历每次遍历的时候进行堆调整 {HeadAdjust(a,i,len); }
}
//大根堆调整
void HeadAdjust(int *a,int k,int len)
{a[0]a[k];//a[0]存储原来k的值 int i;for(i2*k;ilen;ii*2)//判断以k为根的两个孩子谁打 {if(ilen a[i]a[i1])i;//为了防止原a[k]乱跑拿a[0]进行比较if(a[0]a[i]) break; //让根与孩子比较如果根大于孩子则符合大根堆 else//不符合的话 {a[k]a[i];//让大的孩子赋值给根覆盖掉 ki; //然后给原根的坐标挪到孩子处 } } a[k]a[0];//原根的坐标挪到孩子处进入第二轮循环ii*2,新的堆看是否符合大根堆
}
1.2.2.大根堆排序
void HeadSort(int *a,int len)
{BulidMaxHeap(a,len);//初始化大根堆//排序int i;for(ilen;i0;--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(i1;in;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(ilen/2;i0;--i)//从最后一个非叶子结点开始依次往前遍历每次遍历的时候进行堆调整 {HeadAdjust(a,i,len); }
}
//大根堆调整
void HeadAdjust(int *a,int k,int len)
{a[0]a[k];//a[0]存储原来k的值 int i;for(i2*k;ilen;ii*2)//判断以k为根的两个孩子谁打 {if(ilen a[i]a[i1])i;//为了防止原a[k]乱跑拿a[0]进行比较if(a[0]a[i]) break; //让根与孩子比较如果根大于孩子则符合大根堆 else//不符合的话 {a[k]a[i];//让大的孩子赋值给根覆盖掉 ki; //然后给原根的坐标挪到孩子处 } } a[k]a[0];//原根的坐标挪到孩子处进入第二轮循环ii*2,新的堆看是否符合大根堆
} void HeadSort(int *a,int len)
{BulidMaxHeap(a,len);//初始化大根堆//排序int i;for(ilen;i0;--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;}
