八大排序——直接插入排序/希尔排序
目录
一、直接插入排序
每一趟从待排序序列中取第一个值，将其插入到已排序好的序列中，对已排序好的序列，从右到左依次和待插入值比较，如果大于则向后挪，如果发现一个小于等于插入值的值，或者触底，则插入到其后
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]的位置，完成这一趟插入操作。
