长春市建设工程信息网站,电子工程师,网站建设怎么找客源,网站开发劣势目录
一#xff0c;插入排序
插入排序C语言实现#xff08;升序#xff09;
1#xff0c;将新元素插入到有序序列
2#xff0c;循环的开始与终止
二#xff0c;希尔排序
希尔排序C语言实现#xff08;升序#xff09;
1#xff0c;单趟#xff1a;
2#x…目录
一插入排序
插入排序C语言实现升序
1将新元素插入到有序序列
2循环的开始与终止
二希尔排序
希尔排序C语言实现升序
1单趟
2循环及终止 一插入排序
插入排序的工作方式像许多人排序一手扑克牌。开始时我们的左手为空并且桌子上的牌面向下。然后我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置我们从右到左将它与已在手中的每张牌进行比较。拿在左手上的牌总是排序好的原来这些牌是桌子上牌堆中顶部的牌。 插入排序是指在待排序的元素中假设前面n-1(其中n2)个数已经是排好顺序的现将第n个数插到前面已经排好的序列中然后找到合适自己的位置使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入直到整个序列排为有序的过程称为插入排序。
以将数组nums[9]{9,8,7,6,5,4,3,2,1}排为升序为例 现在有九张扑克我们摸到第一张9之后我们认为一张牌就是有序的然后我们摸到第二张牌8为了将手中的牌排为升序小的牌放左边大的牌放右边我们首先要比较摸到的牌和原先手里的牌的大小关系发现8比9小要放在9的左边。以此类推每次都将摸到的牌与手里的牌进行比较找到新牌合适的位置进行插入。
注意因为从摸到第一张牌开始手里的牌就是有序的所以手里的牌是有序的
插入排序C语言实现升序
可以发现将新的元素插入到已经有序的序列中是一个循环过程直到不再有要插入的元素
1将新元素插入到有序序列
首先我们要清楚新元素就是再有序序列之后的第一个元素这个新元素和有序序列都是数组的元素。之所以要强调有序序列和新元素这两个概念是为了更加直观的感受插入的过程
//代码不完整仅仅示例
void InsetSort(int* nums, int numsSize)
{int end;int temp nums[end1];while (end 0 nums[end] temp){nums[end 1] nums[end];end--;}nums[end 1] temp;
} 注释:
下标end表示有序序列的最后一个元素的下标表示数组中下标0到end是有序的temp储存的是新元素的值也就是nums[end1]。
为了将新元素插入到合适的位置数组中下标为0到end1的部分要进行数据的挪动通过end遍历0到end这一部分元素
如果end所指向的元素的值大于temp则将其向后挪动一位即nums[end 1] nums[end]如果end所指向的元素的值小于temp则end1的位置即为temp的位置 2循环的开始与终止
当end为0时通过将新元素插入到有序序列中使得数组下标0到1的部分变为有序那么为了使整个数组有序end需要从0到numsSize-1逐步进行插入新元素循环结束则排序完成 void InsetSort(int* nums, int numsSize)
{for (int i 0; i numsSize - 1; i){int end i;int temp nums[i 1];while (end 0 nums[end] temp){nums[end 1] nums[end];end--;}nums[end 1] temp;}
}
二希尔排序
希尔排序(Shells Sort)是插入排序的一种又称“缩小增量排序”是直接插入排序算法的一种更高效的改进版本。 希尔排序是把记录按下标的一定增量分组对每组使用直接插入排序算法排序随着增量逐渐减少每组包含的关键词越来越多当增量减至 1 时整个文件恰被分成一组算法便终止。
注希尔排序之所以高效是因为插入排序的特性一个数组越是接近有序插入排序就越高效若为有序数组时间复杂度则为O(N)。希尔排序则依据此特性先对数组进行数次预排序使数组接近有序最后再使用插入排序完成升序
以将数组nums[9]{9,8,7,6,5,4,3,2,1}排为升序为例
初始状态gap9/24数组分为4组分别对每组进行插入排序 迭代状态gap4/22数组分为2组分别对每组进行插入排序 终止状态gap2/21数组分为1组分别对每组进行插入排序即对整个数组进行插入排序 希尔排序C语言实现升序
1单趟
每个分组根据增量gap划分之间进行插入排序
2循环及终止
增量是变化的当变为1时完成排序并结束
void ShellSort(int* nums, int numsSize)
{for (int gap numsSize / 2; gap 1; gap / 2){for (int i 0; i numsSize - gap; i){int end i;int temp nums[end gap];while (end 0 nums[end] temp){nums[end gap] nums[end];end - gap;}nums[end gap] temp;}}
}
