C语言排序算法实战：直接插入与希尔排序详解

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

// 辅助函数：打印数组状态
void Print(int* a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
 
// 直接插入排序函数
void InsertSort(int *a, int n)
{
	for (int i = 0; i < n - 1; ++i)
	{
		int end = i;
		int tmp = a[end + 1]; // 暂存当前待插入的元素
		
		// 从右向左寻找插入位置
		while (end >= 0)
		{
			if (a[end] > tmp) // 若前一个元素大于待插入值，则后移
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break; // 找到合适位置，跳出循环
			}
			// 注意：原代码在此处有赋值逻辑陷阱，此处根据标准逻辑修正
			// 只有发生移动时才需后续处理，或者统一在循环结束后处理
		}
		
		// 将暂存的值放入最终确定的空位
		// 由于end可能减了多次，正确的位置是 end + 1
		if (a[end + 1] != tmp) { 
           a[end + 1] = tmp;
       }
       // 更简洁的写法通常将 tmp 赋值放在 while 循环外部或内部特定分支
       // 下面提供一个更严谨的原版逻辑复现修正版：
		/* 
		// 修正后的标准逻辑结构：
		int end = i;
		int x = a[end+1];
		while(end >= 0 && a[end] > x) {
            a[end+1] = a[end];
            end--;
        }
        a[end+1] = x;
        */
		// 鉴于原代码结构的特殊性，以下保留原文的核心流程但修复逻辑漏洞：
	}
	Print(a, n);
}
 
int main()
{
	int a[] = { 5, 2, 4, 6, 1, 3 };
	int n = sizeof(a) / sizeof(a[0]);
	
	// 执行排序
	InsertSort(a, n);
	return 0;
}

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

// 复用上面的Print函数
void Print(int* a, int n)
{
    for (int i = 0; i < n; ++i) printf("%d ", a[i]);
    printf("\n");
}

// 希尔排序实现
void ShellSort(int* a, int n)
{
    int gap = n;
    // 只要 gap > 1 就进行预排序
    while (gap > 1)
    {
        gap = gap / 2; // 更新间隔
        
        // 对每个组进行直接插入排序
        // 起始点 i 从 0 到 n-gap-1，确保 a[i+gap] 不越界
        for (int i = 0; i < n - gap; i++)
        {
            int end = i;
            int tmp = a[end + gap]; // 暂存待插入元素
            
            while (end >= 0)
            {
                if (a[end] > tmp) // 同组的前驱元素较大，则后移
                {
                    a[end + gap] = a[end];
                    end -= gap;     // 向前跳跃 gap 继续比较
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = tmp; // 插入到正确位置
        }
    }
    Print(a, n);
}

int main()
{
    int a[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
    int n = sizeof(a) / sizeof(a[0]);
    
    ShellSort(a, n);
    return 0;
}