【C语言/数据结构】排序(直接插入排序|希尔排序)

简介: 【C语言/数据结构】排序(直接插入排序|希尔排序)

 



插入排序

直接插入排序:

下方是原理图:



//时间复杂度:O(N^2) 逆序
//最好的情况:O(N)  顺序有序
void InsertSort(int* a, int n)
{
  for (int i = 0; i < n - 1; i++)
  {
  int end = i;
  int tmp = a[end + 1];
  while (end >= 0)
  {
    if (tmp < a[end])
    {
    a[end + 1] = a[end];
    end--;
    }
    else
    {
    break;
    }
  }
  a[end + 1] = tmp;
  }
}


分析:此过程为升序。end指向第一个要比较的元素的下标,tmp为待插入元素。当tmp小于前面的元素时,把前一位元素往后移,end--,使其指向前一位(更小的)元素。当tmp不再大于前一位元素,就直接用tmp替换。需注意:for循环的结束条件。


希尔排序


希尔排序有2步:


  1. 预排序(接近有序)(分别对每个分组进行插入排序)
  2. 直接插入排序


预排序


分析:我们假设每组的间隔是3,相同颜色相连的数字是同一组,红色原本是9,6,4,1,进行插入排序后就变成1,4,6,9。其他组别以此类推。这样的目的是使较大的数排后面,小的排前面,让他接近有序。最后再整体进行插入排序,这样可以提高效率。


预排序代码实现如下:


int gap = 3;
  //一组一组排
  //for (int j = 0; j < gap; j++)
  //{
  //  for (int i = j; i < n - gap; i += gap)
  //  {
  //  int end=i;
  //  int tmp = a[end + gap];
  //  while (end >= 0)
  //  {
  //    if (tmp < a[end])
  //    {
  //    a[end + gap] = a[end];
  //    end -= gap;
  //    }
  //    else
  //    {
  //    break;
  //    }
  //  }
  //  a[end + gap] = tmp;
  //  }
  //}
  //多组并排
  for (int i = 0; i < n - gap; i++)
  {
  int end = i;
  int tmp = a[end + gap];
  while (end >= 0)
  {
    if (tmp < a[end])
    {
    a[end + gap] = a[end];
    end -= gap;
    }
    else
    {
    break;
    }
  }
  a[end + gap] = tmp;
  }

分析:预排序有两种写法,第二种写法比第一种少了一层循环。


我们先分析第一种:预排序是在我们前面讲的直接插入排序中修改的。内层for循环中,因为是间隔着排序,所以每次加减时都是加减gap,内层循环结束后,就完成了第一组的排序,外层for循环控制第几组排序。


第二种:少了外层的for循环,i就要从0开始,然后每次加1,这样就是混合着多组进行排序,其他步骤不变。


gap的取值

  • gap越大,大的值更快调到后面,小的值可以更快调到前面,越不接近有序。
  • gap越小,跳的越慢,但是越接近有序,如果gap==1,就是直接插入排序。
//多组并排
int gap = n;
//gap>1时是预排序,目的是让他接近有序
//gap==1是直接插入排序,目的是让他有序
while (gap>1)
{
  //gap=gap/2;
  gap = gap / 3 + 1;
  for (int i = 0; i < n - gap; i++)
  {
  int end = i;
  int tmp = a[end + gap];
  while (end >= 0)
  {
    if (tmp < a[end])
    {
    a[end + gap] = a[end];
    end -= gap;
    }
    else
    {
    break;
    }
  }
  a[end + gap] = tmp;
  }
}

分析:在实际中,gap取值看数量情况定。当gap>1,循环进行预排序,每次/2,最后一次肯定是1。但是每次/2,进行的预排序可能还是过多,就可以/3,不过要保证最后一次是1,因为当2除以3时==0,所以就要在后面加上1。具体除以几,主要保证最后一次是1即可。


时间复杂度


分析:最后一轮累计的挪动次数大约为:n 。总的平均时间复杂度是O(N^1.3),因为计算过程十分复杂,只需了解。


完整代码呈现

//平均O(N^1.3)
void ShellSort(int* a, int n)
{
  //int gap = 3;
  //一组一组排
  //for (int j = 0; j < gap; j++)
  //{
  //  for (int i = j; i < n - gap; i += gap)
  //  {
  //  int end=i;
  //  int tmp = a[end + gap];
  //  while (end >= 0)
  //  {
  //    if (tmp < a[end])
  //    {
  //    a[end + gap] = a[end];
  //    end -= gap;
  //    }
  //    else
  //    {
  //    break;
  //    }
  //  }
  //  a[end + gap] = tmp;
  //  }
  //}
  //多组并排
  int gap = n;
  //gap>1时是预排序,目的是让他接近有序
  //gap==1是直接插入排序,目的是让他有序
  while (gap>1)
  {
  //gap=gap/2;
  gap = gap / 3 + 1;
  for (int i = 0; i < n - gap; i++)
  {
    int end = i;
    int tmp = a[end + gap];
    while (end >= 0)
    {
    if (tmp < a[end])
    {
      a[end + gap] = a[end];
      end -= gap;
    }
    else
    {
      break;
    }
    }
    a[end + gap] = tmp;
  }
  }
}


目录
相关文章
|
存储 机器学习/深度学习 算法
C 408—《数据结构》图、查找、排序专题考点(含解析)
408考研——《数据结构》图,查找和排序专题考点选择题汇总(含解析)。
1840 29
|
搜索推荐 C语言
数据结构(C语言)之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法,通过递归将数组不断分割为子数组,直到每个子数组仅剩一个元素,再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中,每次分割区间为[left, mid]和[mid+1, right],确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值(初始为1),先对单个元素排序,再逐步扩大到更大的区间进行合并,直至整个数组有序。归并排序的时间复杂度为O(n*logn),空间复杂度为O(n),且具有稳定性,适用于普通排序及大文件排序场景。
|
存储 人工智能 算法
【C++数据结构——内排序】二路归并排序(头歌实践教学平台习题)【合集】
本关任务是实现二路归并算法,即将两个有序数组合并为一个有序数组。主要内容包括: - **任务描述**:实现二路归并算法。 - **相关知识**: - 二路归并算法的基本概念。 - 算法步骤:通过比较两个有序数组的元素,依次将较小的元素放入新数组中。 - 代码示例(以 C++ 为例)。 - 时间复杂度为 O(m+n),空间复杂度为 O(m+n)。 - **测试说明**:平台会对你编写的代码进行测试,提供输入和输出示例。 - **通关代码**:提供了完整的 C++ 实现代码。 - **测试结果**:展示代码运行后的排序结果。 开始你的任务吧,祝你成功!
648 10
|
搜索推荐 算法 数据处理
【C++数据结构——内排序】希尔排序(头歌实践教学平台习题)【合集】
本文介绍了希尔排序算法的实现及相关知识。主要内容包括: - **任务描述**:实现希尔排序算法。 - **相关知识**: - 排序算法基础概念,如稳定性。 - 插入排序的基本思想和步骤。 - 间隔序列(增量序列)的概念及其在希尔排序中的应用。 - 算法的时间复杂度和空间复杂度分析。 - 代码实现技巧,如循环嵌套和索引计算。 - **测试说明**:提供了测试输入和输出示例,帮助验证代码正确性。 - **我的通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了代码运行的测试结果。 通过这些内容,读者可以全面了解希尔排序的原理和实现方法。
480 10
|
搜索推荐 C++
【C++数据结构——内排序】快速排序(头歌实践教学平台习题)【合集】
快速排序是一种高效的排序算法,基于分治策略。它的主要思想是通过选择一个基准元素(pivot),将数组划分成两部分。一部分的元素都小于等于基准元素,另一部分的元素都大于等于基准元素。然后对这两部分分别进行排序,最终使整个数组有序。(第一行是元素个数,第二行是待排序的原始关键字数据。本关任务:实现快速排序算法。开始你的任务吧,祝你成功!
566 7
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
2308 9
|
存储 人工智能 算法
数据结构实验之C 语言的函数数组指针结构体知识
本实验旨在复习C语言中的函数、数组、指针、结构体与共用体等核心概念,并通过具体编程任务加深理解。任务包括输出100以内所有素数、逆序排列一维数组、查找二维数组中的鞍点、利用指针输出二维数组元素,以及使用结构体和共用体处理教师与学生信息。每个任务不仅强化了基本语法的应用,还涉及到了算法逻辑的设计与优化。实验结果显示,学生能够有效掌握并运用这些知识完成指定任务。
535 4
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
560 59
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
1399 77
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因,涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问,修改了变量`i`的值,导致`for`循环条件始终为真,形成死循环。原因是VS2022栈区从低地址到高地址分配内存,`arr`数组与`i`相邻,`arr[15]`恰好覆盖`i`的地址。而在VS2019中,栈区先分配高地址再分配低地址,因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致,需避免数组越界以确保代码健壮性。
386 0
栈区的非法访问导致的死循环(x64)