网站设计跟网页制作,西安模板建网站,wordpress自适应手机,建设企业网站进去无法显示1.基本思想 直接插入排序是一种简单的插入排序法#xff0c;其基本思想是#xff1a;把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中#xff0c;直到所有的记录插入完为止#xff0c;得到一个新的有序序列。 实际中我们玩扑克牌时#xff0c;就用…1.基本思想 直接插入排序是一种简单的插入排序法其基本思想是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列。 实际中我们玩扑克牌时就用了插入排序的思想 2.直接插入排序 当插入第 i(i1) 个元素时前面的 array[0],array[1],…,array[i-1] 已经排好序此时用 array[i] 的排序码与 array[i-1],array[i-2],… 的排序码顺序进行比较找到插入位置即将 array[i] 插入原来位置上的元素顺序后移。 3.代码实现
// 直接插入排序函数
// 参数a是待排序数组的指针n是数组的元素个数
void InsertSort(int* a, int n)
{// 外层循环遍历从0到n - 2的元素因为最后一个元素不需要再插入for (int i 0; i n - 1; i){// end指向当前已排好序部分的最后一个元素int end i;// 暂存当前待插入的元素即end 1位置的元素int tmp a[end 1];// 内层循环从end位置开始向前比较将大于tmp的元素向后移动while (end 0){// 如果当前end位置的元素大于tmpif (a[end] tmp){// 将a[end]向后移动一个位置a[end 1] a[end];// end向前移动一个位置继续向前比较end--;}else//end 0时意味着在已排序序列中当前待插入元素tmp的值是最小的{// 当遇到不大于tmp的元素时说明找到了tmp的插入位置跳出循环break;}}// 将tmp插入到正确的位置a[end 1] tmp;}
}
4.小试牛刀 题目链接P1223 排队接水 - 洛谷 4.1解题思路 这道题的核心思路是让接水时间短的人先接水从而使总的等待时间最短平均等待时间也最小。 4.2代码 本题可使用多种排序方法这里我使用的是插入排序
#includestdio.h
//定义个人结构体
typedef struct
{int number;//编号int time;//接水时间
}Person;
void InsertSort(Person* arr,int n)
{for(int i0;in-1;i){int endi;//数组中的第二个元素为待排序的对象默认第一个元素已排序Person tmparr[end1];while(end0){if(arr[end].timetmp.time){arr[end1]arr[end];end--;}else{break;}}arr[end1]tmp;}
}
main()
{int n;//排队人数Person people[1001]{0};double total;scanf(%d,n);for(int i0;in;i){scanf(%d,people[i].time);//实际编号为数组编号加1people[i].numberi1;}InsertSort(people,n);//输出队列序号for (int i 0; i n; i){printf(%d ,people[i].number);}//计算排队时间并输出for(int i1;in;i){for(int j0;ji;j){totalpeople[j].time;}}printf(\n%lf,total/(n));
}
5.疑难解答 5.1为什么第一层循环结束条件为in-2 直接插入排序的基本思想是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列。 初始时我们可以把数组的第一个元素看作是一个已经排好序的单元素序列。从第二个元素开始依次将每个元素插入到前面已排好序的序列中的合适位置。 当我们处理到数组的倒数第二个元素即索引为 n - 2 的元素时经过这一轮插入操作后前面 n - 1 个元素已经是有序的了。此时数组中只剩下最后一个元素索引为 n - 1 的元素还未插入到有序序列中。 由于前面 n - 1 个元素已经有序那么对于最后一个元素我们只需要将它与前面 n - 1 个有序元素进行比较并插入到合适位置即可不需要再进行一轮新的外层循环来处理它。所以外层循环只需要遍历到索引为 n - 2 的元素即 for (int i 0; i n - 1; i)这样就能保证整个数组最终被排序。 举个例子对于数组 [4, 2, 1, 3] 1. 初始时把 4 看作已排好序的序列。 2. 外层循环第一次i 0将 2 插入到 [4] 中得到 [2, 4]。 3. 外层循环第二次i 1将 1 插入到 [2, 4] 中得到 [1, 2, 4]。 4. 外层循环第三次i 2将 3 插入到 [1, 2, 4] 中得到 [1, 2, 3, 4]此时数组已经有序不需要再处理最后一个元素的插入了。 -------有问题欢迎私信和评论------
