希尔排序

本文章的代码使用jetbrains公司旗下的的Clion编写，操作系统位macOS Ventura(13.2.1). 代码没有在dev-c++测试过（dev-c++可能会有相关的空格问题）

//
// Created by 魏志杰 on 2023/7/25.
//

#include "stdio.h"
#define Max 100
#define before  printf("排序前")
#define after   printf("排序后")
#define newline printf("\n")
#define print   printf("%6d", R[i].key)
#define printA  printf("%6d",A[i])
#define Array int A[]={5,7,2,5,9,6,-42,1,67,2,3};

//希尔排序是一种分组插入的方法，其基本的思路是，先取定一个小于n的整数d，作为第一个增量，把表的全部元素分成d个组，所有距离为d的倍数的元素放在一个组里
//再在各个组里进行进行直接插入排序,然后取第二个增量d2(d2<d)重复上面的分组和排序。


typedef struct {
    int key;
    int data;
}SqType;


//希尔排序每趟并不产生有序区，在最后一趟结束之前，所有元素并不一定归位了，但是希尔排序每趟完成后，数据越来越接近有序。
//取d=n/2  d(i+1)=[di/2]
void shell(SqType R[] ,int n){  //对R[0,n-1]按递增有序进行希尔排序
   int i,j,d;
   SqType tmp;
   d=n/2;
    while (d>0){                //增量置初值
        for(i=d;i<n;i++){       //对所有相隔d位置的所有元素组采取直接插入排序
            tmp=R[i];
            j=i-d;
            while (j>=0 &&tmp.key<R[j].key){  //对相隔d位置的元素组进行排序
                R[j+d]=R[j];
                j=j-d;
            }
            R[j+d]=tmp;
        }
        d=d/2;              //减少增量
    }
}

void shellSort(int A[],int n){
// 希尔排序
        int gap, i, j, temp;
        for (gap = n / 2; gap > 0; gap /= 2) { // 定义增量序列，初始增量为数组长度的一半，然后每次缩小增量为一半
            for (i = gap; i < n; i++) {         // 对每个增量进行插入排序
                temp = A[i];
                for (j = i; j >= gap && A[j - gap] > temp; j -= gap) {
                    A[j] = A[j - gap];
                }
                A[j] = temp;

            }
        }
    }



int  main(){
    SqType R[Max];
    Array;
    for (int i = 0; i < 10; i++)
        R[i].key = A[i];
    before;
    for (int i = 0; i < 10; i++)
        print;
    newline;
    shell(R,10);
    after;
    for (int i = 0; i < 10; i++)
        print;
    newline;
    shellSort(A,10);
    after;
    for (int i = 0; i < 10; i++)
        printA;

}

结果演示如下