【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;
  }
  }
}


秦jh
+关注
目录
打赏
0
4
4
1
80
分享
相关文章
C 408—《数据结构》图、查找、排序专题考点(含解析)
408考研——《数据结构》图,查找和排序专题考点选择题汇总(含解析)。
186 29
数据结构(C语言)之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法,通过递归将数组不断分割为子数组,直到每个子数组仅剩一个元素,再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中,每次分割区间为[left, mid]和[mid+1, right],确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值(初始为1),先对单个元素排序,再逐步扩大到更大的区间进行合并,直至整个数组有序。归并排序的时间复杂度为O(n*logn),空间复杂度为O(n),且具有稳定性,适用于普通排序及大文件排序场景。
【C++数据结构——内排序】二路归并排序(头歌实践教学平台习题)【合集】
本关任务是实现二路归并算法,即将两个有序数组合并为一个有序数组。主要内容包括: - **任务描述**:实现二路归并算法。 - **相关知识**: - 二路归并算法的基本概念。 - 算法步骤:通过比较两个有序数组的元素,依次将较小的元素放入新数组中。 - 代码示例(以 C++ 为例)。 - 时间复杂度为 O(m+n),空间复杂度为 O(m+n)。 - **测试说明**:平台会对你编写的代码进行测试,提供输入和输出示例。 - **通关代码**:提供了完整的 C++ 实现代码。 - **测试结果**:展示代码运行后的排序结果。 开始你的任务吧,祝你成功!
176 10
【C++数据结构——内排序】希尔排序(头歌实践教学平台习题)【合集】
本文介绍了希尔排序算法的实现及相关知识。主要内容包括: - **任务描述**:实现希尔排序算法。 - **相关知识**: - 排序算法基础概念,如稳定性。 - 插入排序的基本思想和步骤。 - 间隔序列(增量序列)的概念及其在希尔排序中的应用。 - 算法的时间复杂度和空间复杂度分析。 - 代码实现技巧,如循环嵌套和索引计算。 - **测试说明**:提供了测试输入和输出示例,帮助验证代码正确性。 - **我的通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了代码运行的测试结果。 通过这些内容,读者可以全面了解希尔排序的原理和实现方法。
124 10
|
6月前
|
【C++数据结构——内排序】快速排序(头歌实践教学平台习题)【合集】
快速排序是一种高效的排序算法,基于分治策略。它的主要思想是通过选择一个基准元素(pivot),将数组划分成两部分。一部分的元素都小于等于基准元素,另一部分的元素都大于等于基准元素。然后对这两部分分别进行排序,最终使整个数组有序。(第一行是元素个数,第二行是待排序的原始关键字数据。本关任务:实现快速排序算法。开始你的任务吧,祝你成功!
160 7
【C语言程序设计——选择结构程序设计】按从小到大排序三个数(头歌实践教学平台习题)【合集】
本任务要求从键盘输入三个数,并按从小到大的顺序排序后输出。主要内容包括: - **任务描述**:实现三个数的排序并输出。 - **编程要求**:根据提示在编辑器中补充代码。 - **相关知识**: - 选择结构(if、if-else、switch) - 主要语句类型(条件语句) - 比较操作与交换操作 - **测试说明**:提供两组测试数据及预期输出。 - **通关代码**:完整代码示例。 - **测试结果**:展示测试通过的结果。 通过本任务,你将掌握基本的选择结构和排序算法的应用。祝你成功!
91 4
数据结构实验之C 语言的函数数组指针结构体知识
本实验旨在复习C语言中的函数、数组、指针、结构体与共用体等核心概念,并通过具体编程任务加深理解。任务包括输出100以内所有素数、逆序排列一维数组、查找二维数组中的鞍点、利用指针输出二维数组元素,以及使用结构体和共用体处理教师与学生信息。每个任务不仅强化了基本语法的应用,还涉及到了算法逻辑的设计与优化。实验结果显示,学生能够有效掌握并运用这些知识完成指定任务。
177 4
【排序算法】八大排序(下)(c语言实现)(附源码)
本文继续学习并实现了八大排序算法中的后四种:堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现,并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序,快速排序通过递归和多种划分方法实现高效排序,归并排序通过分治法将问题分解后再合并,计数排序则通过统计每个元素的出现次数实现非比较排序。最后,文章还对比了这些排序算法在处理一百万个整形数据时的运行时间,帮助读者了解不同算法的优劣。
293 7
【排序算法】八大排序(上)(c语言实现)(附源码)
本文介绍了四种常见的排序算法:冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据,详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序,选择排序通过选择最小元素进行交换,插入排序通过逐步插入元素到已排序部分,而希尔排序则是插入排序的改进版,通过预排序使数据更接近有序,从而提高效率。文章最后总结了这四种算法的空间和时间复杂度,以及它们的稳定性。
294 8
|
8月前
|
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
183 58
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等