当当网的网站怎么做的,网站怎么做跳转页面,福州网站开发培训,英文公司网站制作希尔排序是插入排序的进阶版本#xff0c;他多次调用插入排序#xff0c;在插入排序上进行了改造#xff0c;使其处理无序的数据时候更快
核心思想#xff1a;1.分组 2.直接插入排序#xff1a;越有序越快
算法思想#xff1a;
间隔式分组#xff0c;利用直接插入排序…希尔排序是插入排序的进阶版本他多次调用插入排序在插入排序上进行了改造使其处理无序的数据时候更快
核心思想1.分组 2.直接插入排序越有序越快
算法思想
间隔式分组利用直接插入排序让组内有序然后缩小分组再次排序直到组数为1,理论基础为直接插入排序
高明之处 我们正常分组时候是这样直接挨着分组每3个3个分组这样导致我们分组之后小的数字变化不大大的数字变化也不大而我们希望小的数字在前面大的数字在后面这样可以减少我们的时间复杂度 而我们通过这样的间隔式分组可以实现尽量让大数据在后面肖书记在前面通过5 3 1的三次分组注最后一次必须是1的分组因为我们要让所有数据有序实现比插入排序时间复杂度低的排序
代码实现:
//一趟希尔排序
static void Shell(int* arr, int len,int gap)//gap为组数或者(间隔)
{int tmp, i, j;for (i gap; i len; igap){tmp arr[i];for (j i - gap; j 0; j-gap){if (arr[j] tmp){arr[j gap] arr[j];}elsebreak;}arr[j gap] tmp;}
}void ShellSort(int* arr, int len)
{int drr[] { 5,3,1 };for (int i 0; i sizeof(drr) / sizeof(drr[0]); i){Shell(arr, len, drr[i]);}
}特点
希尔排序时间复杂度O(n^1.3~n^1.5),空间复杂度O1不稳定
