C语言实现插入排序与希尔排序

目录

一，插入排序

插入排序C语言实现（升序）

1，将新元素插入到有序序列

2，循环的开始与终止 

二，希尔排序

希尔排序C语言实现（升序）

1，单趟：

2，循环及终止：

---

一，插入排序

插入排序的工作方式像许多人排序一手扑克牌。开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较。拿在左手上的牌总是排序好的，原来这些牌是桌子上牌堆中顶部的牌。
插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第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[end+1];while (end >= 0 && nums[end] > temp){nums[end + 1] = nums[end];end--;}nums[end + 1] = temp;
}

 注释:

下标end表示有序序列的最后一个元素的下标，表示数组中下标0到end是有序的，temp储存的是新元素的值，也就是nums[end+1]。

为了将新元素插入到合适的位置，数组中下标为0到end+1的部分要进行数据的挪动，通过end遍历0到end这一部分元素，

如果end所指向的元素的值大于temp，则将其向后挪动一位，即nums[end + 1] = nums[end]；如果end所指向的元素的值小于temp，则end+1的位置即为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;}
}

二，希尔排序

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”，是直接插入排序算法的一种更高效的改进版本。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。

注：希尔排序之所以高效，是因为插入排序的特性（一个数组越是接近有序，插入排序就越高效（若为有序数组，时间复杂度则为O(N)）。希尔排序则依据此特性，先对数组进行数次预排序，使数组接近有序，最后再使用插入排序，完成升序

以将数组nums[9]={9,8,7,6,5,4,3,2,1}排为升序为例

初始状态：gap=9/2=4，数组分为4组，分别对每组进行插入排序

 迭代状态：gap=4/2=2，数组分为2组，分别对每组进行插入排序

终止状态：gap=2/2=1，数组分为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;}}
}