数据结构插入排序

简介: 数据结构插入排序

95a05b3da6094989826a6532a705ab11.gif

好久不见,这几天有点事情,都快一个礼拜没有学习,对键盘都要陌生起来了,今天也是刚刚学了一点排序,在这里也给大家更新一个插入排序,后面也会渐渐的把八大排序更新完的,还有就是二叉树,二叉树小编能力有限,可能也是学了一点点,废话不多说,我们进入今天的学习吧。

插入排序和我们之前学过的冒泡排序有一点相似之处,首先他们的空间复杂度都是O(N*N),插入排序的整个过程是怎么样的呢,首先我们先引入一个小问题,那就是我们将一个数插入到一个升序的有序列数组当中,我们是怎样插入的,首先我们应该拿这个数去进行比较,从末尾开始比,如果比这个数大我们就要继续往前找,一直到找到大于或者等于这个数的时候,我们在这个数的末尾进行插入,在插入过程中,如果这个数比其他数要小的时候,其他数应该要往后移动,相当于是一个覆盖的思路,我们这里给一个图,让大家比较好理解。

我们end一直往前面走,一直到找到合适的位置才停止,中间还有一个过程是覆盖,画图里没有体现出来,就是不满足条件就往后移动覆盖,我们用代码看看可能更好来理解。

int end = 9;
    int tmp = a[end + 1];
    while (end >= 0)
    {
      if (tmp < a[end])
      {
        a[end + 1] = a[end];
        end--;
      }
      else
      {
        break;
      }
    }
    a[end+1] = tmp;
  }

假设我们有九个数,现在就是要把1放入这个数组当中我们改怎么做呢,上面的代码就可以体现出来,那么我们有这个思路之后,我们是不是可以模拟到插入排序当中,其实很简单只要在我外面套一个循环就能实现了,那我们来试一试吧

void InsertSort(int* a, int n)
{
  int i = 0;
  for (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;
  }
}

这个样子就能把我们的插入排序实现了,我们也可以测试一下
头文件

InsertSort.h

#include<stdio.h>
void InsertSort(int* a, int n);
void PrintInsert(int* a, int n);

InsertSort.c

#include"Insert.h"
void InsertSort(int* a, int n)
{
  int i = 0;
  for (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;
  }
}
void PrintInsert(int* a, int n)
{
  int i = 0;
  for (i = 0; i < n; i++)
  {
    printf("%d ", a[i]);
  }
  printf("\n");
}

Test.c

int main()
{
  int arr[] = { 9,8,7,6,5,4,3,2,1 };
  InsertSort(arr, sizeof(arr) / sizeof(int));
  PrintInsert(arr, sizeof(arr) / sizeof(int));
  return 0;
}

调试之后就能把它变成有序的了,今天我们就讲一个排序,因为小编偷懒,今天只学了一个排序哈哈哈哈

我们下次再见

相关文章
|
2月前
|
算法 搜索推荐
数据结构与算法学习十一:冒泡排序、选择排序、插入排序
本文介绍了冒泡排序、选择排序和插入排序三种基础排序算法的原理、实现代码和测试结果。
24 0
数据结构与算法学习十一:冒泡排序、选择排序、插入排序
|
5月前
|
搜索推荐 测试技术
【数据结构常见七大排序(一)】—插入排序篇【直接插入排序】And【希尔排序】
【数据结构常见七大排序(一)】—插入排序篇【直接插入排序】And【希尔排序】
|
6月前
|
机器学习/深度学习 算法 搜索推荐
数据结构算法--2 冒泡排序,选择排序,插入排序
**基础排序算法包括冒泡排序、选择排序和插入排序。冒泡排序通过相邻元素比较交换,逐步将最大值“冒”到末尾,平均时间复杂度为O(n^2)。选择排序每次找到剩余部分的最小值与未排序部分的第一个元素交换,同样具有O(n^2)的时间复杂度。插入排序则类似玩牌,将新元素插入到已排序部分的正确位置,也是O(n^2)复杂度。这些算法适用于小规模或部分有序的数据。**
|
6月前
|
算法 搜索推荐
数据结构与算法-插入排序
数据结构与算法-插入排序
35 2
|
7月前
|
存储 搜索推荐 算法
[数据结构]————排序总结——插入排序(直接排序和希尔排序)—选择排序(选择排序和堆排序)-交换排序(冒泡排序和快速排序)—归并排序(归并排序)
[数据结构]————排序总结——插入排序(直接排序和希尔排序)—选择排序(选择排序和堆排序)-交换排序(冒泡排序和快速排序)—归并排序(归并排序)
|
7月前
|
C语言
【C语言/数据结构】排序(直接插入排序|希尔排序)
【C语言/数据结构】排序(直接插入排序|希尔排序)
55 4
|
7月前
|
搜索推荐 算法 C++
[数据结构]-玩转八大排序(一)&&插入排序&&选择排序
[数据结构]-玩转八大排序(一)&&插入排序&&选择排序
|
6月前
|
人工智能 算法 C语言
数据结构与算法——简单排序-冒泡排序、插入排序,时间复杂度下界(图示、代码、时间复杂度、定理)
数据结构与算法——简单排序-冒泡排序、插入排序,时间复杂度下界(图示、代码、时间复杂度、定理)
44 0
|
6月前
|
存储 搜索推荐
深入了解数据结构第四弹——排序(1)——插入排序和希尔排序
深入了解数据结构第四弹——排序(1)——插入排序和希尔排序
31 0
|
7月前
|
存储 算法 搜索推荐
【数据结构与算法】:插入排序与希尔排序
欢迎大家来到初阶数据结构的最后一小节:排序
【数据结构与算法】:插入排序与希尔排序