c语言插入排序算法：直接插入排序和希尔排序_c语言的插入算法

（1）直接插入排序基本思想：将待排序的元素插入到已排好序的序列中的适当位置，直到所有元素都插入完毕。

1.功能代码:

void insertionSort(int arr[], int n) {
    int i,j,key;
    //从第一个元素arr[0]开始遍历,到arr[n-1]结束，n为需要排序的元素个数
    for (i = 0; i < n; i++) {
        key = arr[i];
        j = i - 1;
       while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

2.例题：将序列{4，5，1，2，6，3}进行快速排序

#include"stdio.h"
void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 0; i < n; i++) {
        key = arr[i];
        j = i - 1;
        while (j >=0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}
int main(){
	int arr[]={4,5,1,2,6,3};
	int i;
	insertionSort(arr,6);
	for(i=0;i<6;i++){
		printf("%d ",arr[i]);
	}
	return 0;
} 

（2）希尔排序：Shell Sort，是直接插入排序的一种改进版，也称为缩小增量排序（Diminishing Increment Sort），将一个序列分成若干个子序列分别进行直接插入排序，然后逐渐减小子序列的长度，最终整个序列就被排好序了。

具体实现步骤如下：

1. 选择一个增量序列 t1，t2，……，tk，其中 ti > tj，tk = 1；

2. 每次按增量序列对元素进行分组，对每组使用直接插入排序算法排序；

3. 改变增量序列，重复第2步，直到增量序列为1。

#include"stdio.h"
void shell_sort(int arr[], int len) {
    int gap, i, j, tmp;
    for (gap = len / 2; gap > 0; gap /= 2) {  // 分组
        for (i = gap; i < len; i++) {  // 对每组进行直接插入排序
            tmp = arr[i];
            for (j = i - gap; j >= 0 && arr[j] > tmp; j -= gap) {
                arr[j + gap] = arr[j];
            }
            arr[j + gap] = tmp;
        }
    }
}
 
int main() {
    int arr[] = {50,26,38,80,70,90,8,30,40,20};
    int len = sizeof(arr) / sizeof(arr[0]);
    int i;
    printf("Before sorting:\n");
    for (i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
 
    shell_sort(arr, len);
 
    printf("After sorting:\n");
    for (i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
 
    return 0;
}

  上述代码中，首先定义了一个 shell_sort 函数来实现希尔排序，其中 len 表示数组的长度，arr 表示需要排序的数组。在 shell_sort 函数中，使用 gap 变量来表示分组的间隔，每次将 gap 减半，直到 gap 为 1，表示最后对整个序列进行一次直接插入排序。在 for 循环中，使用 i 从 gap 开始遍历整个数组，对于每一个 i，都将其与前面 gap 个元素进行比较，进行直接插入排序。比较时，如果前面的元素大于当前元素，则将前面的元素后移 gap 个位置，直到找到合适的位置插入当前元素。最后，在 main 函数中对上述代码进行了简单的测试，并输出排序前后的数组。