带你学懂数据结构中的八大排序(上)
创始人
2024-05-01 14:00:21
0

✨个人主页: Yohifo
🎉所属专栏: 数据结构 | C语言
🎊每篇一句: 图片来源

  • Every challenge, every adversity, contains within it the seeds of opportunity and growth.
    • 每个挑战,每次逆境,里面都藏有机会与成长的种子。

道阻且长,行则将至


文章目录

  • 📘前言
  • 📘正文
    • 📖插入排序
      • 📃直接插入排序
      • 📃希尔排序
    • 📖选择排序
      • 📃简单选择排序
      • 📃堆排序
    • 📖排序小结
  • 📘总结


📘前言

排序(Sort)是初阶数据结构中的最后一块内容,所谓排序,就是通过某种手段,使目标数据变为递增或递减,排序有很多种方式:插入、选择、交换、归并、映射 等等,本文会介绍这些方式下的详细实现方法,因篇幅较长,故分为上下文的形式介绍,本文是上半部分。

下面是通过排序生成的排行榜

TIOBE编程语言排行榜


📘正文

📖插入排序

插入,指将数据插入到合适位置,这个分类中包含了两种排序算法:直接插入希尔,其中希尔排序又称缩小增量排序,是一种非常快但不稳定的排序,它的时间复杂度计算极为复杂,下面详细来看看这两个排序吧

📃直接插入排序

思路:从第二个数开始,假设此数为 tmp ,逐个往前进行比对,如果前数大于 tmp ,就将前数值赋值到 tmp 处,然后继续往前比对,直到找到小于或等于 tmp 的数(或者比对至数据首)就停止,最后将 tmp 的值赋值到此处就行了

//直接插入排序
void InsertSort(int* pa, int n)
{assert(pa);//从后往前比较,找到合适位置就插入for (int i = 1; i < n; i++){int end = i;int tmp = pa[end];while (end){if (pa[end - 1] > tmp)pa[end] = pa[end - 1];elsebreak;end--;}pa[end] = tmp;}
}

动图展示
直接插入排序

时间复杂度:

  • 最坏:数据为一个逆序的等差数列 O(N^2)
  • 最好:顺序有序 O(N)

空间复杂度:

  • 仅仅只需要一个 tmp 变量 O(1)

稳定性:

  • 稳定,当两个相同数相遇时,后者是不会跑到前者前面去的

📃希尔排序

希尔排序是在直接插入排序上进行优化的一种排序,希尔排序分为两步:

  • 1、预排序,使得数据尽可能接近有序
  • 2、直接插入排序,最后调用一次直接插入排序,快速的完成排序

思路:预排序是通过区间划分实现的,假设当前区间为 gap,那么 1、1+gap*n 可以分成一组,同理2、3、4 都可以分,将这些组分别进行直接插入排序(数据少,效率高)。每完成一次分组排序,gap 就会缩小,直到 gap 为1时,进行一次直接插入排序,整个希尔排序就完成了

//希尔排序
void ShellSort(int* pa, int n)
{assert(pa);//思路:在插入排序的基础上,先分为n个区间,使数组尽可能有序(预排序)int gap = n;while (gap > 1){gap = gap / 3 + 1;	//确保gap最后为1for (int i = 0; i < n - gap; i++){int end = i;int tmp = pa[end + gap];while (end >= 0){//此时的end位于tmp之前sif (pa[end] > tmp)pa[end + gap] = pa[end];elsebreak;end -= gap;}pa[end + gap] = tmp;}}
}

动图展示(图太长了,分段展示)
1、预排序
希尔排序(预排序)
2、直接插入排序
直接插入排序

时间复杂度:

  • 希尔的时间复杂度计算是一个极其复杂的过程,需要用到高等数学的知识,这里直接记就行 O(N^1.3)

空间复杂度:

  • 仅仅只需要一个 tmp 变量 O(1)

稳定性:

  • 不稳定,当两个相同数被不同区间选中时,可能会发生交换现象,示例 1 4 2 2 3

📖选择排序

选择排序下也可以分为两种:简单选择与之前学过的堆排序,两者的本质是一样的,都是依赖于不断的比对,选到合适数后进行交换

📃简单选择排序

思路:选到最大的数,然后与 end 值交换;优化:选最大与最小,分别与 end 值和 begin 值交换

void swap(int*pnum1, int* pnum2)
{assert(pnum1 && pnum2);int tmp = *pnum1;*pnum1 = *pnum2;*pnum2 = tmp;
}//简单选择排序
void SelectSort(int* pa, int n)
{assert(pa);//思路:选最小的放前面,选最大的放后面int begin = 0;int end = n - 1;while (begin < end){int maxi = begin;int mini = begin;for (int i = begin + 1; i <= end; i++){if (pa[i] > pa[maxi])maxi = i;if (pa[i] < pa[mini])mini = i;}swap(&pa[begin], &pa[mini]);if (maxi == begin)maxi = mini;swap(&pa[end], &pa[maxi]);begin++, end--;}
}

动图展示:
简单选择排序

时间复杂度:

  • 这是一个比较糟糕的排序,因为不管是什么情况都是 O(N^2)

空间复杂度:

  • 仅借助变量辅助交换 O(1)

稳定性:

  • 不稳定,在选择时,可能把相同数中的后者选到前面,示例 1 4 2 2 3

注意:

  • 当交换 min 值与 begin 值后,如果 max 等于此时的 begin ,那么就要将 max 赋为 min,即 max = min

📃堆排序

思路:堆排序用到了堆的知识,如果想排升序的话建大堆,因为大堆中堆顶是最大值,将堆顶值与堆低值交换后,执行向下调整,使其再次变为大堆,就这样反复交换、调整,堆排序就完成了

void swap(int*pnum1, int* pnum2)
{assert(pnum1 && pnum2);int tmp = *pnum1;*pnum1 = *pnum2;*pnum2 = tmp;
}void AdjustDown(int* pa, int n, int parent)
{assert(pa);//大堆,找大孩子,调整int child = parent * 2 + 1;while (child < n){if (child + 1 < n && pa[child + 1] > pa[child])child++;if (pa[child] > pa[parent]){swap(&pa[child], &pa[parent]);parent = child;child = parent * 2 + 1;}elsebreak;}
}//堆排序
void HeapSort(int* pa, int n)
{assert(pa);//思路:升序建大堆,将堆顶元素沉底,然后再调整int parent = (n - 1 - 1) / 2;	//找父亲for (int i = parent; i >= 0; i--)AdjustDown(pa, n, i);//将堆顶元素沉底后调整int end = n - 1;while (end > 0){swap(&pa[0], &pa[end]);AdjustDown(pa, end--, 0);}
}

动图展示:
1、调整建堆
建堆
2、向下调整排序(上)
排序主体,上
3、向下调整排序(下)
排序主体,下

时间复杂度:

  • 向下调整+交换 O(N*logN)

空间复杂度:

  • 仅借助变量辅助交换 O(1)

稳定性:

  • 不稳定,当两个相同值分别位于首尾时,向下调整会打乱相对顺序,示例 2 4 1 3 2

📖排序小结

排序名称时间复杂度空间复杂度稳定性
直接插入排序O(N^2)O(1)稳定
希尔排序O(N^1.3)O(1)不稳定
简单选择排序O(N^2)O(1)不稳定
堆排序O(N*logN)O(1)不稳定

更多排序将在下篇文章中讲解


📘总结

排序有很多种,有好的、有坏的,我们要重点掌握优秀的排序,比如希尔堆排,当前其他排序的思想也得清楚,知道怎么实现就行了。本文只是排序的上半部分,涉及的排序都还算简单,下一篇文章中将会介绍排序大哥:快排,以及同样优秀的归并排序,知识点很难,但也很重要,敬请期待吧

如果你觉得本文写的还不错的话,期待留下一个小小的赞👍,你的支持是我分享的最大动力!

如果本文有不足或错误的地方,随时欢迎指出,我会在第一时间改正

星辰大海

相关文章推荐
关于“堆”,看看这篇文章就够了(附堆的两种应用场景)
听说你还不了解二叉树?赶紧进来轻松解决
听说Linux基础指令很多?这里都帮你总结好了

感谢支持

相关内容

热门资讯

安卓双系统添加应用,轻松实现多... 你有没有想过,你的安卓手机里可以同时运行两个系统呢?听起来是不是很酷?想象一边是熟悉的安卓系统,一边...
pipo安卓进系统慢,探究pi... 最近是不是发现你的Pipo安卓系统更新或者运行起来特别慢?别急,今天就来给你好好分析分析这个问题,让...
怎样使用安卓手机系统,安卓手机... 你有没有发现,安卓手机已经成为我们生活中不可或缺的一部分呢?从早晨闹钟响起,到晚上睡前刷剧,安卓手机...
双系统安卓安装caj,轻松实现... 你有没有想过,你的安卓手机里装上双系统,是不是就能同时享受安卓和Windows系统的乐趣呢?没错,这...
安卓使用ios系统教程,安卓用... 你是不是也和我一样,对安卓手机上的iOS系统充满了好奇?想要体验一下苹果的优雅和流畅?别急,今天我就...
安卓系统gps快速定位,畅享便... 你有没有遇到过这样的情况:手机里装了各种地图导航软件,但每次出门前都要等上好几分钟才能定位成功,急得...
安卓手机系统更新原理,原理与流... 你有没有发现,你的安卓手机最近是不是总在提醒你更新系统呢?别急,别急,让我来给你揭秘一下安卓手机系统...
安卓系统通知管理,全面解析与优... 你有没有发现,手机里的通知就像是一群调皮的小精灵,时不时地跳出来和你互动?没错,说的就是安卓系统的通...
安卓系统手机哪买,揭秘哪里购买... 你有没有想过,拥有一部安卓系统手机是多么酷的事情呢?想象你可以自由安装各种应用,不受限制地探索各种功...
安卓系统 ipv4,基于安卓系... 你知道吗?在智能手机的世界里,有一个系统可是无人不知、无人不晓,那就是安卓系统。而在这个庞大的安卓家...
目前安卓是什么系统,探索安卓系... 亲爱的读者,你是否曾好奇过,如今安卓系统究竟是什么模样?在这个科技飞速发展的时代,操作系统如同人体的...
安卓6.0系统比5.0,从5.... 你有没有发现,自从手机更新了安卓6.0系统,感觉整个人都清爽了不少呢?没错,今天咱们就来聊聊这个话题...
安卓2.36系统升级,功能革新... 你知道吗?最近安卓系统又来了一次大变身,那就是安卓2.36系统升级!这可不是一个小打小闹的更新,而是...
安卓系统源码怎么打开,并可能需... 你有没有想过,安卓系统的源码就像是一扇神秘的门,隐藏着无数的技术秘密?想要打开这扇门,你得掌握一些小...
安卓8.0系统体验视频,智能革... 你有没有听说安卓8.0系统最近可是火得一塌糊涂啊!作为一个紧跟科技潮流的数码达人,我当然要来给你好好...
宣传系统漫画app安卓,探索安... 亲爱的读者们,你是否曾在某个午后,百无聊赖地打开手机,想要寻找一些轻松愉悦的读物?今天,我要给你介绍...
鸿蒙替换安卓系统吗,开启智能生... 你知道吗?最近科技圈里可是炸开了锅,因为华为的新操作系统鸿蒙系统,据说要大举进军手机市场,替换掉安卓...
手机安卓系统深度清理,解锁手机... 手机里的东西是不是越来越多,感觉就像一个装满了杂物的储物柜?别急,今天就来教你一招——手机安卓系统深...
安卓上的windows系统,融... 你有没有想过,在安卓手机上也能体验到Windows系统的魅力呢?没错,这就是今天我要跟你分享的神奇故...
安卓系统焦点变化事件,Andr... 你知道吗?在安卓系统的世界里,最近发生了一件超级有趣的事情——焦点变化事件。这可不是什么小打小闹,它...