江苏省建设工程一站式申报网站,软件工程培训机构哪家好,城市网站联盟,网易163企业邮箱格式选择排序#xff1a;每趟从待排序的记录中选出关键字最小的记录#xff0c;顺序放在已排序的记录序列末尾#xff0c;直到全部排序结束为止。 选择排序正如定义所讲#xff0c;在数组查询出最小值#xff0c;然后放在此次循环开始位置#xff08;前一次循环已经获取比它更…选择排序每趟从待排序的记录中选出关键字最小的记录顺序放在已排序的记录序列末尾直到全部排序结束为止。 选择排序正如定义所讲在数组查询出最小值然后放在此次循环开始位置前一次循环已经获取比它更小的值放在前面。 简单选择排序就是单纯的从数组中一次一次循环获取到最小值放到循环位置。而堆排序正如名字是从一个堆中选择然后放在堆的循环开始位置所以重点就是如何争取获取堆分组。 一、简单选择排序 1、算法思想 正如图上所示每次选择最小值然后放在本次循环的开始位置。 2、代码 //选择排序
void SortAlgorithm::SelectSort(pSqlList pList)
{int i,j,min;printf(开始验证选择排序);//选择排序和低级冒泡排序很像关键就是在比较时低级冒泡进行数据交换而选择排序进行记录最后只交换一次for (i 0;ipList-length;i){min i;for(j pList-length-1;ji;j--){//注意数组坐标千万别溢出if (pList-SqlArray[min] pList-SqlArray[j]){min j;}}//最后进行交换先选择最小的最后一次交换swap(pList,i,min);PrintSqlList(pList);}} 简单选择排序算法海华丝比较简单关键点就是遍历寻找最小记录然后入循环开始位置进行交换。 二、堆排序 1、堆排序概念 堆排序是首先引入完全二叉树的概念就是构建完全二叉树前提是完全二叉树是有特点的也就是大根堆和小根堆。 上图是完全二叉树在完全二叉树中有几个性质 设当前元素在数组中以R[i]表示那么 (1) 它的左孩子结点是R[2*i1]; (2) 它的右孩子结点是R[2*i2]; (3) 它的父结点是R[(i-1)/2]; (4) R[i] R[2*i1] 且 R[i] R[2i2]。 大根堆每个结点的关键字都不小于其孩子结点的关键字。 小根堆每个结点的关键字都不大于其孩子结点的关键字。 2、算法思想 1根据初始数组去构造初始堆默认是大根堆构建一个完全二叉树保证所有的父结点都比它的孩子结点数值大。 2每次交换第一个和最后一个元素输出最后一个元素最大值然后把剩下元素重新调整为大根堆。 上述算法是个循环操作先构建然后交换输出最后调整余下的为大根堆其实就是寻找最大值其实只需要左右两个结点那个比较大就获取那个所以调整堆排序也是比较简单就是比较左右结点获取最大值 第一步构建大根堆 第二步、输出、调整 3、代码 ////堆排序
void SortAlgorithm::HeapSort(pSqlList pList)
{//循环构建堆for (int i pList-length/2;i0;i--){AdjustHeap(pList,i,pList-length-1);}PrintSqlList(pList);for (int i pList-length-1;i1;i--){//循环输出根节点同时再次调整为大根堆swap(pList,1,i); //根节点位于最前面也就是1这样就将1最大值放在数组后面了AdjustHeap(pList,1,i-1);PrintSqlList(pList);}
}
inline void SortAlgorithm::AdjustHeap(pSqlList pList,int start,int length)
{int temp pList-SqlArray[start]; //这是分支节点然后比较它的分支节点也就是2ifor (int i 2*start;ilength;i i*2){//获取左右结点中比较大的值的坐标if (ilength pList-SqlArray[i] pList-SqlArray[i1]){i;}//如果根节点本来就大无序调整if (temp pList-SqlArray[i]){break;}//交换值将左右结点大值放在根节点pList-SqlArray[start] pList-SqlArray[i];start i;}//将开始需要比较的值放在最后交换出的位置上pList-SqlArray[start] temp;} 4、代码分析 程序中一开始构建调整大根堆最大值是length/2因为从完全二叉树的概念上分析 在上图中大根堆的建立就是调整前四个元素的位置就是放再分支节点上还是叶子结点上所以只要输入4即可。 一开始大根堆发现是90在最前面。 首先将位于第一位根节点树最大然后和最后一位交换然后调整前8位第九位已经是最大了。 然后再讲获取到的80和最后一位第九位第十已经不需交换然后调整前7位当然都是从1开始了。 最后经过一次次循环调整完成算法的排序。 其中关键的思想是获取调整堆排序比如一开始90和20交换后20位于第一位置此时20和左右结点中的较大值80交换关键是后续继续拿20和后面左右结点比较直到break也就是找到比它小的跳出然后赋值。 三、性能分析 1、简单选择排序 从简单选择排序的过程来看它最大的特点就是交换移动数据次数相当少这样也就节约了相应的时间。分析它的时间复杂度无论最好最差的情况其比较次数都是一样多第i趟排序需要进行n-i次关键字的比较此时需要n-1 ...1 n(n - 1)/2次。而对于交换次数而言当最好的时候交换次数为0最差的时候也就初始降序时交换次数为n-1次。总的时间复杂度依然为O(n2)。 尽管简单选择排序与冒泡排序同为O(n2)但简单选择排序的性能上还是要优于冒泡排序的。 2、堆排序 堆排序是一种不稳定的排序方法。 因为在堆的调整过程中关键字进行比较和交换所走的是该结点到叶子结点的一条路径。 在程序运行时主要消耗在初始化构建堆和重建堆的反复刷选上。在初始化构建堆时是从非终结点开始其实比较两次本来时n/2这样最多对n/2进行两次比较工作所以初始化构建大根堆是O(n)。 在调整构建堆时第i次构建树logI根据完全二叉树性质需要遍历N-1记录,所以时间复杂度是O(nlogn)转载于:https://www.cnblogs.com/polly333/p/4816828.html
