当前位置：首页 > news >正文

八大排序——直接插入排序/希尔排序

news 2025/4/29 5:56:13

八大排序——直接插入排序/希尔排序

一、直接插入排序

二、希尔排序

一、直接插入排序

每一趟从待排序序列中取第一个值，将其插入到已排序好的序列中，对已排序好的序列，从右到左依次和待插入值比较，如果大于则向后挪，如果发现一个小于等于插入值的值，或者触底，则插入到其后

len个数据，需要len-1趟

void Insert_Sort(int arr[], int len)
{for (int i = 1; i < len; i++){int tmp = arr[i];//i下标的值就是我们这一趟准备插入的值int j;for (j=i-1;j>=0;j--)//j下标保存已排序序列的最右端值下标，逐步向左走{if (arr[j] > tmp)//arr[j]是要比较的值{arr[j + 1] = arr[j];}else{break;//找到了小于等于我准备插入的值tmp,那么当前位置的下一个位置就是我要插入的位置}}//触底了，已排序好的所有值都比tmp大arr[j + 1] = tmp;}
}

//主函数测试
int main()
{int arr[] = { 3,2,5,1,4,9,7,11,6 };int len = sizeof(arr) / sizeof(arr[0]);Insert_Sort(arr, len);for (int i = 0; i < len; i++){printf("%d ", arr[i]);}printf("\n");return 0;
}

外层循环：

插入排序默认第一个元素是已排序的，所以从第二个元素（下标为 1）开始处理。
i 从 1 递增到 len - 1，每一次循环处理一个元素，控制排序的趟数。

内层循环：

j 初始化为 i - 1，也就是已排序序列的最后一个元素的下标。
j 逐步递减，从右向左遍历已排序序列。
如果 arr[j] 大于 tmp，就把 arr[j] 向后移动一位，即 arr[j + 1] = arr[j]。
若 arr[j] 小于等于 tmp，就意味着找到了 tmp 应该插入的位置，此时使用 break 跳出内层循环。

二、希尔排序

缩小增量排序，希尔排序是对直接插入排序的优化

//时间复杂度O(n^1.3 ~ n^1.7) 空间复杂度O(1) 稳定性：不稳定
void Shell(int arr[], int len, int gap)
{for (int i = gap; i < len; i++)//从第gap个元素开始遍历{int tmp = arr[i];//i下标的值就是我们这一趟当前准备插入的值int j;//for (j = i - gap; j >= 0; j-=gap)//j下标一开始保存已排序好的序列最右端值的下标，逐步向左走{if (arr[j] > tmp){arr[j + gap] = arr[j];}else{break;//插入情况1：找到了一个小于等于我准备插入的值}}//如果代码执行到这里，代表着触底了，插入情况1：已排序好的序列中的所以值都比我tmp的大arr[j + gap] = tmp;}}void Shell_Sort(int arr[], int len)
{//增量数组int gap[] = { 5,3,1 };for (int i = 0; i < sizeof(gap) / sizeof(gap[0]); i++){Shell(arr, len, gap[i]);//每一趟单独执行希尔排序(需要告诉我们这一趟按哪个增量处理)}
}

外层 for 循环：从数组的第 gap 个元素开始遍历，i 表示当前要插入的元素的下标。
保存待插入元素：将 arr[i] 的值保存到 tmp 中，以便后续找到合适位置插入。
内层 for 循环：从 i - gap 开始，以 gap 为步长向左遍历已排序的部分。j 表示当前比较的元素的下标。
比较和移动元素：如果 arr[j] 大于 tmp，则将 arr[j] 向右移动 gap 个位置（arr[j + gap] = arr[j];）。
找到插入位置：如果 arr[j] 小于等于 tmp，则说明找到了 tmp 的合适插入位置，跳出内层循环。
插入元素：将 tmp 插入到 arr[j + gap] 的位置，完成这一趟插入操作。