7大排序算法-- 直接插入,希尔,冒泡,选择 --精解(下)

简介: 7大排序算法-- 直接插入,希尔,冒泡,选择 --精解(下)

希尔排序:

希尔排序 其实就是一个对我们上面的直接插入排序的一个优化

① 使用预排序

② 在使用直接插入排序


首先我们上面不是说了直接插入排序比较适应那些 局部有序 和 接近有序 的数组嘛 所以如果说现在给我们一个数组 它并不满足刚刚的两种情况 那我们是不是可以使用一个预排序 是这个数组里的接近我们的这两种情况  这个时候再使用我们的直接插入排序是不是会更好一点呢?


希尔排序--预排序:

我们与排序的思想就是 把大的数更快的到后面去  把小的数更快的到前面去

思想知道了 那我们该怎么去实现它呢?

首先实现预排序 我们要把我们的数据分成一个一个的组(gap) 假设gap=3  (也就是三个间隙为一组)


f04699086a6a46ad9b0515201a81eace.gif

 大家看到我们此时的分组了 其实我们分组的目的就是为了把数据分成几个组 就好像这里我们是 9 5 6 8 一组 1 8 7一组 3 2 4一组 我们对着三组数据分别进行插入排序的操作


020fa3ec9b7f411ab18e1ed49a84a625.gif

如图所示 就是每一组进行一个插入排序的操作 让小往前移动 让大的往后移动 其他组也是一样的道理: 

6c4a1af91308446a9da6d52cfc5bf388.gif

还有一组我就不演示了 相信大家应该明白其中的道理了吧

那现在大家想想 我们既然这里gap设置的是3 那如果是其他的值呢 我们的预排序又会有怎样的效果呢?

实际上很显然 当我们的gap越小越接近有序  gap越大 大的数据 可以更快到后面,小的数可以更快到到前面 但他越不接近有序

         int gap=3;
         for(int i=0;i<gap;i++)
         {
           for(int j=i;j<n-gap;j+=gap)
           {
            int end = j;
      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循环是为了遍历每一组  我们的边界之所以设成 n-gap:


fe5723d95ac946fc959bf54433b7cbb5.png


遍历到 n-gap-1 就可以了 就不用再往后遍历

当然我们还可以这样写 外面的遍历:

        int gap=3;
        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 现在又是什么情况呢?

其实很简单 我们gap=1不就是间隙为1是同一的组嘛 那这样是不是每个数都是一个组里面的这个时候在实现for循环里面的操作不就是 一个插入排序了嘛?

  我们 的希尔排序分为预排序和直接插入排序  我们 gap不同  也就对应前面的两种顺序 那我们是不似乎可以把gap改成不是固定的值内?  

void ShellSort(int* a, int n)//希尔排序 gap不为1 预排序 gap为1 插入排序
{
  int gap = n;
  while (gap > 1)
  {
    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的变化并没有固定的标准 只是有些书上是这样建议的 写成其他的也行  我们+1是必须的 因为这样才能保证必定gap会有一次等于 1


希尔排序的时间复杂度:

预排序:

gap很大的时候 数据会跳的很快 差不多是O(N)

我们其实gap很大的时候 我们数据跳的也就越快 假设 gap=n/3 那是不是我们的数据只要跳三次就可以到应该的位置上了呢 那我们此时for循环里面的操作是不是可以忽略不记了呢 以后的数不也是一样的道理嘛 这就是为什么是O(N)了


gap很小的时候 我们的数据 已经很接近有序了 这个时候排的话 只有很少的数才会去交换 那我们的时间复杂度是不是也可以约估成O(N)了呢?


我们外面的while循环又要进行多少次呢?

咋们每次 ÷3+1 ÷3+1 其实+1就可以忽略掉了

是不是就是这样内  n/3/3/3/3/.../3/3=1;

假设 ÷ 了x次 那么 x=log3n


总结:如果按照这种算法 咋们的希尔排序的时间复杂度就是O(N*log3N) (实际上呢 一本严蔚敏老师的书上 提到的是 按照计算 他的出来希尔排序的比较和移动次数约为n^1.3) 稳定性:不稳定


选择排序:

选择排序其实挺简单的:

image.gif

我们遍历这个数组选出最小的放到前面 每次遍历的第一个位置都会跟着选出数据的次数更新

我们选出第一个最小的数据了 那么就把它与第一个数据交换 继续遍历数组但不包括第一个位置 此时选出来的数据就要与第二个位置的数据交换了  大家看能明白嘛?


我这里写的呢 跟一般教材上面的不太一样  我这里写得是同时选两个数 也就是一个最大一个最小 但是呢思路都是一样的

void SelectSort(int* a, int n)
{
  int maxi, mini, right, left;
  left = 0;
  right = n - 1;
  while (left < right)
  {
    maxi = mini = left;
    for (int i = left; i < right + 1; i++)
    {
      if (a[mini] > a[i]) mini = i;
      if (a[maxi] < a[i]) maxi = i;
    }
    swap(a + mini, a + left);
    swap(a + maxi, a + right);
    left++;
    right--;
  }
}

 这样我们的代买就写完了  不知道大家对照着这个数组看有没有发现上面是否存在问题呢?


dfc3519929eb4969bbd30d92ceaee715.png这个问题挺难发现的 我们第一次选 maxi=0 mini=1 我们首先mini与left 交换 可是我们 此时maxi上的位置还是我们的9嘛 刚刚的交换不是就把 9 换到mini的位置上了嘛 所以应该是这样的:

void SelectSort(int* a, int n)
{
  int maxi, mini, right, left;
  left = 0;
  right = n - 1;
  while (left < right)
  {
    maxi = mini = left;
    for (int i = left; i < right + 1; i++)
    {
      if (a[mini] > a[i]) mini = i;
      if (a[maxi] < a[i]) maxi = i;
    }
    swap(a + mini, a + left);
    if(maxi==left) maxi=mini;  
    swap(a + maxi, a + right);
    left++;
    right--;
  }
}

所以正确的代码应该是这样的 因为我们既然我们的maxi变了 就把他修正一下不就行了嘛 left与mini交换了 maxi=left 那么此时正确的max的值不就应该在mini的位置了嘛

传统的选择排序的时间复杂度:O(N^2) 稳定性:不稳定

目录
相关文章
|
1月前
|
数据可视化 搜索推荐 Python
Leecode 刷题笔记之可视化六大排序算法:冒泡、快速、归并、插入、选择、桶排序
这篇文章是关于LeetCode刷题笔记,主要介绍了六大排序算法(冒泡、快速、归并、插入、选择、桶排序)的Python实现及其可视化过程。
14 0
|
1月前
|
搜索推荐 算法
排序算法---冒泡&选择&插入总结
排序算法---冒泡&选择&插入总结
16 0
|
3月前
|
搜索推荐 算法
十大排序算法-快排-希尔-堆排-归并-冒泡-桶排-选择-插入-计数-基数
十大排序算法-快排-希尔-堆排-归并-冒泡-桶排-选择-插入-计数-基数
十大排序算法-快排-希尔-堆排-归并-冒泡-桶排-选择-插入-计数-基数
|
3月前
|
数据采集 搜索推荐 算法
【高手进阶】Java排序算法:从零到精通——揭秘冒泡、快速、归并排序的原理与实战应用,让你的代码效率飙升!
【8月更文挑战第21天】Java排序算法是编程基础的重要部分,在算法设计与分析及实际开发中不可或缺。本文介绍内部排序算法,包括简单的冒泡排序及其逐步优化至高效的快速排序和稳定的归并排序,并提供了每种算法的Java实现示例。此外,还探讨了排序算法在电子商务、搜索引擎和数据分析等领域的广泛应用,帮助读者更好地理解和应用这些算法。
42 0
|
5月前
|
搜索推荐 算法
【排序】数据结构——排序算法概念及代码详解(插入、冒泡、快速、希尔)
【排序】数据结构——排序算法概念及代码详解(插入、冒泡、快速、希尔)
|
5月前
|
人工智能 算法 搜索推荐
蓝桥杯宝藏排序题目算法(冒泡、选择、插入)
以下是内容的摘要: 本文介绍了三种排序算法:冒泡排序、选择排序和插入排序。冒泡排序通过不断交换相邻的逆序元素逐步排序,最坏情况下需要 O(n^2) 次比较。选择排序在每轮中找到剩余部分的最小元素并放到已排序序列的末尾,同样具有 O(n^2) 时间复杂度。插入排序则是将每个元素插入到已排序序列的正确位置,时间复杂度也是 O(n^2),但空间复杂度为 O(1)。
|
6月前
|
算法 搜索推荐 Java
Java数据结构 -- 常见算法分析(查找算法、排序算法)精解详解!!!
Java数据结构 -- 常见算法分析(查找算法、排序算法)精解详解!!!
61 0
|
6月前
|
存储 算法 搜索推荐
【算法】七大经典排序(插入,选择,冒泡,希尔,堆,快速,归并)(含可视化算法动图,清晰易懂,零基础入门)
【算法】七大经典排序(插入,选择,冒泡,希尔,堆,快速,归并)(含可视化算法动图,清晰易懂,零基础入门)
185 1
|
6月前
|
搜索推荐
图解基础排序算法(冒泡、插入、选择)(山东大学实验二)
图解基础排序算法(冒泡、插入、选择)(山东大学实验二)
|
28天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
下一篇
无影云桌面