赞
踩
希尔排序是直接插入排序的一种优化排序算法。
通过增量step将序列分割成若干子序列【i,i + step,…,i + k*step】;
然后对子序列进行直接插入排序,使得每个子序列都有序;
最后通过不断缩小增量step,从而实现整个序列完全有序;
排序过程
简单示例,例如:
[4 7 3 8 2 6 5 1]
第一趟排序:
步长:step = 4 分组:[4 2]、[7,6]、[3 5]、[8 1]
对每一组进行直接插入排序得:[2 4]、[6,7]、[3 5]、[1 8]
整体排序后:[2 6 3 1 4 7 5 8]
第二趟排序:
步长:step = 2 分组:[2 3 4 5]、[6 1 7 8]
对每一组进行直接插入排序得:[2 3 4 5]、[1 6 7 8]
整体排序后:[2 1 3 6 4 7 5 8]
第三趟排序:
步长:step = 1 分组:[2 1 3 6 4 7 5 8]
对每一组进行直接插入排序得:[1 2 3 4 5 6 7 8]
整体排序后:[1 2 3 4 5 6 7 8]
排序结束
#include <stdio.h>
#define size 10
void ShellSort(int *num, int len)
{
int i, j, temp, step;
// 步长,每次循环缩小一倍
for (step = (len - 1) / 2; step >= 1; step /= 2)
{
// 插入排序过程,从步长第二个数开始判断是否需要插入
for (i = step; i < len; i++)
{
if (num[i - step] > num[i])
{
temp = num[i];
for (j = i - step; j > 0 && num[j] > temp; j -= step)
{
num[j + step] = num[j];
}
num[j + step] = temp;
}
}
}
}
int main()
{
int i, num[size] = {453, 357, 876, 320, 35, 53, 654, 57, 687, 5364};
ShellSort(num, size);
for ( i = 0; i < size; i++)
{
printf("%d ", num[i]);
}
printf("\n");
return 0;
}
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。