设计素材网站无版权,微信小程序开发大赛,fullpage wow做的网站,湖北城乡住房建设厅网站怎查证件一.改进冒泡排序 在冒泡排序中#xff0c;记录的比较和移动是在相邻单元中进行的#xff0c;记录每次交换只能上移或下移一个单元#xff0c;因而总的比较次数和移动次数比较多。 改进的着眼点#xff1a; 1.减少总的比较次数和移动次数 2.增大记录的比较和移动距离 3.较大…一.改进冒泡排序 在冒泡排序中记录的比较和移动是在相邻单元中进行的记录每次交换只能上移或下移一个单元因而总的比较次数和移动次数比较多。 改进的着眼点 1.减少总的比较次数和移动次数 2.增大记录的比较和移动距离 3.较大记录从前面直接移动到后面较小记录从后面直接移动到前面 二.快速排序的基本思想 首先选取一个轴值通过一趟排序将待排序记录分割成独立的两部分前一部分记录的关键码均小于或等于轴值后一部分记录的关键吗均大于或等于轴值然后分别对这两部分重复上述方法直到整个序列有序。 三.需要解决的关键问题 1.如何选取轴值
1选取第一个元素
2选取最后一个元素
3选取第一个、最后一个、中间元素中值为中间的那个元素 2.如何实现分割一次划分 设待划分的序列是r[s]~r[t],设参数ij分别指向子序列左右两端的下标s和t令r[s]为轴值。
1j从后向前扫描直到r[j]r[s],将r[j]移动到r[i]的位置使关键码小的记录移动到前面去
2i从前向后扫描直到r[i]r[j],将r[i]移动到r[j]的位置使关键码大的记录移动到后面去
3重复上述操作直到ij 四.代码 int partition(int a[],int first,int end){int ifirst,jend,temp;while(ij){while(ija[j]a[i]){--j;}if(ij){tempa[i];a[i]a[j];a[j]temp;}while(ija[j]a[i]){i;}if(ij){tempa[i];a[i]a[j];a[j]temp;}}return i;//ij时返回轴值
}void quickSort(int a[],int first,int end){if(firstend){int pospartition(a,first,end);quickSort(a, first, pos-1);quickSort(a, pos1, end);}
}五.时间性能分析 1最好情况
每次轴值都能选取到最中间的元素
Onlog2n 2最坏情况
每次都选取到最大/最小的元素
On^2)
