排序算法【希尔排序】

一、原理

（1）步长为4时候的插入排序

（2）步长为2的时候的插入排序

（3）步长为1的时候的插入排序

二、代码如下所示：

#ifndef __TEST_H__
#define __TEST_H__
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>bool check(int* ptr, int begin, int len);
int* CreateArray(int len);/* 测试排序算法的宏定义* fun:函数指针* arr:数组地址* n  :数组元素个数*/
#define TEST_MY(fun, arr, n) { \printf("Test %s: ", #fun); \int* ptr = (int*)malloc(n*sizeof(int)); \memcpy(ptr, arr, n*sizeof(int)); \long long begin = clock(); \fun(ptr, 0, n); \long long end = clock(); \if (check(ptr, 0, n)) { \printf(" ok "); \} else { \printf(" error "); \} \printf(" len:%d   Tim: %lld ms \r\n", n, (end - begin)*1000/ CLOCKS_PER_SEC); \free(ptr); \
}/** 交换两个变量值的宏定义 */#endif

#include "test.h"
#include <string.h>/* 检查数组中的数据是不是从小到大的顺序 */
bool check(int* ptr, int begin, int len)
{for (int i = begin; i < len - 2; i++){if (ptr[i] > ptr[i + 1]){return false;}}return true;
}/* 创建一个指定长度的乱序数组 */
int* CreateArray(int len)
{int* array = (int*)malloc(sizeof(int) * len);for (int i = 0; i < len; i++){array[i] = rand() % 10000;}return array;
}

#include <stdio.h>
#include "test.h"/* 插入排序 */
void insert_sort(int* arr, int begin, int len)
{int j, data;for (int i = begin + 1; i < len; i++){j = i;while (j > begin && arr[j] < arr[j - 1]){data = arr[j];arr[j] = arr[j - 1];arr[j - 1] = data;j -= 1;                 //放在最后在减少，放在最前面会出错。}}
}/* 无监督插入排序算法 */
void unguarded_insert_sort(int* arr, int begin, int len, int step)
{int data;int min_index = begin;//找到最小值for (int i = begin + step; i < len; i+= step){if (arr[i] < arr[min_index]){min_index = i;}}//向前插入，如果直接交换，就不是插入了。while (min_index > begin){data = arr[min_index];arr[min_index] = arr[min_index - step];arr[min_index - step] = data;min_index -= step;}//无监督向前插入排序for (int i = begin + 2 * step; i < len; i+= step){int j = i;while (arr[j] < arr[j - step])   //最后一次循环总是不符合条件的{data = arr[j];arr[j] = arr[j - step];arr[j - step] = data;j -= step;}}
}/* 希尔排序 */
void shell_sort(int* arr, int begin, int len)
{int k = 2, n = (len - begin), step;do{step = (n / k == 0 ? 1 : n / k);for (int i = begin; i < begin + step; i++){unguarded_insert_sort(arr, begin, len, step);}k *= 2;              //步长每次乘以2} while (step !=1);      //step的步长不为1
} void main()
{int* arr = CreateArray(10000);//TEST_MY(selection_sort, arr, 10000);TEST_MY(shell_sort, arr, 10000);/*unguarded_insert_sort(arr, 0, 10000, 1);*/printf("data:%d, %d, %d, %d\r\n", arr[0], arr[1], arr[2], arr[3]);free(arr);return;
}

运行的结果如下所示：