手撕七大排序 (一)

简介: 手撕七大排序 (一)

一. 排序的概念及其运用


1. 排序的概念


所谓排序 就是给你一堆数据 让你按照一个或多个关键字 让这一堆数据递增或者递减


2. 排序的运用


这个就很常见了 就拿我们买东西举例



我们最近想要去买个手机


那么应该怎么选呢?


最多人买的应该没错吧


于是我们想看看 哪个手机买的人最多 这个时候我们只需要点一下按照销量排序 我们就可以拿到我们需要的数据了


3. 常见的排序算法

ac69a1c725d140e9a80681f8fd1ec13d.png


我这里使用xmind整理了一份思维导图给大家


我们这篇博客主要需要学习的是插入排序和选择排序


二. 直接插入排序


1. 基础概念

0414c89006514e41ac0a251b84e08281.png

插入排序其实就像我们拿到一副扑克牌


我们肯定是习惯将整个一副牌按照从小到大的顺序排好是吧


这个就是插入排序在我们现实生活中的运用


2. 代码表示


(我们这里的所有数据以小序为例)


我们这里先假设插入一个数字


首先插入排序我们是默认前面的数据是有序的


所以说我们插入一个元素需要三个数据才可以完成


第一个当然是指向我们数组的指针


第二个是目前数组内元素的个数 我们用这个来确定最后面的元素是哪个


第三个是我们需要插入的值


我们用它来插入


ee418e3acb7940ab845ecf86b8c6967c.png


代码表示如下


// arr表示数组 size是元素的个数 x是插入的值的值 
void Insertsort1(int* arr, int size, int x)
{
  // assert
  assert(arr);
  // 因为插入排序的要
  求是默认前面的有序的
  // 所以说我们这里也默认传入的数组是有序的
  int end = size - 1;
  // x就是我们要插入的值
  while (end >= 0)
  {
    // 比较大小 
    if (arr[end] > x)
    {
      // end往后挪挪 腾位置
      arr[end + 1] = arr[end];
      end--;
    }
    else
    {
      break;
    }
  }
  // 这里画图注意下end的位置 
  arr[end + 1] = x;
}


我们来写一段代码测试下 这个插入排序到底对不对


d4e8979d83a0432298c3071a69ea9317.png

我们可以发现 这段代码没有问题


之后我们开始写整体的数组排序


这个时候我们只需要进行两次循环


(第一次循环将最前面一个元素当成是一个有序数组

第二次循环将最前面两个元素当成是一个有序数组

… … …)

代码表示如下


void Insertsort(int* arr, int size)
{
  // assert
  assert(arr);
  // 我们当这个数组是一个数的有序数组
  // 依次进行插入排序 直到最后
  int end = 0;
  int x = arr[end + 1];
  // 两层循环 一层控制end的大小 一层控制插入排序 这里开始操作
  int i = 0;
  for ( i = 0; i < size-1; i++)
  {
    // 这里赋值end进行迭代
    end = i;
    x = arr[end + 1];
    // 注意这里的边界条件
    while (end>=0)
    {
      // 这里进行进行单个的插入排序
      if (arr[end] > x)
      {
        arr[end + 1] = arr[end];
        end--;
      }
      else
      {
        break;
      }
    }
    // 还是一样 画图注意end这个时候在哪里 数组是一个什么样子的
    arr[end + 1] = x;
  }
}


我们来看看最后结果是什么样子的


2f1eea4330b84ca0832e79ffb183c63a.png

可以完美运行


三. 希尔排序(shellsort)


1. 基础概念

71cf1a6b9a2c43d280e52df4402e1d4d.png


在了解希尔排序之前我们先了解下直接插入排序的时间复杂度


在完全有序时 直接插入排序的时间复杂度最高 此时为 O(N^2)


在完全有序时 直接插入排序的时间复杂度最低 此时为 O(N)


所以说 只要让我们要排序的数字尽量有序 就能很大程度上降低时间复杂度


我们将这一步称为 预排序


2. 预排序


65fe1d5ddcad416099af259e8eefe977.png


这里我们要引入一个 gap变量 我们将之称为间隔


从零起始位置开始 我们利用它们之间的间隔作为依据


建立N个不同的数组


并且这个时候我们将这个数组进行插入排序


之后我们不断缩小间隔 继续进行预排序


最后当gap等于1的时候再进行一次插入排序


3. 希尔排序代码


void Shellsort(int* arr, int size)
{
  // assert
  assert(arr);
  // set gap
  int gap = size;
  // 这个时候我们就要利用到间隔 来进行快排 
  // 当gap=1的时候就进行插入排序了
  while (gap > 1)
  {
    // 这个时候我们开始进行预排序
    gap = gap / 2;
    int end = 0;
    int x = arr[end + gap];
    // gap = gap / 3 + 1;   这样子也可以
    int i = 0;
    for ( i = 0; i < size-gap; i++)
    {
      end = i;
      x = arr[end + gap];
      while (end>=0)
      {
        if (arr[end] > x)
        {
          arr[end + gap] = arr[end];
          end -= gap;
        }
        else
        {
          break;
        }
      }
      // 注意end位置
      arr[end + gap] = x;
    }
  }
}


整体代码表示如上


以上就是本篇博客的全部内容啦 由于博主才疏学浅 所以难免会出现纰漏 希望大佬们看到错误之后能够


不吝赐教 在评论区或者私信指正 博主一定及时修正


那么大家下期再见咯





相关文章
|
3月前
|
算法
【❤️算法笔记❤️】-每日一刷-23、合并 K 个升序链表
【❤️算法笔记❤️】-每日一刷-23、合并 K 个升序链表
36 0
|
7月前
|
人工智能 算法 搜索推荐
蓝桥杯宝藏排序题目算法(冒泡、选择、插入)
以下是内容的摘要: 本文介绍了三种排序算法:冒泡排序、选择排序和插入排序。冒泡排序通过不断交换相邻的逆序元素逐步排序,最坏情况下需要 O(n^2) 次比较。选择排序在每轮中找到剩余部分的最小元素并放到已排序序列的末尾,同样具有 O(n^2) 时间复杂度。插入排序则是将每个元素插入到已排序序列的正确位置,时间复杂度也是 O(n^2),但空间复杂度为 O(1)。
|
8月前
|
算法 前端开发 索引
2624. 蜗牛排序
2624. 蜗牛排序
48 0
|
搜索推荐
[数据结构 -- 手撕排序第一篇] 插入排序
[数据结构 -- 手撕排序第一篇] 插入排序
|
存储 自然语言处理 索引
|
搜索推荐 算法
【排序算法 上】带你手撕常见排序 (插入,希尔,选择,堆排序) (动图详解)
【排序算法 上】带你手撕常见排序 (插入,希尔,选择,堆排序) (动图详解)
118 0
【排序算法 上】带你手撕常见排序 (插入,希尔,选择,堆排序) (动图详解)
|
搜索推荐 算法 C语言
【排序算法 下】带你手撕常见排序 (冒泡,快排,归并排序) (动图详解)
【排序算法 下】带你手撕常见排序 (冒泡,快排,归并排序) (动图详解)
171 0
【排序算法 下】带你手撕常见排序 (冒泡,快排,归并排序) (动图详解)
|
算法
手撕七大排序 (三)
手撕七大排序 (三)
95 0
手撕七大排序 (三)
|
算法 搜索推荐
手撕七大排序 (四)
手撕七大排序 (四)
86 0
手撕七大排序 (四)