易企营销型网站建设企业,黄骅市找工作,网络推广营销工具,wordpress页面无法编辑器#x1f525;博客主页#xff1a; 小羊失眠啦. #x1f3a5;系列专栏#xff1a;《C语言》 《数据结构》 《Linux》《Cpolar》 ❤️感谢大家点赞#x1f44d;收藏⭐评论✍️ 文章目录 一、排序的概念及其运用1.1 排序的概念1.2 常见的算法排序 二、 冒泡排序三、直接插入排… 博客主页 小羊失眠啦. 系列专栏《C语言》 《数据结构》 《Linux》《Cpolar》 ❤️感谢大家点赞收藏⭐评论✍️ 文章目录 一、排序的概念及其运用1.1 排序的概念1.2 常见的算法排序 二、 冒泡排序三、直接插入排序四、希尔排序五、 选择排序六、各大排序算法的复杂度和稳定性 一、排序的概念及其运用
1.1 排序的概念
排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。排序算法就是如何使得记录按照要求排列的方法。
稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。
内部排序数据元素全部放在内存中的排序。
外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。
1.2 常见的算法排序
排序算法分为比较类排序和非比较类排序如下图所示 二、 冒泡排序
思想 : 在一个序列中每次对序列中的相邻记录的键值大小进行比较将较大(升序)或较小(降序)的记录向后移动。如此循环大/小的记录会慢慢“浮”到序列的后端整个过程就像是冒泡一样顾称之为冒泡排序。冒泡过程以下是对某个序列进行冒泡排序的过程 可以看出对于上面具有5个元素的无序数组我们通过4趟的冒泡后就将其变为有序数组每一趟冒泡后都可以使最大的数沉底。 动图演示我们可以通过一下动图感受一下冒泡两两比较的过程 循环控制很明显我们需要两层循环来控制冒泡排序的过程。内层循环控制当前趟的数据交换外层循环控制冒泡排序的趟数。外层循环结束条件由于每一趟结束后都有一个数冒到序列后端因此对于N个数的序列来说一共需要N-1趟(只剩一个数不需要冒泡)。
for (int i 0; i n - 1; i) //外层循环N-1趟
{;
}内层循环结束条件内层循环用于数据的比较。已知N个数据共需比较N-1次由于每一趟结束后就有数据到正确的位置下一趟需要比较的数据个数就会少1因此每趟的比较次数随着趟数的增加呈递减趋势初始为N-1次。
for (int i 0; i n - 1; i) //外层循环N-1趟
{for (int j 0; j n - 1 - i; j) //内层循环次数随趟数增加而递减初始为N-1{;}
}完整代码
void swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}void BubblingSort(int* a, int n)
{for (int i 0; i n - 1; i) //外层循环N-1趟{for (int j 0; j n - 1 - i; j) //内层循环次数随趟数增加而递减初始为N-1{if (a[j] a[j 1]) //升序排列较大的往后移{swap(a[j], a[j 1]); //交换}}}
}改进优化上面的代码还存在着改进空间我们来看下面两个情景 对于情境1我们只需一趟冒泡即可让数组有序而如果按照上面的代码我们依旧要进行4趟的冒泡即有三趟是无效的。 而情境2就更夸张了数组已经有序我们却傻乎乎的做了4趟无效冒泡。无疑是非常浪费时间的。 考虑到这些情况我们提出了优化方案在每趟结束后判断一下当前趟是否发生了元素交换如果没有则说明序列已经有序了及时止损反之继续。优化后的代码如下 void swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}void BubblingSort(int* a, int n)
{for (int i 0; i n - 1; i) //外层循环N-1趟{int flag 0;for (int j 0; j n - 1 - i; j) //内层循环次数随趟数增加而递减初始为N-1{if (a[j] a[j 1]) //升序排列较大的往后移{swap(a[j], a[j 1]); //交换flag 1;}}if (flag 0)break;}
}时间/空间复杂度结合上面的图片和代码我们可以看出总共N-1趟每趟N-1N-2…次比较共比较 (N-1) (N-2) (N-3) (N-4) (N-5) … 1次时间复杂度为O(N^2)而由于没有额外的辅助空间空间复杂度为O(1)。稳定性分析由于我们是将较大的或较小的进行交换当两个数相等时并不会进行交换因而不会改变相同元素的先后次序所以冒泡排序是稳定的排序。 三、直接插入排序
基本思想
插入排序的基本思想是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列。 过程分析
我们可以将第一个元素作为一个有序序列从第二个元素开始插入到这个有序序列中过程如下 以升序为例 当插入第i个元素时(i1)说明前面的array[0],array[1],…,array[i-1]已经排好序我们将array[i]位置的值从后往前与array[i-1],array[i-2],…依次进行比较找到插入位置即将array[i]插入原来位置上的元素顺序后移。 为什么不从前往后开始进行比较 如果我们从前往后进行比较当找到插入位置时根据顺序表的插入我们知道必须先将后面的元素全部后移而后移又不能从前往后移否则会造成元素覆盖我们必须从后往前移动。折腾了半天又要从后往前遍历那为什么不一开始就从后往前比较在比较的同时一并挪动元素何乐而不为呢 单趟插入动图 全过程动图: void InsertSort(int* a, int n)
{for (int i 0; i n - 1; i){int end i;int tmp a[end 1];while (end 0){if (a[end] tmp)a[end 1] a[end];elsebreak;end--;}a[end 1] tmp;}
}复杂度/稳定性分析 复杂度:
根据上面的动图我们可以发现当元素集合越接近有序直接插入的时间效率越高当元素集合已经有序时时间复杂度便是O(N)即遍历一遍数组最优情况。
而时间复杂度我们看的是最坏情况即数组元素逆序的情况。此时每次插入相当于头插而头插的时间复杂度为O(N)因此总时间复杂度为O( 插入次数 * 单次插入时间复杂度 ) O(N^2)。
而除了待排序数组之外只有常数级的辅助空间空间复杂度为O(1)。
稳定性:
由于我们是大于tmp才进行元素挪动当等于tmp时直接将tmp放到后方不会对相同元素的顺序进行改变因此直接插入排序是稳定的排序 四、希尔排序
基本思想 希尔排序又称缩小增量法其基本思想是选出一个整数gap表示增量根据gap将待排序的记录分为gap组所有距离为gap的记录分在同一组然后对每一组进行直接插入排序。随着排序次数的增多增量gap逐渐减少当gap1时即所有记录分在同一组进行直接插入排序排序完成后序列便有序了算法结束。分组方法如下 过程分析:
首先我们需要对gap的初始值进行确定这并没有一个确定的答案一般是按照数据量来进行选取。一般我们选取gap n/3 1或者gap n/2作为gap的初始值。根据算法的思想我们观察到gap是在不断地进行缩小最后缩小到1进行直接插入排序。因此我们gap的缩小增量可以继续使用gap gap/3 1或gap n/2来表示。对1、2点进行合并后我们可以这样用来表示gap的迭代更新
int gap n; //n为序列元素个数
while(gap 1)
{//gap gap/2;gap gap/3 1;//每组进行直接插入排序//...
}上面的循环在以下两种情况下会结束 n 1即序列只有一个元素此时无需进行排序不会进入循环n ! 1 gap 1由于gap的更新是在插入排序之前因此当循环判断到gap 1时上一次进行的就是以1为gap增量的直接插入排序此时序列已经有序退出循环。 为什么要取gap gap/3 1而不是gap gap/3 由于最后gap要缩小到1进行直接插入排序而如果我们选取gap gap/3时假设gap初始为6第一次更新后gap2第二次更新后gap0(向下取整)循环便结束了并不会进行gap1时的插入排序。因此为了避免这种情况的发生我们让gap gap/3 1保证最后一次gap一定为1。 那为什么取gap gap/2而不是gap gap/2 1 这种情况不需要处理的原因是gap不可能等于0因为进入循环的条件是gap1,而gap只有等于0或1时gap/2才会为0。因此无论gap初始为多少最后一定都会在gap1处停下。并且当gap2时使用gap gap/2 1会出现死循环/font噢 每组之间进行的就是我们上面介绍的直接插入排序不一样的是相邻元素的距离是gap而不是1。以下是gap 3时的单趟希尔排序的动图过程 下面是希尔排序的全过程以gap gap/3 1为例 通过观察我们可以发现实际上希尔排序就是直接插入排序的优化版。随着每一趟的分组排序序列越来越接近有序。前面我们说过直接插入排序在序列越接近有序的情况下效率越高希尔排序就是通过每趟的预排序来使得序列越来越接近有序从而提高直接插入排序的整体效率。要点提炼当gap 1时对序列进行分组预排序目的是使得序列越来越接近有序当gap 1时数组接近有序此时进行直接插入排序效率大幅提高。
//写法1一组一组排
void ShellSort1(int* a, int n)
{int gap n;while (gap 1){//1gap 1,预排序//2gap 1直接插入排序gap gap / 3 1; //缩小增量for (int j 0; j gap; j) //一组一组进行插入排序共gap组{//对当前组进行直接插入排序,组内相邻元素相距gap。//(其实就相当于把上面介绍的直接插入排序代码中的-1改成-gap即可)for (int i j; i n - gap; i gap){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。那么我们实际上不用一组一组分开排而是采用多组并排的方式这样就可以少写一个for循环代码如下 void ShellSort(int* a, int n)
{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很大或者gap很小的情况下每趟排序的时间复杂度为O(N)共进行log3n趟那我们是不是可以认为希尔排序的时间复杂度为O(NlogN)实际上并不行因为当gap处于中间的过程时时间复杂度的分析实际上是个很复杂的数学问题。每一趟预排序之后都对下一趟排序造成影响这就好比叠buff的过程。 以下分别是两本书中对希尔排序时间复杂度的说法 1、《数据结构(C语言版)》— 严蔚敏 2、《数据结构-用面相对象方法与C描述》— 殷人昆 因为我们上面的gap是按照Knuth提出的方式取值的并且Knuth进行了大量的试验统计时间复杂度我们就按照O(n^1.25)到O(1.6n^1.25)来进行取值。
然后就是空间复杂度由于我们依旧只用到了常数级的辅助变量因此空间复杂度为O(1)。
稳定性:
由于希尔排序是分组进行排序当相同的数被分到不同组时很可能就会改变相同的数的顺序因此希尔排序是不稳定的排序。 五、 选择排序
思想 : 每一次从待排序的数据元素中选出最小(升序)或最大(降序)的一个元素存放在序列的起始位置直到全部待排序的数据元素排完。选择过程以下是对某个序列进行选择排序的过程 动图演示我们一样通过动图感受一下选择排序的过程 循环控制类似的我们需要两层循环来控制选择排序的过程。内层循环遍历序列找出最大/最小值外层循环控制选择的次数。外层循环结束条件每一次遍历完都可以选出一个数换到起始位置一共N个数故要选N-1次(最后一个数不需要选择)
for (int i 0; i n-1; i) //外层循环共要选择n-1次
{;
}内层循环结束条件内层循环通过比较进行选数一开始N个数需要比较N-1次然后每趟结束后下一次选择的起始位置就往后移动一位比较次数减1
for (int i 0; i n-1; i) //外层循环共选择n-1次
{for (int j i 1; j n; j) //内层循环起始位置开始向后进行比较选最小值{;}
}完整代码
void swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}void SelectSort(int* a, int n)
{for (int i 0; i n - 1; i) //外层循环共选择n-1次{int mini i; //记录最小值的下标初始为第一个数下标for (int j i 1; j n; j) //内层循环起始位置开始向后进行比较选最小值{if (a[mini] a[j]) //比最小值小交换下标{mini j;}}swap(a[mini], a[i]); //将最小值与起始位置的数据互换}
}时间/空间复杂度一共选了N-1次每次选择需要比较N-1N-2N-3…次加起来和冒泡一样时间复杂度为O(N)没有用到辅助空间空间复杂度为O(1)稳定性分析由于是选数交换在交换的过程中很可能会打乱相同元素的顺序例如下面这个例子 我们发现在第一趟交换中黑5被交换到了红5后面在整个排序结束后黑5依然在红5的后方与最开始的顺序不一致。由此我们可以得出选择排序是不稳定的排序。 六、各大排序算法的复杂度和稳定性
排序算法时间复杂度(最好)时间复杂度(平均)时间复杂度(最坏)空间复杂度稳定性数据敏感度冒泡排序稳定强选择排序不稳定弱直接插入排序稳定强希尔排序不稳定强堆排序不稳定弱快速排序不稳定强归并排序稳定弱
本次的内容到这里就结束啦。希望大家阅读完可以有所收获同时也感谢各位铁汁们的支持。文章有任何问题可以在评论区留言小羊一定认真修改写出更好的文章~~
