◆博主名称少司府欢迎来到少司府的博客☆*: .. o(≧▽≦)o ..:*☆⭐数据结构系列个人专栏初阶数据结构_少司府的博客-CSDN博客⭐编程基础训练系列个人专栏编程基础50题_少司府的博客-CSDN博客⭐名不显时心不朽再挑灯火看文章目录一、排序的概念及其运用1.1 排序的相关概念1.2 排序的相关运用1.3 常见的几种排序算法二、常见排序算法的实现升序2.1 冒泡排序2.2 选择排序2.3 堆排序2.3.1 向下调整函数2.3.2 堆排序2.4 插入排序2.5 希尔排序2.6 快速排序2.6.1 hoare 版本2.6.2 前后指针版2.7 归并排序2.8 计数排序三、排序的总结3.1 稳定性介绍3.2 总结一、排序的概念及其运用1.1 排序的相关概念排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。内部排序数据元素全部放在内存中的排序。外部排序数据元素太多不能同时放在内存中根据排序过程的要求不断地在内外存之间移动数据的排序。1.2 排序的相关运用排序算法在生活中无处不在购物APP中商品的价格排行、国内各个高校的排名等等。1.3 常见的几种排序算法除此之外我们列举了以下几种常见的排序算法。其中我们比较熟悉的就是冒泡排序了。我们可以通过下面这个网站来查看各种排序的演示图https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html二、常见排序算法的实现升序2.1 冒泡排序冒泡排序作为常见的排序算法其核心不过是遍历两两交换将大的数字冒到后面去其时间复杂度是O(n^2)本身没有什么实践意义但是具有教学意义作为新生入门的排序刚刚好。2.2 选择排序和冒泡排序一样直接选择排序也是时间复杂度为O(n^2)的排序算法其本身也没有什么实践意义。其核心是遍历找到最大元素的下标maxi将它与最后一个元素交换这样就把最大的排到了最后。这里做了优化同时走最大和最小同时排出最大和最小可以提升一点点效率。2.3 堆排序2.3.1 向下调整函数堆排序的核心就是“建堆”和“排序”因此我们需要先写一个向下调整函数来实现建堆。如图while循环向下不断调整若孩子比父亲大则交换。2.3.2 堆排序堆排序的主要排序逻辑如图先建大堆取堆顶元素放到最后在缩减范围之后不断向下调整将大的数放到后面完成升序的排序逻辑。其具体逻辑在上期中讲过可点击这里https://blog.csdn.net/CAO_070413/article/details/158386332?fromshareblogdetailsharetypeblogdetailsharerId158386332sharereferPCsharesourceCAO_070413sharefromfrom_link堆排序的时间复杂度是O(N*logN)。2.4 插入排序在观看源码之前我们先简单介绍一下直接插入排序。直接插入排序是一种简单的排序算法其主要逻辑是默认前面是有序的数列不断将后面的数插入到前面的数列之中。我们玩扑克牌的时候也是用的插入排序的逻辑。如图while循环之前定义一个end指向有序数列的最后一个数tmp保存end后一个数也就是待插入的数。升序排序的话如果tmp比end指向的数小就不断把有序的数字往后推当找到第一个小于等于tmp的数字时就把tmp插到它的后面。插入排序的时间复杂度是O(N^2)。2.5 希尔排序希尔排序的底层是插入排序可以理解为对插入排序的拓展由于是希尔这位大佬提出来的所以叫做希尔排序ShellSort。希尔排序的核心思想是先对待排序数组进行预排序使其变得相对有序最后再进行直接插入排序。虽然有预排序看起来步骤多了但实际上它的效率却是大大提高了。如图可以看到希尔排序的底层仍然是插入排序只是插入排序是一个一个地挪动而希尔排序是先将数列分为多组每组内部进行插入排序也就是预排序以gap为单位进行挪动。gapgap/31一个是减少预排序的次数另一个是让最后一次gap1这样最后一次就是直接插入排序了。希尔排序的时间复杂度是O(N^1.3)。2.6 快速排序2.6.1 hoare 版本我们在学C语言的时候应该有了解或者学习过qsort这个函数这个函数的底层就是快速排序。这里有个动图展示快速排序https://gitee.com/bithange/113-issues/raw/master/24%E5%B9%B4-05%E6%9C%8827%E6%97%A5--%E6%8E%92%E5%BA%8F/%E5%8A%A8%E5%9B%BE/hoare.gif如图初识化key指向第一个数L和R同时往两边走R先走R找到比key小的数字L找到比key大的数字并将这两个数交换当L和R相遇的时候其指向的数字是比key小的将key和相遇位置交换再对左右两边进行此操作也就是递归。如图该代码在原版本上加入了三数取中和小区间优化。三数取中是找到left、right和mid的中间值下标key指向中间值如果数组已经有序没有优化的化会让其退化为时间复杂度为O(N^2)的算法递归深度增加导致栈溢出。小区间优化是让最后几层不递归直接用其他的算法逻辑这样能大大减少递归次数提高效率。2.6.2 前后指针版由于hoare版本要考虑的细节比较多且不容易理解后来又对快速排序做了优化前后指针版更容易理解一些。这是前后指针的动图https://gitee.com/bithange/113-issues/raw/master/24%E5%B9%B4-05%E6%9C%8827%E6%97%A5--%E6%8E%92%E5%BA%8F/%E5%8A%A8%E5%9B%BE/%E5%89%8D%E5%90%8E%E6%8C%87%E9%92%88.gif如图初始化prev指向起始位置cur指向后一个位置。cur向后面移动当arr[cur] arr[keyi]的时候交换prev和cur指向的值prev和cur不断将比arr[keyi]小的值放到左边大的值放到右边。如图可以将单趟封装成一个子函数。2.7 归并排序归并排序采用分治的思想其核心是将已经有序的数列合并变成一个新的有序的数列。如图类似于二叉树的结构我们把数列不断分为两组若只有一个数则认为已经有序了。如图归并排序也是需要封装一个子函数来处理排序逻辑。与其他排序不同的是归并排序需要额外开一个空间复杂度为ON的空间begin1、end1begin2、end2分别指向两组数列的首尾不断递归使其有序。把排好序的数列不断追加到tmp数列中。最后再用memcpy把tmp拷贝到原数组去。归并排序时间复杂度是O(N*logN)空间复杂度是O(N)。2.8 计数排序与上述排序都不一样的是计数排序是一种非比较排序。其核心思想统计相同元素出现次数并根据统计的结果将序列回收到原来的序列中。如图先找到最大值和最小值相差的范围再开辟一个count的空间用于统计次数最后通过数字出现的次数来对原数组进行排序。其算法的时间复杂度是O(Nrange)空间复杂度是O(N)。三、排序的总结3.1 稳定性介绍稳定性概念相等的值在排序后其相对位置保持不变则稳定性强。3.2 总结时间复杂度空间复杂度稳定性直接插入排序O(N^2)O(1)强希尔排序O(N^1.3)O(1)弱选择排序O(N^2)O(1)弱堆排序O(N*logN)O(1)弱冒泡排序O(N^2)O(1)强快速排序O(N*logN)O(logN)弱归并排序O(N*logN)O(N)强本期的分享就到这里如果觉得博主的文章比较对胃口的话可以点一个小小的关注~您的三连是我持续更新的动力~
初识数据结构：排序算法
◆博主名称少司府欢迎来到少司府的博客☆*: .. o(≧▽≦)o ..:*☆⭐数据结构系列个人专栏初阶数据结构_少司府的博客-CSDN博客⭐编程基础训练系列个人专栏编程基础50题_少司府的博客-CSDN博客⭐名不显时心不朽再挑灯火看文章目录一、排序的概念及其运用1.1 排序的相关概念1.2 排序的相关运用1.3 常见的几种排序算法二、常见排序算法的实现升序2.1 冒泡排序2.2 选择排序2.3 堆排序2.3.1 向下调整函数2.3.2 堆排序2.4 插入排序2.5 希尔排序2.6 快速排序2.6.1 hoare 版本2.6.2 前后指针版2.7 归并排序2.8 计数排序三、排序的总结3.1 稳定性介绍3.2 总结一、排序的概念及其运用1.1 排序的相关概念排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。内部排序数据元素全部放在内存中的排序。外部排序数据元素太多不能同时放在内存中根据排序过程的要求不断地在内外存之间移动数据的排序。1.2 排序的相关运用排序算法在生活中无处不在购物APP中商品的价格排行、国内各个高校的排名等等。1.3 常见的几种排序算法除此之外我们列举了以下几种常见的排序算法。其中我们比较熟悉的就是冒泡排序了。我们可以通过下面这个网站来查看各种排序的演示图https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html二、常见排序算法的实现升序2.1 冒泡排序冒泡排序作为常见的排序算法其核心不过是遍历两两交换将大的数字冒到后面去其时间复杂度是O(n^2)本身没有什么实践意义但是具有教学意义作为新生入门的排序刚刚好。2.2 选择排序和冒泡排序一样直接选择排序也是时间复杂度为O(n^2)的排序算法其本身也没有什么实践意义。其核心是遍历找到最大元素的下标maxi将它与最后一个元素交换这样就把最大的排到了最后。这里做了优化同时走最大和最小同时排出最大和最小可以提升一点点效率。2.3 堆排序2.3.1 向下调整函数堆排序的核心就是“建堆”和“排序”因此我们需要先写一个向下调整函数来实现建堆。如图while循环向下不断调整若孩子比父亲大则交换。2.3.2 堆排序堆排序的主要排序逻辑如图先建大堆取堆顶元素放到最后在缩减范围之后不断向下调整将大的数放到后面完成升序的排序逻辑。其具体逻辑在上期中讲过可点击这里https://blog.csdn.net/CAO_070413/article/details/158386332?fromshareblogdetailsharetypeblogdetailsharerId158386332sharereferPCsharesourceCAO_070413sharefromfrom_link堆排序的时间复杂度是O(N*logN)。2.4 插入排序在观看源码之前我们先简单介绍一下直接插入排序。直接插入排序是一种简单的排序算法其主要逻辑是默认前面是有序的数列不断将后面的数插入到前面的数列之中。我们玩扑克牌的时候也是用的插入排序的逻辑。如图while循环之前定义一个end指向有序数列的最后一个数tmp保存end后一个数也就是待插入的数。升序排序的话如果tmp比end指向的数小就不断把有序的数字往后推当找到第一个小于等于tmp的数字时就把tmp插到它的后面。插入排序的时间复杂度是O(N^2)。2.5 希尔排序希尔排序的底层是插入排序可以理解为对插入排序的拓展由于是希尔这位大佬提出来的所以叫做希尔排序ShellSort。希尔排序的核心思想是先对待排序数组进行预排序使其变得相对有序最后再进行直接插入排序。虽然有预排序看起来步骤多了但实际上它的效率却是大大提高了。如图可以看到希尔排序的底层仍然是插入排序只是插入排序是一个一个地挪动而希尔排序是先将数列分为多组每组内部进行插入排序也就是预排序以gap为单位进行挪动。gapgap/31一个是减少预排序的次数另一个是让最后一次gap1这样最后一次就是直接插入排序了。希尔排序的时间复杂度是O(N^1.3)。2.6 快速排序2.6.1 hoare 版本我们在学C语言的时候应该有了解或者学习过qsort这个函数这个函数的底层就是快速排序。这里有个动图展示快速排序https://gitee.com/bithange/113-issues/raw/master/24%E5%B9%B4-05%E6%9C%8827%E6%97%A5--%E6%8E%92%E5%BA%8F/%E5%8A%A8%E5%9B%BE/hoare.gif如图初识化key指向第一个数L和R同时往两边走R先走R找到比key小的数字L找到比key大的数字并将这两个数交换当L和R相遇的时候其指向的数字是比key小的将key和相遇位置交换再对左右两边进行此操作也就是递归。如图该代码在原版本上加入了三数取中和小区间优化。三数取中是找到left、right和mid的中间值下标key指向中间值如果数组已经有序没有优化的化会让其退化为时间复杂度为O(N^2)的算法递归深度增加导致栈溢出。小区间优化是让最后几层不递归直接用其他的算法逻辑这样能大大减少递归次数提高效率。2.6.2 前后指针版由于hoare版本要考虑的细节比较多且不容易理解后来又对快速排序做了优化前后指针版更容易理解一些。这是前后指针的动图https://gitee.com/bithange/113-issues/raw/master/24%E5%B9%B4-05%E6%9C%8827%E6%97%A5--%E6%8E%92%E5%BA%8F/%E5%8A%A8%E5%9B%BE/%E5%89%8D%E5%90%8E%E6%8C%87%E9%92%88.gif如图初始化prev指向起始位置cur指向后一个位置。cur向后面移动当arr[cur] arr[keyi]的时候交换prev和cur指向的值prev和cur不断将比arr[keyi]小的值放到左边大的值放到右边。如图可以将单趟封装成一个子函数。2.7 归并排序归并排序采用分治的思想其核心是将已经有序的数列合并变成一个新的有序的数列。如图类似于二叉树的结构我们把数列不断分为两组若只有一个数则认为已经有序了。如图归并排序也是需要封装一个子函数来处理排序逻辑。与其他排序不同的是归并排序需要额外开一个空间复杂度为ON的空间begin1、end1begin2、end2分别指向两组数列的首尾不断递归使其有序。把排好序的数列不断追加到tmp数列中。最后再用memcpy把tmp拷贝到原数组去。归并排序时间复杂度是O(N*logN)空间复杂度是O(N)。2.8 计数排序与上述排序都不一样的是计数排序是一种非比较排序。其核心思想统计相同元素出现次数并根据统计的结果将序列回收到原来的序列中。如图先找到最大值和最小值相差的范围再开辟一个count的空间用于统计次数最后通过数字出现的次数来对原数组进行排序。其算法的时间复杂度是O(Nrange)空间复杂度是O(N)。三、排序的总结3.1 稳定性介绍稳定性概念相等的值在排序后其相对位置保持不变则稳定性强。3.2 总结时间复杂度空间复杂度稳定性直接插入排序O(N^2)O(1)强希尔排序O(N^1.3)O(1)弱选择排序O(N^2)O(1)弱堆排序O(N*logN)O(1)弱冒泡排序O(N^2)O(1)强快速排序O(N*logN)O(logN)弱归并排序O(N*logN)O(N)强本期的分享就到这里如果觉得博主的文章比较对胃口的话可以点一个小小的关注~您的三连是我持续更新的动力~
