深圳市建设监理协会网站,利用代码如何做网站,肇庆网站搜索排名,东宁做木耳招工人网站一、排序算法说明排序的定义#xff1a;对一个无序的序列进行排序的过程。输入#xff1a;n个数#xff1a;a1,a2,a3,…,an。输出#xff1a;n个数的排列:a1,a2,a3,…,an#xff0c;使得a1a2a3…an。排序的稳定性#xff1a;相同值的节点相对位置是否会发…一、排序算法说明排序的定义对一个无序的序列进行排序的过程。输入n个数a1,a2,a3,…,an。输出n个数的排列:a1,a2,a3,…,an使得a1a2a3…an。排序的稳定性相同值的节点相对位置是否会发生改变。稳定如果a原本在b前面而ab排序之后a仍然在b的前面。不稳定如果a原本在b的前面而ab排序之后a可能会出现在b的后面。排序的时间复杂度一个算法执行所耗费的时间一般在三种情况下考虑最好情况、最坏情况、平均情况。空间复杂度运行完一个程序所需内存的大小。二、各种排序算法性能分析1. 插入排序1.1 直接插入排序直接插入排序的原理是将未排好序的序列一个个地插入到已排好序的序列中插入时需要与已排好序的序列进行多次比较直到找到合适的位置插入而原来已排好序的部分节点可能需要进行后移操作这个过程中需要一个额外的空间保存一个值用于交换节点所以空间复杂度为O(1)。时间复杂度最坏情况当待排序序列正好为逆序状态首先遍历整个序列之后一个个地将待插入元素放在已排序的序列最前面之后的所有元素都需要向后移动一位所以比较和移动的时间复杂度都是O(n)再加上遍历整个序列的复杂度总复杂度为O(n^2)。最好情况当待排序序列正好为正序状态则遍历完整个序列当插入元素时只比较一次就够了所以时间复杂度为O(n)。平均情况当被插入的元素放在已排序的序列中间位置时为平均情况比较和移动的时间复杂度为O(n/2)所以总的时间复杂度依然为O(n^2)。稳定性插入排序是在一个已经有序的小序列的基础上一次插入一个元素。当然刚开始这个有序的小序列只有1个元素就是第一个元素。比较是从有序序列的末尾开始也就是想要插入的元素和已经有序的最大者开始比起如果比它大则直接插入在其后面否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的那么插入元素把想插入的元素放在相等元素的后面。所以相等元素的前后顺序没有改变从原无序序列出去的顺序就是排好序后的顺序所以插入排序是稳定的。1.2 希尔排序希尔排序是对直接插入排序的优化它的原理是加大插入排序中元素的间隔并在这些有间隔的元素中进行插入排序从而使数据进行大幅度的移动当进行过依次排序后再减小间隔再一次进行插入排序直到间隔缩小为1。这样做的目的可以使得最后排序时整个序列基本有序而无需再进行过多的元素比较和移动次数在这个过程中也只需要一个额外的空间保存一个值用于交换节点所以空间复杂度为O(1)。时间复杂度与增量的选取有关计算起来较为复杂不再细述。稳定性希尔排序是进行多次直接插入排序的算法由于多次插入排序虽然每一次插入排序是稳定的不会改变相同元素的相对顺序但在不同的插入排序过程中相同的元素可能在各自的插入排序中移动最后其稳定性就会被打乱所以希尔排序是不稳定的。2. 选择排序2.1 直接选择排序直接选择排序的原理是在待排序的序列中选取最小大的值放在序列的第一个位置。遍历整个序列首先选取第一位置的值分别与之后所有的值比较如果后边值更小则与之交换直到第一轮遍历结束时序列第一个位置的值就是最小的接下来继续从第二个、第三个做同样的操作此过程需要一个额外的空间保存最小值用于交换所以空间复杂度为O(1)。时间复杂度序列无论是正序还是逆序状态每一轮的最小值需要比较到最后才能确定所以最坏情况和最好情况下都需要 比较n次再加上遍历整个序列的O(n)总的复杂度为O(n^2)平均情况的复杂度也是O(n^2)。稳定性直接选择排序是给每个位置选择当前元素最小的比如给第一个位置选择最小的在剩余元素里面给第二个元素选择第二小的依次类推直到第n-1个元素第n个元素不用选择了因为只剩下它一个最大的元素了。那么在一趟选择如果当前元素比一个元素小而该小的元素又出现在一个和当前元素相等的元素后面那么交换后稳定性就被破坏了。举个例子序列5 8 5 2 9 第一遍选择时第1个元素5会和2交换那么原序列中2个5的相对前后顺序就被破坏了所以选择排序不是一个稳定的排序算法。2.2 堆排序堆排序是对直接选择排序的改进算法选择排序的特点在于每次选取最小或最大的值而选取最大值时的比较次数为复杂度的关键堆排序采用二叉树的方法存储元素每个节点都满足父节点的值大于等于子节点的特点与直接选择排序类似堆排序需要两个个值的空间来存储临时变量用于交换节点一次用于存储子树最大节点用于交换子节点一次用于存储堆顶的值用于交换最后的节点所以空间复杂度为O(1)。采用堆的方式寻找最大值是降低时间复杂度的关键假设有n个数据需要n-1次建堆的过程每次建堆的时间复杂度为log2n但是无论序列的开始状态如何都需要对堆进行遍历寻找最大值所以在最好情况、最坏情况和平均情况下的时间复杂度都是O(nlog2n)。稳定性堆排序是利用堆的特点堆的结构是节点i的孩子为2*i和2*i1节点大顶堆要求父节点大于等于其2个子节点小顶堆要求父节点小于等于其2个子节点。在一个长为n 的序列堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆)这3个元素之间的选择当然不会破坏稳定性。但当为n /2-1, n/2-2, …1这些个父节点选择元素时就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了而第n/2-1个父节点把后面一个相同的元素没有交换那么这2个相同的元素之间的稳定性就被破坏了。所以堆排序不是一个稳定的排序算法。3. 交换排序3.1 冒泡排序冒泡排序是交换类排序算法的典型实现它的原理是遍历整个序列比较前后相邻两个值的大小如果前边比后边大则交换它们直到序列的最后的两个值进行比较这样最后的值就是最大的之后再进行第二轮、第三轮遍历直到剩下序列的最前的值。从实现原理上可以知道冒泡排序只需要一个值的空间用于交换节点所以空间复杂度为O(1)。时间复杂度最坏情况序列为逆序状态则每一轮遍历都需要n次交换位置所以时间复杂度为O(n^2)。最好情况序列为正序状态每一轮遍历不需要交换位置所以时间复杂度为O(n)。平均情况每一轮遍历需要n/2次交换位置所以时间复杂度依然为O(n^2)。稳定性冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较交换也发生在这两个元素之间。所以如果两个元素相等不会发生交换。如果两个相等的元素没有相邻那么即使通过前面的两两交换把两个相邻起来也不会发生交换所以相同元素的前后顺序并没有改 变所以冒泡排序是一种稳定排序算法。3.2 快速排序快速排序是另一种交换类排序方法它的原理是选择一个基准元素通常选择第一个元素或者最后一个元素通过一趟扫描将待排序列分成两部分一部分比基准元素小一部分大于等于基准元素此时基准元素在其排好序后的正确位置然后再用同样的方法递归地排序划分的两部分。首先就地快速排序使用的空间是O(1)的而真正消耗空间的就是递归调用了因为每次递归就要保持一些数据每一次都平分数组的情况下空间复杂度为O(logn) 最差的情况下空间复杂度为O(n)。时间复杂度最坏情况每一次选取的基准元素都是最大或最小的复杂度为O(n^2)最好情况每一次选取的基准元素都能平分整个序列由于快排涉及到递归调用所以时间复杂度为O(nlog2n)。平均情况平均情况下复杂度也是O(nlog2n)。稳定性快速排序有两个方向左边的i下标一直往右走当a[i]a[center_index]其中center_index是中枢元素的数组下标一般取为数组第0个元素。而右边的j下标一直往左走当a[j]a[center_index]。如果i和j都走不动了ij 交换a[i]和a[j],重复上面的过程直到ij。 交换a[j]和a[center_index]完成一趟快速排序。在中枢元素和a[j]交换的时候很有可能把前面的元素的稳定性打乱比如序列为 5 3 3 4 3 8 9 10 11现在中枢元素5和3(第5个元素下标从1开始计)交换就会把元素3的稳定性打乱所以快速排序是一个不稳定的排序算法不稳定发生在中枢元素和a[j] 交换的时刻。4. 归并排序归并排序先递归的把数组划分为两个子数组一直递归到数组中只有一个元素然后再调用函数把两个子数组排好序因为该函数在递归划分数组时会被压入栈所以这个函数真正的作用是对两个有序的子数组进行排序。排序函数的步骤让两个数组的元素进行比较把大的/小的元素存放到临时数组中如果有一个数组的元素被取光了那就直接把另一数组的元素放到临时数组中然后把临时数组中的元素都复制到实际的数组中。所以 归并的空间复杂度就是那个临时的数组和递归时压入栈的数据占用的空间n logn所以空间复杂度为:O(n)。时间复杂度归并排序的时间主要花在了划分序列和合并序列上由于是采用递归的方式进行合并所以与快速排序类似树的每层元元素的个数最多是n也就代表着每层最多进行n次比较而递归树最多只有log2n层而且不管元素在什么情况下都要做这些步骤所以该算法的最优时间复杂度和最差时间复杂度及平均时间复杂度都是一样都是O( nlogn )。稳定性归并排序的原理是把序列递归地分成短序列递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换)然后把各个有序的段序列合并成一个有序的长序列不断合并直到原序列全部排好序。可以发现在1个或2个元素时1个元素不会交换2个元素如果大小相等也不会交换所以不会破坏稳定性。而在短的有序序列合并的过程中稳定性也没有受到破坏合并过程中可以保证如果两个当前元素相等时把处在前面的序列的元素保存在结果序列的前面这样就保证了稳定性。所以归并排序是稳定的排序算法。三、各种排序算法性能总结参考排序算法之性能分析及总结_Blog-CSDN博客blog.csdn.net超详细的八大排序算法的各项比较以及各自的特点_柯南的博客-CSDN博客blog.csdn.net
