希尔(shell)排序:分组后(间隔式的分组)利用直接插入排序
简单来说就是,插入排序是间隔为一的数字之间进行比较,但希尔排序是间隔为gap的数字为一组,先进行一次插入排序,再不断缩小gap的值,重复以上操作。直到最后一个gap的值为1(分组数不是确定的,但在以后一定是1,才能保证有序)。
最好的情况是序列基本有序,且分组数为1,时间复杂度为:O(n)。
最坏的情况的时间复杂度:O(n)。(时间复杂度与选定的分组数有关)
稳定性(不稳定):希尔排序是特殊的插入排序,插入排序是相邻数字进行比较,等大的数字不交换顺序,所以是稳定的拍寻,但希尔排序:由于是分组排序,交换的过程中进行了跳跃式的交换,相同的元素可能在各自的插入排序中移动,改变了等大数字的先后顺序,所以是一个不稳定的排序。
代码如下:
//gap:分组数
void Shell(int* arr, int len, int gap)
{
int tmp;//保存当前需要处理的值
int j;
for (int i = gap; i < len; i++)//从"第二个"元素开始
{
tmp = arr[i];
for (j = i - gap; j >= 0; j -= gap)
{
if (arr[j] > tmp)
arr[j + gap] = arr[j];
else
break;
}
arr[j + gap] = tmp;
}
}
//打印函数
void show(int* arr, int len)
{
for (int i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
int arr[] = { 4,6,2,8,9,0,1,7,3,5 };
ShellSort(arr, sizeof(arr) / sizeof(arr[0]));
show(arr, sizeof(arr) / sizeof(arr[0]));
return 0;
}
运行结果