【数据结构】直接插入排序 & 希尔排序(一)

简介: 【数据结构】直接插入排序 & 希尔排序(一)

一,排序的概念

排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作;

稳定性:假定在待排序的记录序列中,存在多个具有同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。

内部排序:数据元素全部放在内存中的排序。

外部排序:数据元素太多不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序。

二,直接插入排序

1,基本思想

直接插入排序是一种简单的插入排序法,其基本思想是:

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 ;

实际中我们玩扑克牌时,就用了插入排序的思想

2,基本思路

当插入第i(i>=1)个元素时,前面的 array[0],array[1],…,array[i-1] 已经排好序,此时用array[i]的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较,找到插入位置即将array[i]插入,原来位置上的元素顺序后移;

直接插入排序的特性总结:

1, 元素集合越接近有序,直接插入排序算法的时间效率越高

2.,时间复杂度:O(N^2)

3, 空间复杂度:O(1),它是一种稳定的排序算法

4, 稳定性:稳定

3,思路实现

刚开始数组前一个数 arr [ 0 ] 是有序的然后让二个数 arr [ 1 ] 当做插入数使得前两个数有序

然后再让第三个数 arr [ 2 ] 当做插入数使得前三个数有序

以此类推直至数组全部有序

我们现在写一个升序的直接插入排序

//交换
void Swap(int* a, int* b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}
//插入排序
void InsertSort(int* arr, int n)
{
  int i = 0;
  for (i = 0; i < n-1; i++)
  {
    int end = i;
    int tmp = arr[end + 1];
    while (end >= 0)
    {
      if (arr[end] >= tmp)
      {
        //交换
        Swap(&arr[end], &arr[end+1]);
        end--;
      }
      else
      {
        break;
      }
    }
    arr[end + 1] = tmp;
  }
}

我们测试一下;

//打印
void PrintSort(int* arr, int n)
{
  int i = 0;
  for (i = 0; i < n; i++)
  {
    printf("%d ", arr[i]);
  }
}
int main()
{
  int arr[] = { 9,1,2,5,7,4,8,6,3,5 };
  //插入排序
  InsertSort(arr, sizeof(arr) / sizeof(arr[0]));
  PrintSort(arr, sizeof(arr) / sizeof(arr[0]));
  return 0;
}

可以看到是有序的,直接插入排序就 OK 了;

三,希尔排序

希尔排序法又称缩小增量法

希尔排序法的基本思想是:先选定一整数,把待排序文件中所有记录分成 gap 组,所有距离为的 gap 的数组分在同一组,并对每一组内的数据进行排序。然后重复上述分组和排序的工作。当 gap=1时,所有数组在统一组内排好序;

图示:

1,希尔排序的特性总结

1, 希尔排序是对直接插入排序的优化;

2, 当 gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就会很快。这样整体而言,可以达到优化的效果;

3, 希尔排序的时间复杂度不好计算,因为 gap 的取值方法很多,导致很难去计算,因此在好些数据中给出的希尔排序的时间复杂度都不固定

因为我们的 gap 是按照 Knuth 提出的方式取值的,而且 Knuth 进行了大量的试验统计,我们暂时就按照:O(n^1.25) 到O(1,6*n^1.25) 来算,其实平均也就是 O(n*1.3)

4.,稳定性:不稳定

2,思路实现:

我们先让 gap 的值取总数据的一半也就是 n/2 ,然后每下次循环都缩减一半直至 gap=1 ,出循环程序结束;

//希尔排序
void HillSort(int* arr, int n)
{
  int gap = n;
  int i = 0;
  while (gap > 1)
  {
    gap = gap / 2;
    for (i = 0; i < n-gap; i++)
    {
      int end = i;
      int tmp = arr[end + gap];
      while (end >= 0)
      {
        if (arr[end] >= tmp)
        {
          //交换
          Swap(&arr[end], &arr[end + gap]);
          end -= gap;
        }
        else
        {
          break;
        }
      }
      arr[end + gap] = tmp;
    }
  }
}

还是上面那组数据:

这就 OK 了,其实就是换汤不换药,学会了直接插入排序,希尔排序直接秒杀!

第一阶段就到这里了,带大家秒杀秒杀两个排序热热身;

后面博主会陆续更新;

如有不足之处欢迎来补充交流!

完结。。

目录
相关文章
|
2月前
|
搜索推荐 算法 数据处理
【C++数据结构——内排序】希尔排序(头歌实践教学平台习题)【合集】
本文介绍了希尔排序算法的实现及相关知识。主要内容包括: - **任务描述**:实现希尔排序算法。 - **相关知识**: - 排序算法基础概念,如稳定性。 - 插入排序的基本思想和步骤。 - 间隔序列(增量序列)的概念及其在希尔排序中的应用。 - 算法的时间复杂度和空间复杂度分析。 - 代码实现技巧,如循环嵌套和索引计算。 - **测试说明**:提供了测试输入和输出示例,帮助验证代码正确性。 - **我的通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了代码运行的测试结果。 通过这些内容,读者可以全面了解希尔排序的原理和实现方法。
62 10
|
9月前
|
算法 搜索推荐
数据结构算法--6 希尔排序和计数排序
**希尔排序**是插入排序的改进版,通过分组插入来提高效率。它逐步减少元素间的间隔(增量序列),每次对每个间隔内的元素进行插入排序,最终增量为1时进行最后一次直接插入排序,实现整体接近有序到完全有序的过程。例如,对数组`5, 7, 4, 6, 3, 1, 2, 9, 8`,先以间隔`d=4`排序,然后`d=2`,最后`d=1`,完成排序。计数排序则适用于0到100的数值,通过统计每个数出现次数,创建对应计数数组,再根据计数重建有序数组,时间复杂度为`O(n)`。
|
5月前
|
算法 搜索推荐 Shell
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
89 1
|
5月前
|
算法 搜索推荐
数据结构与算法学习十一:冒泡排序、选择排序、插入排序
本文介绍了冒泡排序、选择排序和插入排序三种基础排序算法的原理、实现代码和测试结果。
44 0
数据结构与算法学习十一:冒泡排序、选择排序、插入排序
|
8月前
|
搜索推荐 测试技术
【数据结构常见七大排序(一)】—插入排序篇【直接插入排序】And【希尔排序】
【数据结构常见七大排序(一)】—插入排序篇【直接插入排序】And【希尔排序】
|
9月前
|
机器学习/深度学习 算法 搜索推荐
数据结构算法--2 冒泡排序,选择排序,插入排序
**基础排序算法包括冒泡排序、选择排序和插入排序。冒泡排序通过相邻元素比较交换,逐步将最大值“冒”到末尾,平均时间复杂度为O(n^2)。选择排序每次找到剩余部分的最小值与未排序部分的第一个元素交换,同样具有O(n^2)的时间复杂度。插入排序则类似玩牌,将新元素插入到已排序部分的正确位置,也是O(n^2)复杂度。这些算法适用于小规模或部分有序的数据。**
|
9月前
|
算法 搜索推荐
数据结构与算法-插入排序
数据结构与算法-插入排序
43 2
|
9月前
|
算法 Shell C语言
数据结构与算法——希尔排序(引例、希尔增量序列、原始希尔排序、代码、时间复杂度、Hibbard增量序列、Sedgewick增量序列)
数据结构与算法——希尔排序(引例、希尔增量序列、原始希尔排序、代码、时间复杂度、Hibbard增量序列、Sedgewick增量序列)
116 0
|
9月前
|
人工智能 算法 C语言
数据结构与算法——简单排序-冒泡排序、插入排序,时间复杂度下界(图示、代码、时间复杂度、定理)
数据结构与算法——简单排序-冒泡排序、插入排序,时间复杂度下界(图示、代码、时间复杂度、定理)
63 0
|
4月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
64 1