希尔排序

伪代码  https://www.bilibili.com/video/av53359021?from=search&seid=15772003084039500629

代码转自：   https://www.cnblogs.com/wuyudong/p/shell-sort-algorithm.html

代码为：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
void shellsort(int a[], int n)
{
	int gap = n / 2;
	while (gap > 0)
	{
		for (int i = gap; i < n; i++)
		{
			int t = a[i];
			int j = i - gap;
			while (j >= 0 && t < a[j])
			{
				a[j + gap] = a[j];
				j -= gap;
			}
			a[j + gap] = t;
		}
		gap /= 2;
	}
}
int main(void)
{
#define N 100
	int a[N] = { 0 };
	int n; scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	
	shellsort(a, n);
	for (int i = 0; i < n; i++)
		printf("%d ",a[i]);
	puts("");
	
	system("pause");
	return 0;
}

一，

　思路：　希尔排序是先排序 间隔大的子序列，再排序 间隔小的子序列。

这样的好处：

   　gap 值较大时：子序列中对象较少，速度较快

   　gap 值较小时：子序列中对象变多，但大多数对象基本有序，所以还是很快的

 二，

那么针对每个 gap 具体怎么排序呢？

对于给定 gap ,我们忽略那些不相干的数字，其实我们是在对子序列做 插入排序

　　　　　for (int i = gap; i < n; i++)
        {
            int t = a[i];
            int j = i - gap;
            while (j >= 0 && t < a[j])
            {
                a[j + gap] = a[j];
                j -= gap;
            }
            a[j + gap] = t;
        }
        gap /= 2;

所以这一段的实质是在对 间隔一定大小的元素做插入排序。

以下是提取出来子序列做 插入排序 流程图

三， 我对插入排序的理解

j 指向 一个排好的数组的末位，i 指向要插入的元素

先将 a[i] 值保存下来，在跟数组一个一个的比较看一下应该放在哪里。

由于数组排好序，只要遇到一个比他大就就把这个数往后移，一旦遇到比他小的就说明 该元素 正确的位置 在这个比他小的后一位没跑了

所以 将保存好的值 赋给此时 j 的后一位，就 ok 了

============================================

When you treasure your past, are satisfied with your present, and are optimistic about your future, you are on the top of your life.When you understand that success will not make you, failure will not destroy you, flat will not drown you, you stand on the highest point of life.

当你珍惜自己的过去，满意自己的现在，乐观自己的未来时，你就站在了生活的最高处。 当你明了成功不会造就你，失败不会击垮你，平淡不会淹没你时，你就站在了生命的最高处。